CS Paper Radar

Large Finite Point Sets Have 4 Collinear Points or a 6-Clique

Édouard Bonnet

cs.DM math.CO ·submitted 2026-08-19 21:51 UTC · v1
theory

Abstract

We prove that every finite point set of size at least $10^{11055931}$ has four collinear points or six points that pairwise see each other. This resolves the first open case of the big-line-big-clique conjecture of Kára, Pór, and Wood.

Comment
7 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Large Planar Point Sets Contain 4 Collinear Points or Almost 7-Cliques, and Related Results

cs.CG math.CO ·2026-09-22 ·Bhaswar B. Bhattacharya, Sandip Das, Sk Samim Islam, Aashirwad Mohapatra, Saumya Sen
theory similarity 0.81
Abstract · 14 pages, 1 figure

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.

0.19

Clique Number of Tournaments II

cs.DM math.CO ·2026-09-07 ·Guillaume Aubian, Samuel Coulomb
theory similarity 0.59
Abstract

The directed clique number $\vecω(T)$ of a tournament $T$ is the minimum, over all orderings of the vertices of $T$, of the clique number of the graph whose edges are the arcs that point backward with respect to the ordering. In this paper, we prove that, for every integer $k \geq 3$, deciding whether $\vecω(T) \leq k$ is NP-complete. This answers a question of Nguyen, Scott, and Seymour, and contrasts with the classical undirected setting, where deciding whether $ω(G) \leq k$ is polynomial-time solvable for every fixed integer $k$. On the other hand, we give a polynomial-time algorithm distinguishing tournaments with $\vecω(T) \leq 2$ from those with $\vecω(T) > 100$. We also study the tournament analogue of the Gyárfás--Sumner conjecture. We construct new $\vecχ$-bounding tournaments and thereby prove a conjecture of Aboulker, Aubian, Charbit, and Lopes stating that every class of tournaments with bounded twin-width is $\vecχ$-bounded. We then exhibit new tournaments that are not $\vecχ$-bounding, disproving another conjecture of Aboulker, Aubian, Charbit, and Lopes, as well as two conjectures of Kim. Finally, we present infinite families of 3-$\vecω$-critical and 4-$\vecω$-critical tournaments.

0.06

Almost Linear Universal Point Sets for Planar Graphs

cs.CG math.CO ·2026-09-10 ·Taylor Gordon
theorycode/data similarity 0.58
Abstract · 12 pages, 2 figures. Lean formalization of the earlier construction: https://github.com/taylorgordon20/math/tree/main/213-superpatterns

A point set is universal for planar graphs on $n$ vertices if every such graph has a straight-line drawing without crossings whose vertices belong to the set. We construct universal point sets of size $n^{1+o(1)}$, improving the previous quadratic upper bound. Our construction uses the reduction of Bannister, Cheng, Devanny, and Eppstein from universal point sets to superpatterns for $213$-avoiding permutations. We represent these permutations by ordered rooted forests and construct a small family of intervals containing every such forest. The result follows from a straightforward bound on the size of the family of intervals. GPT-6 Astra assisted in developing the construction and proof.

0.37

Symmetric, rational and infinitely many $(23_4)$ configurations, and the end of the existence problem for geometric $(n_4)$ configurations

cs.CG math.COcs.DM ·2026-10-08 ·Wenhao Lu
publishedtheory similarity 0.57
Abstract · To be presented at the 2027 Joint Mathematics Meetings, Chicago (AMS Contributed Paper Session on Combinatorics, I, January 12, 2027)

A geometric $(n_4)$ configuration is a set of $n$ points and $n$ lines in the real projective plane such that every point lies on exactly four of the lines and every line contains exactly four of the points. The question of which $n$ admit such a configuration was posed by Grünbaum in 2000, and successive work of Bokowski, Grünbaum, Schewe, Pilaud and Cuntz settled every case but $n=23$. We settle this last case by bounding the symmetry of such configurations and classifying the most symmetric ones exactly. We prove that for every prime $n\equiv3\pmod4$ the group of projective symmetries of a geometric $(n_4)$ configuration has order at most four, explaining why symmetric constructions failed at $n=23$, and the same argument bounds the symmetry of $(n_5)$ configurations for primes $n\not\equiv1\pmod5$. Reducing the Klein four-group case to 4021 bilinear polynomial systems and solving all of them exactly with Gröbner bases, we show that exactly two $(23_4)$ configurations reach this bound up to projective equivalence and that there are no others even over $\mathbb{C}$. Both are self-polar; the first has integer coordinates and the second is defined over $\mathbb{Q}(\sqrt{17})$ but not over $\mathbb{Q}$. Consequently geometric $(n_4)$ configurations exist if and only if $n\ge18$ and $n\ne19$. The same classification recovers Cuntz's $(22_4)$ and $(26_4)$ configurations and finds three new combinatorial types at $n=22$ and $94$ at $n=26$. Among self-polar $(23_4)$ configurations with a single involution we find $50$ more, defined over number fields of degree at most $7$. Four of them deform in one-parameter families, and computing three of these exactly, one birational to the modular curve $X_1(11)$, we prove that there are infinitely many geometric $(23_4)$ configurations, among them infinitely many with rational coordinates that are self-polar and have no projective symmetry.

0.35

Larger Crossing Families

cs.CG math.CO ·2026-10-28 ·Joachim Orthaber, Patrick Schnider
similarity 0.57
Abstract

We give the first explicit constant for crossing families of linear size by showing that every set of $n$ points in general position in the plane contains a crossing family of size approximately $\frac{n}{79}$. We further identify some conditions where there are even larger crossing families. The first such condition forbids the existence of a large different pattern, namely non-convex 4-clusters: We show that every point set contains either a large non-convex 4-cluster or a large crossing family. The second condition is the existence of many crossings: We give a bound for the size of a crossing family in terms of the number of crossings of the complete geometric graph drawn on the point set.

0.23

Non-simple Arrangements of Lines and Pseudolines with Many Triangles

cs.CG math.CO ·2026-11-02 ·Roman Parpalak, Denis Utkin
code/data similarity 0.56
Abstract · 72 pages, 19 figures, 8 tables. Code, enumeration outputs and certificates: https://github.com/parpalak/nonsimple-arrangements

We study affine arrangements of an even number $n$ of lines and pseudolines with many triangles. For simple ones, Blanc's bound limits the number of triangular faces to $\lfloor n(n-5/2)/3\rfloor$. Adapting the Bartholdi-Blanc-Loisel doubling to the even case, we construct an infinite series of arrangements of $n=6\cdot2^t+2$ ($8,14,26,50,\ldots$) straight lines with two triple points and $(n(n-5/2)+1)/3$ triangles, one more than the simple bound allows. We obtain exhaustive enumerations of triangle-maximal pseudoline arrangements, simple or not, for even $n\le12$. For $n=6,8,10,12,14$ the maximum number of triangles, for both lines and pseudolines, is $7,15,25,38,54$; for $n=8,12,14$ every optimal arrangement has multiple points. All optimal arrangements for even $n\le12$ are realizable by straight lines, except two arrangements of 10 pseudolines, which are not stretchable. For the odd value $n=11$, no arrangement with $33$ triangles exists even with multiple points. We also obtain even arrangements by adding a line to odd ones. For $n\equiv2\pmod 6$ this again gives one triangle more than the simple bound, in pseudolines up to $n=44$ and in straight lines for $n=20$ and $n=32$. Doubling these pseudoline arrangements gives members of the series $18\cdot2^t+2$ and $30\cdot2^t+2$ with the same excess, up to $n=146$ and $n=242$, respectively; those with $n=38$ and $n=74$ are realizable by straight lines. These results lead us to conjecture that an arrangement of an even number $n$ of pseudolines has at most $\lfloor n(n-2)/3\rfloor-\lfloor n/6\rfloor$ triangles.

0.34

New lower bounds for kissing numbers in dimensions 32-35 and 37-39

cs.DM math.MGcs.ITmath.CO ·2026-10-22 ·Qihong Lin
code/data similarity 0.54
Abstract · 8 pages. Certificates and verification programs: https://github.com/QH-Lin/kissing-number-32 (doi:10.5281/zenodo.23527725) and https://githu…

We show that the kissing numbers in dimensions 32, 33, 34, 35, 37, 38 and 39 are at least 352320, 370240, 390980, 415308, 499816, 605322 and 768916, improving the previous bounds 347584, 364736, 384836, 409676, 498024, 591900 and 763668. Except in dimension 38, the configurations are those of Edel, Rains and Sloane with new binary constant-weight codes of weight 8 and minimum distance 8 in the middle layer; each additional word adds 128 points. In dimension 38 we add 6855 antipodal pairs of vectors of the second shell of the Leech lattice to the empty equator of Kravatskiy's 591612-point configuration, where 144 pairs were known; this is an independent set problem in a regular graph of degree 11178 on 8386560 vertices. The codes and lines were found by local search, and all configurations were checked pair by pair in exact integer arithmetic.

0.40

The k-Clique hypothesis is dead, for good

cs.DS cs.CC ·2026-11-06 ·Virginia Vassilevska Williams, Or Zamir
highly cited similarity 0.54
Abstract

We present an algorithm that solves the $k$-Clique problem for any large enough $k$ and any $n$-vertex graph in $n^{\left(\fracω{3}-c\right)k}$ time, where $ω\geq 2$ is the matrix multiplication exponent and $c>0$ is a positive constant independent of both $ω$ and $k$. This refutes the long-standing $k$-Clique conjecture, regardless of the value of the matrix multiplication constant, even if $ω=2$. In fact, our algorithm solves the more general problem of counting weighted $k$-Cliques.

0.42