On a conjecture of Karasev

Seunghun Lee, Kang Min YooComput. Geom 2018 · DOI

TL;DR

This paper investigates a conjecture by Karasev concerning the partitioning of colored lines in a plane. While the general conjecture is disproven, the authors prove a special case for lines in "convex position," demonstrating that such sets can always be partitioned into colorful subsets whose formed triangles share a common point. This work contributes to the understanding of geometric combinatorial problems with applications in discrete geometry.

What Problem Does This Paper Address?

The paper tackles a problem rooted in discrete geometry, specifically related to Tverberg's Theorem and its generalizations. Tverberg's Theorem deals with partitioning sets of points in $R^d$ into subsets whose convex hulls intersect. The paper focuses on a "dual" version involving lines in a plane and their intersections, and a "colored" version where elements are assigned colors.

Karasev conjectured that for any set of $3k$ lines in general position in the plane, if these lines are partitioned into 3 color classes of equal size $k$, then it's possible to partition these lines into $k$ "colorful" 3-subsets (each containing one line of each color) such that all the triangles formed by these subsets share a common point. The paper first establishes that this general conjecture is false, providing a counterexample. However, it then investigates a specific scenario: when the lines are in "convex position." Lines in convex position have a specific geometric arrangement where the complement of their union has a connected component whose boundary intersects every line. The paper aims to prove Karasev's conjecture for this restricted, but still significant, case.

Methods

The paper employs a combination of geometric and combinatorial techniques. A key strategy is to reduce the main theorem (Theorem 1.6) to a dual version concerning points on a circle (Theorem 2.1). This reduction involves a clever mapping from lines in convex position to points on a circle, preserving the colorfulness and intersection properties.

The proof of Theorem 2.1, the core of the paper, relies heavily on observations and propositions that build towards the final result. These include:

  • Geometric Joins: The concept of a "geometric join" of point sets is used, particularly its starshaped property in the plane. This is leveraged to show that if all colorful 3-subsets are "unbounding" (their convex hulls don't contain the circle's center), a specific point on the circle can be identified.
  • Combinatorial Characterization: Proposition 2.4 provides a combinatorial tool to find a specific type of colorful partition when two different partitions of the same set exist. This is crucial for constructing the desired partitions.
  • Circular Ordering and Middle Points: The notion of "middle points" of 3-sets of points on a circle is introduced. The paper then focuses on finding partitions where these middle points are "consecutive" (lie within a semicircle and form a contiguous arc).
  • Induction and Case Analysis: The proofs, particularly for Lemma 3.1 and the claim within it, involve detailed case analysis based on the geometric arrangement of points and the coloring of subsets. This often leads to contradictions or constructive arguments.
  • Reduction to a Simpler Problem: The proof of Lemma 3.1 involves identifying a specific subset of points ($Q$) and showing that it can be re-partitioned into a bounding and two unbounding 3-sets with desired properties, which then allows for the construction of the overall partition.

Datasets

Not discussed in the paper. The paper deals with abstract geometric configurations rather than empirical data.

Key Insights and Ideas

  • Disproving the General Conjecture: The paper demonstrates that Karasev's conjecture, in its most general form for lines in general position, is false. This is a significant result, highlighting the importance of specific geometric constraints.
  • The Power of "Convex Position": The paper proves that the "convex position" condition is sufficient to salvage Karasev's conjecture. This suggests that geometric structure plays a critical role in the validity of such combinatorial statements.
  • Circle-Based Reduction: The elegant reduction of the line problem to a point-on-a-circle problem is a key methodological insight. This transformation simplifies the geometric constraints and allows for the application of combinatorial arguments related to circular orderings.
  • "Middle Points" as a Crucial Concept: The introduction and analysis of "middle points" of 3-sets on a circle are central to the proof. The condition that these middle points must be "consecutive" is a strong constraint that guides the construction of the desired partition.
  • The Interplay of Bounding and Unbounding Sets: The distinction and interaction between "bounding" and "unbounding" 3-sets on a circle are critical. The proofs often involve showing how to transform or construct partitions that manage these types of sets effectively.

Key Results

  • Disproof of Karasev's Conjecture: The paper provides a counterexample (Example 1.5) showing that Karasev's conjecture is false for lines in general position.
  • Proof of Karasev's Conjecture for Lines in Convex Position: The main result (Theorem 1.6) states that for any set of $3k$ lines in "convex position" in the plane, partitioned into 3 color classes of size $k$, there exists a partition into $k$ colorful 3-subsets such that all the triangles formed by these subsets have a common point.
  • Dual Theorem for Points on a Circle: A key intermediate result (Theorem 2.1) proves that for $3k$ points on a circle without antipodal pairs, partitioned into 3 color classes of size $k$, there exists a partition into $k$ disjoint colorful 3-sets whose middle points are consecutive.

Limitations and Future Work

  • Generalization to Higher Dimensions: The paper explores the possibility of generalizing Theorem 1.6 to hyperplanes in $R^d$. Section 4.1 presents an example in 3D with 4 color classes, where colorful partitions of hyperplanes result in simplices with empty intersections, suggesting that a direct generalization of Theorem 1.6 for hyperplanes in $R^d$ might be impossible.
  • Necessity of Convex Position: Section 4.2 investigates whether the "convex position" condition is strictly necessary. An example of 6 lines not in convex position is given, which still allows for colorful partitions with intersecting triangles for every possible coloring. This indicates that the conclusion of Theorem 1.6 might hold for a broader class of line arrangements than just those in convex position.
  • Optimal Bounds: While the paper proves the existence of partitions, it doesn't necessarily focus on finding the smallest possible number of lines or points required for such configurations, which is a common theme in related Tverberg-type problems.
  • Further Exploration of Line Arrangements: The paper opens avenues for further research into characterizing line arrangements for which Karasev's conjecture holds, beyond the "convex position" constraint.

Summary updated

BibTeX
@article{lee2018conjecture,
  author = {Seunghun Lee and Kang Min Yoo},
  title = {{On a conjecture of Karasev}},
  journal = {Comput. Geom.},
  year = {2018},
  doi = {10.1016/j.comgeo.2018.06.003},
}
Figure