OP-00953 Open

The Kupitz–Perles balanced line conjecture

Let $X \subset \mathbb{R}^2$ be a set of $n$ points. Pinchasi proved the statement below with $100$ replaced by $O(\log \log n)$, and an example of Alon shows that $100$ cannot be replaced by a very small constant. Conlon and Lim gave a negative answer for a variant with pseudolines.

Problem. Must some line $\ell$ through two or more points of $X$ split the remaining points so that the counts on its two sides differ by at most $100$?

Source: Y. S. Kupitz, Extremal Problems in Combinatorial Geometry, Aarhus Lecture Notes 53 (1979), in a stronger form; known as the Kupitz–Perles conjecture, see R. Pinchasi, Lines with many points on both sides, Discrete Comput. Geom. 30 (2003), Problem 7.1, and N. Alon in Kleitman and combinatorics: a celebration (2002), Problem 364. Listed as Problem 75 in B. Green, 100 open problems (version of January 2026).

Imported from people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf.

Classification

Primary: CO — Combinatorics
Secondary: MG
Keywords: balanced lines, discrete geometry, halving lines, lines through point sets
Literature checked: Oct. 26, 2026 by clemens-admin

References

@book{kupitz1979,
  author = {Kupitz, Y. S.},
  title = {Extremal Problems in Combinatorial Geometry},
  series = {Lecture Notes Series},
  volume = {53},
  publisher = {Aarhus Universitet, Matematisk Institut},
  year = {1979}
}

@article{pinchasi2003,
  author = {Pinchasi, Rom},
  title = {Lines with many points on both sides},
  journal = {Discrete \& Computational Geometry},
  volume = {30},
  number = {3},
  pages = {415--435},
  year = {2003},
  doi = {10.1007/s00454-003-2826-8}
}

@article{alon2002problems,
  title = {Research problems, in {K}leitman and combinatorics: a celebration},
  note = {Problem 364, posed by N. Alon},
  journal = {Discrete Mathematics},
  volume = {257},
  number = {2-3},
  pages = {599--624},
  year = {2002},
  doi = {10.1016/S0012-365X(02)00619-2}
}

@article{conlon2025lim,
  author = {Conlon, David and Lim, Jeck},
  title = {Everywhere unbalanced configurations},
  journal = {Advances in Mathematics},
  volume = {480},
  pages = {110445},
  year = {2025},
  doi = {10.1016/j.aim.2025.110445},
  eprint = {2308.02466},
  archivePrefix = {arXiv}
}

@misc{kalai2010,
  author = {Kalai, Gil},
  title = {A discrepancy problem for planar configurations},
  howpublished = {\url{https://gilkalai.wordpress.com/2010/02/03/a-discrepency-problem-for-planar-configurations/}},
  year = {2010}
}

@misc{green100open,
  author = {Green, Ben},
  title = {100 open problems},
  howpublished = {\url{https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf}},
  note = {Problem 75; version of January 2026, most recent update December 2025},
  year = {2026}
}

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00953, "The Kupitz–Perles balanced line conjecture", clopen.solutions.