Source-linked AI summary
Large Planar Point Sets Contain 4 Collinear Points or Almost 7-Cliques, and Related Results
Bhaswar B. Bhattacharya, Sandip Das, Sk Samim Islam, Aashirwad Mohapatra, Saumya Sen
TL;DR
The big-line-big-clique problem asks when large planar point sets must contain many collinear or pairwise visible points, and the (7, 4) case was a next open case. This paper proves visibility-graph containment for fixed graphs of chromatic number at most five and for six-chromatic graphs with a color-critical edge, including a seven-point set with at least 20 visible pairs. Its results come within one visibility edge of that open case.
Problem
The big-line-big-clique conjecture asks whether sufficiently large planar point sets contain either ℓ collinear points or k pairwise visible points; the (7, 4) case remained open.
Source: §1 · pp. 1, 3Method
The proofs order points by generic projection and use interval-density bounds and a sliding-interval comparison, with vertex-removal stability for six-chromatic targets.
Source: §1.1 · p. 4Results
At least 20 of 21 pairs among seven points are visible, and every fixed H with χ(H) ≤ 5 or χ(H) = 6 and a color-critical edge occurs in sufficiently large point sets without four collinear points.
Source: §1 · pp. 2–3Takeaways & Limitations
The seven-point result comes within one visibility edge of the next open (7, 4) case of the big-line-big-clique conjecture.
Source: §1 · p. 3The present stability input and sliding-interval argument do not bridge the leading-coefficient gap for the (7, 4) case, which likely requires additional geometric input or a stronger comparison.
Source: §5 · p. 10
Abstract
from arXiv · showhide
We prove that every sufficiently large finite planar point set contains either four collinear points or seven points with at most one non-visible pair. More generally, we show that for every fixed graph $H$ with chromatic number at most five, or with chromatic number six and a color-critical edge, the visibility graph of every sufficiently large finite planar point set with no four collinear points contains a copy of $H$. These results extend the recent breakthrough of Bonnet (2026), guaranteeing six pairwise visible points, and come within one visibility edge of the next open case of the big-line-big-clique conjecture.
1 Introduction
For sufficiently large planar point sets with no four collinear points, visibility graphs contain every fixed graph of chromatic number at most five, and every such six-chromatic graph with a color-critical edge. The results also guarantee seven points with at most one non-visible pair and outline the proof techniques and their scope.
1 Introduction
- Every fixed graph H with χ(H) ≤ 5, or with χ(H) = 6 and a color-critical edge, occurs in the visibility graph of every sufficiently large point set with no four collinear points.The theorems allow ordinary, not necessarily induced, copies.Source: §1 · p. 2
- The chromatic-number-at-most-five result is equivalent to finding complete balanced 5-partite graphs, or five disjoint point groups with all cross-group pairs visible.Visibility within each group is unrestricted.Source: §1 · p. 2
- Every sufficiently large planar point set with no four collinear points contains seven points such that at least 20 of their 21 pairs are visible.Source: §1 · p. 3
- For each fixed t, the results guarantee five pairwise visible points with at least t common visibility-graph neighbors; they also cover a six-chromatic example outside the complete 6-partite family.The common-neighbor conclusion follows from applying the theorem to K5 joined to an independent set of size t.Source: §1 · pp. 3–4
- Every 6-chromatic graph on at most ten vertices has a color-critical edge, while the question of covering all fixed 6-chromatic graphs remains open.K1,2,2,2,2,2 has eleven vertices and no color-critical edge.Source: §1 · p. 4
1.1 Overview of the Proofs and New Technical Ingredients
- The proof for chromatic number at most five uses projection order, an interval-density bound, and a sliding-interval comparison of visible and non-visible pairs.For six-chromatic targets, the outline combines interval coloring with vertex-removal stability to obtain a fixed deficit in visible-pair density.Source: §1.1 · pp. 4–5
- The sliding-interval comparison replaces Bonnet’s harmonic-potential argument and also simplifies the proof of a visible K6 while improving the resulting bound.Appendix A gives an improved explicit bound on the number of points needed to guarantee four collinear points or six pairwise visible points.Source: §1.1 · p. 5
1.2 AI Declaration
- GPT-6 Astra produced initial proofs of Theorems 1.1 and 1.3 through iterative exchanges; the authors revised the arguments and take responsibility for the content.The authors supplied additional details, examples, and contextual discussion.Source: §1.2 · p. 5
2 Preliminaries
The projection order makes every consecutive interval preserve its visibility relations within the full point set. With no four collinear points, every non-visible pair has a unique blocker.
2 Preliminaries
- A point set is ordered by distinct projections, and an interval consists of consecutive points in that order.Visibility in an interval agrees with visibility in the full point set.Source: §2 · p. 5
- Every non-visible pair has a unique blocker between its endpoints, and the two pairs formed with that blocker are visible.The line through the endpoints contains exactly those three points of the set.Source: §2 · p. 5
3 A Sliding Interval Comparison
The section compares visible and non-visible pairs across sliding intervals by mapping each blocked pair to a visible pair in one half of a larger interval. The map is injective under the no-four-collinear condition.
3 A Sliding Interval Comparison
- The total count of non-visible pairs over sliding intervals of length 2K is at most the total visible-pair count over intervals of length K.Counts include multiplicity: a pair is counted once for each interval containing both endpoints.Source: §3 · pp. 6–7
- A non-visible pair's unique blocker determines a visible subpair in the half of its length-2K interval containing the blocker.The construction maps the non-visible pair and its interval to that visible pair and half-interval.Source: §3 · p. 6
- The map is injective because the projection order and unique three-point lines allow the original pair and sliding interval to be recovered.If four collinear points are allowed, a visible subpair can belong to multiple blocked pairs on the same line, so this reconstruction may fail.Source: §3 · pp. 6–7
4 Proof of Theorem 1.1
For graphs with chromatic number at most five, the proof assumes an H-free visibility graph and bounds the density of visible pairs in long intervals. The sliding-interval comparison then forces the point set to have bounded size, contradicting its assumed size.
4 Proof of Theorem 1.1
- For every sufficiently long interval J (|J| ≥ MH), there are at most ρ|J|² visible pairs, with ρ = 3/8 + 1/120 < 2/5.Source: §4 · pp. 7–8
- The sliding-interval count makes the assumed density bound impossible for arbitrarily large point sets when ρ is strictly below 2/5.The counting argument's exact threshold is 2/5; under the strict bound, its resulting inequality bounds the size of the point set.Source: §4 · p. 7
- Every sufficiently large point set with no four collinear points contains four collinear points or a copy of each fixed graph H with chromatic number at most five.The proof assumes the visibility graph is H-free and uses a five-partite graph containing H to obtain an edge-density bound on long intervals.Source: §4 · pp. 7–8
5 Proof of Theorem 1.3
For a fixed six-chromatic graph with a color-critical edge, the proof combines interval coloring and graph stability to force a density deficit in long visibility intervals. The sliding-interval comparison then yields the theorem, while the argument identifies a barrier at K7.
5 Proof of Theorem 1.3
- A sufficiently large interval requires deleting a positive proportion of its vertices to make its visibility graph 5-colorable.The proof invokes the bound of 2310 points for a 5-colorable visibility graph of a set with no four collinear points.Source: §5 · p. 8
- Stability gives a fixed quadratic edge deficit below 2/5 N^2 for sufficiently large H-free graphs far from 5-colorable.The vertex-removal stability result relates edge counts to the number of vertex deletions needed for 5-colorability.Source: §5 · p. 9
- For a fixed six-chromatic H with a color-critical edge, sufficiently large H-free visibility graphs cannot arise from point sets with no four collinear points.The proof reaches a contradiction by combining an interval edge-density bound with the sliding-interval comparison.Source: §5 · pp. 9–10
- The proof's sliding-interval argument reaches a natural barrier at K7 because K7-freeness alone permits more edges than the 2/5 density threshold.The authors say resolving the (7,4) case likely requires additional geometric input or a stronger comparison.Source: §5 · p. 10
A Improved Bound for Six Visible Points
The appendix improves the numerical threshold for guaranteeing four collinear points or six pairwise visible points. It combines a sliding-interval argument with stability and coloring inputs, then further sharpens the bound using the exact empty-hexagon number.
A Improved Bound for Six Visible Points
- In a K6-free graph meeting the stated hypotheses, fewer than 3500ε|V(G)| vertices can be removed so the remaining graph is 5-colorable.This stability input is used in the bound improvement.Source: A Improved Bound for Six Visible Points · p. 12
- 2 × 10^13 points suffice to guarantee four collinear points or six pairwise visible points, improving Bonnet’s earlier bound.The argument combines the sliding-interval counting method with Bonnet’s stability and coloring inputs.Source: A Improved Bound for Six Visible Points · pp. 11–12
- Using H(6) = 30 yields the bound n ≤ 66,847,630,079 < 7×10^10; consequently, every finite planar point set with at least 7×10^10 points contains four collinear points or six pairwise visible points.A later arXiv preprint [5] shows 880 points suffice; determining the exact minimum remains open.Source: A Improved Bound for Six Visible Points · pp. 12–13
B Proof of Proposition 5.3
The proof uses stability to partition large H-free graphs into five nearly equal parts with few exceptional pairs. A color-critical edge then forces near-independent parts, enabling an embedding argument that contradicts the assumed lower bound on the five-coloring parameter.
Proof of Proposition 5.3
- Stability gives five nearly equal vertex parts with few missing cross-edges and few within-part edges.The proof invokes the partition formulation of the Erdős-Simonovits stability theorem [6, 20].Source: B Proof of Proposition 5.3 · p. 13
- For a color-critical edge, its endpoints share a color in a proper 5-coloring after the edge is removed, making it the sole within-class edge of H.The proof derives that each corresponding part, after removing its exceptional vertices, is independent.Source: B Proof of Proposition 5.3 · p. 14
- The embedding starts by mapping the color-critical edge to an edge within one part, then greedily maps remaining color classes to adjacent vertices in other parts.The embedding works outside the exceptional sets because those vertices have few nonneighbors in each other part.Source: B Proof of Proposition 5.3 · p. 14
- The five independent parts outside the exceptional vertices give a 5-coloring after deleting only o(|V(G_t)|) vertices, contradicting τ5(G_t) ≥ δ|V(G_t)|.This contradiction completes the proof of Proposition 5.3.Source: B Proof of Proposition 5.3 · p. 14