pith. sign in

arxiv: 2606.28157 · v1 · pith:YJIEKDKHnew · submitted 2026-06-26 · 🧮 math.CO

A unit-distance graph in the plane with independence ratio below 1/4

\'Akos D\'ucz , D\'aniel Varga This is my paper

Pith reviewed 2026-06-29 03:25 UTC · model grok-4.3

classification 🧮 math.CO
keywords unit-distance graphindependence ratiochromatic number of the planefractional chromatic numberErdős questiongeometric graphfinite graph construction
0
0 comments X

The pith

There exists a finite unit-distance graph in the plane with independence ratio strictly smaller than 1/4.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that augmenting an existing 27-vertex unit-distance graph with two additional vertices produces a finite graph whose largest independent set occupies strictly less than one quarter of the vertices. This directly settles an open question of Erdős by showing that independence ratios below 1/4 are attainable. The argument works by establishing that the geometric fractional chromatic number of the augmented graph exceeds 4, which forces the independence ratio below 1/4. The same bound implies that the fractional chromatic number of the plane is strictly larger than 4.

Core claim

By adding two carefully chosen vertices to the 27-vertex unit-distance graph of Matolcsi, Ruzsa, Varga, and Zsámboki, the authors obtain a larger unit-distance graph whose geometric fractional chromatic number is strictly larger than 4. Consequently the independence ratio of this graph is strictly less than 1/4. The proof can be made fully constructive, although the resulting graph has an enormous number of vertices.

What carries the argument

A two-vertex augmentation of the 27-vertex unit-distance graph that raises its geometric fractional chromatic number strictly above 4.

If this is right

  • The fractional chromatic number of the plane is strictly larger than 4.
  • Conjecture 1 of Matolcsi, Ruzsa, Varga, and Zsámboki is false.
  • Finite unit-distance graphs with independence ratio below 1/4 exist.
  • The independence ratio of some unit-distance graphs is strictly less than 1/4.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Iterating the same augmentation on the new graph might produce examples with still smaller independence ratios.
  • An explicit listing of the vertices would allow independent verification of the independence number by direct search.
  • The same augmentation idea may apply to other geometric graphs where fractional chromatic number bounds are sought.

Load-bearing premise

The two chosen vertices can be placed so that the augmented graph remains a unit-distance graph while its geometric fractional chromatic number exceeds 4.

What would settle it

A proof that the geometric fractional chromatic number of the augmented graph equals 4, or a direct computation showing its independence number is at least one quarter of its order.

Figures

Figures reproduced from arXiv: 2606.28157 by \'Akos D\'ucz, D\'aniel Varga.

Figure 1
Figure 1. Figure 1: Our extension of the G27 graph with vertices p and q. Here we present the pair of vertices p, q, which achieve our χgf bound when added to G27. If we let ω1 = 1/2 + i √ 3/2 and ω3 = 5/6 + i √ 11/6, we can define the Moser lattice as LMoser = {a + bω1 + cω3 + dω1ω3 : a, b, c, d ∈ Z}. The entire G27 graph is a subset of LMoser, and by [6], no graph in this lattice can achieve χgf (G) > 4. Vertex p can be rep… view at source ↗
Figure 2
Figure 2. Figure 2: Congruences containing the vertices p and q. The blue intervals both have length 1, the green intervals both have length 2, and the red intervals all have the same length. 5. Characterizing the optimal geometric fractional colorings of G27 The rest of this note explains how the vertices p and q were found. We now characterize the optimal geometric fractional colorings of G27, or more specifically we enumer… view at source ↗
read the original abstract

We prove that there exists a finite unit-distance graph in the plane with independence ratio strictly smaller than 1/4, answering a question of Erd\H{o}s. Our proof closely follows the framework of Matolcsi, Ruzsa, Varga, and Zs\'amboki, based on the geometric fractional chromatic number, but adds a carefully chosen two-vertex augmentation that pushes their 27-vertex construction from geometric fractional chromatic number $4$ to a value strictly larger than 4. This disproves their Conjecture 1, and implies that the fractional chromatic number of the plane is strictly larger than 4. The proof can be made fully constructive, but the resulting finite graph has an enormous number of vertices.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The manuscript proves that there exists a finite unit-distance graph in the plane with independence ratio strictly smaller than 1/4. It follows the framework of Matolcsi, Ruzsa, Varga, and Zsámboki by starting from their 27-vertex unit-distance graph (with geometric fractional chromatic number exactly 4) and adding a carefully chosen two-vertex augmentation whose positions and incident edges are selected so that the resulting graph has geometric fractional chromatic number strictly larger than 4. This disproves Conjecture 1 of the prior work and implies that the fractional chromatic number of the plane is strictly larger than 4. The construction is finite but enormous; the proof is claimed to be fully constructive.

Significance. If the augmentation step is correct, the result resolves an open question of Erdős on the independence ratio of the plane and provides the first explicit finite unit-distance graph with independence ratio below 1/4. It strengthens the known lower bound on the chromatic number of the plane via the geometric fractional chromatic number. The explicit (though large) construction is a strength, as is the direct reduction from the independence-ratio claim to the strict inequality χ_g(G') > 4.

major comments (2)
  1. [Abstract] Abstract (paragraph on framework and augmentation): The two-vertex augmentation is asserted to raise the geometric fractional chromatic number from exactly 4 to strictly greater than 4, but the manuscript provides no explicit coordinates for the added vertices, no list of their unit-distance edges, and no derivation showing that every geometric fractional coloring must have weight >4. This step is load-bearing for the independence-ratio claim, as the ratio is obtained directly from 1/χ_g(G').
  2. [Framework description] Framework description: The argument relies on the prior 27-vertex graph having χ_g exactly 4 and claims the augmentation is independent of that value, yet no verification is given that the added constraints eliminate all weight-4 fractional colorings (for instance, no linear-programming formulation or explicit forbidden coloring is exhibited).

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and for recognizing the significance of the result. We address the two major comments point by point below.

read point-by-point responses

  1. Referee: [Abstract] Abstract (paragraph on framework and augmentation): The two-vertex augmentation is asserted to raise the geometric fractional chromatic number from exactly 4 to strictly greater than 4, but the manuscript provides no explicit coordinates for the added vertices, no list of their unit-distance edges, and no derivation showing that every geometric fractional coloring must have weight >4. This step is load-bearing for the independence-ratio claim, as the ratio is obtained directly from 1/χ_g(G').

    Authors: The positions of the two added vertices are defined geometrically as the unique (up to isometry) points satisfying a finite system of unit-distance equations with a small number of vertices from the base 27-vertex graph; these equations are stated explicitly in Section 3. The new edges are precisely the unit-distance pairs involving the new vertices and the base graph. The proof that no geometric fractional coloring of total weight 4 survives is by exhaustive case analysis on the possible weight-4 colorings of the base graph (which are completely classified by the earlier work) and showing that each such coloring is incompatible with at least one new edge. Because the final graph is enormous we do not list every edge numerically, but the construction is fully algorithmic and therefore constructive. We will add a short paragraph in the revision that spells out the case analysis in more detail. revision: partial

  2. Referee: [Framework description] Framework description: The argument relies on the prior 27-vertex graph having χ_g exactly 4 and claims the augmentation is independent of that value, yet no verification is given that the added constraints eliminate all weight-4 fractional colorings (for instance, no linear-programming formulation or explicit forbidden coloring is exhibited).

    Authors: The augmentation is independent of the precise value 4 in the sense that the same geometric placement works for any base graph whose weight-4 colorings are known; here we use only the classification already proved for the 27-vertex graph. The verification that all weight-4 colorings are eliminated is combinatorial: each possible weight-4 assignment on the base vertices is shown to force a contradiction with one of the new unit-distance constraints. This is a direct geometric argument rather than an LP formulation; an LP would be possible but is unnecessary for the proof. We are happy to include a schematic diagram of the forbidden configurations in a revised version if the referee finds it helpful. revision: no

Circularity Check

0 steps flagged

No significant circularity; new augmentation supplies independent content.

full rationale

The derivation begins from the 27-vertex unit-distance graph of the cited prior work (which establishes χ_g = 4) and then explicitly augments it by two new vertices and edges. The paper states that this augmentation is chosen so that every geometric fractional coloring must exceed weight 4, yielding the strict inequality χ_g(G') > 4 and therefore independence ratio < 1/4. This step is presented as a concrete, verifiable construction rather than a redefinition, a fitted parameter renamed as a prediction, or a result forced solely by the prior self-citation. The base framework is cited, but the load-bearing claim (the augmentation's effect) is external to the prior paper's fitted values and is not reduced to it by the paper's own equations. No self-definitional, ansatz-smuggling, or renaming patterns appear.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no explicit free parameters, axioms, or invented entities; the construction is described only at the level of augmentation to a prior framework.

pith-pipeline@v0.9.1-grok · 5652 in / 1143 out tokens · 44056 ms · 2026-06-29T03:25:59.782511+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 2 linked inside Pith

  1. [1]

    Ambrus, A

    G. Ambrus, A. Csiszárik, M. Matolcsi, D. Varga, and P. Zsámboki,The density of planar sets avoiding unit distances, Math. Program.207(2024), 303–327

    2024

  2. [2]

    Bellitto, A

    T. Bellitto, A. Pêcher, and A. Sédillot,On the density of sets of the Euclidean plane avoiding distance1, Discrete Math. Theor. Comput. Sci.23(2021), no. 1

    2021

  3. [3]

    D. W. Cranston and L. Rabern,The fractional chromatic number of the plane, Combinatorica 37(2017), no. 5, 837–861

    2017

  4. [4]

    H. T. Croft,Incidence incidents, Eureka30(1967), 22–26

    1967

  5. [5]

    A. D. N. J. de Grey,The chromatic number of the plane is at least 5, Geombinatorics28 (2018), no. 1, 18–31. arXiv:1804.02385

    Pith/arXiv arXiv 2018

  6. [6]

    Dúcz,A note on geometric colorings of the Moser lattice, arXiv:2606.12325, 2026

    Á. Dúcz,A note on geometric colorings of the Moser lattice, arXiv:2606.12325, 2026

    Pith/arXiv arXiv 2026

  7. [7]

    A unit-distance graph in the plane with independence ratio below1/4

    Á. Dúcz and D. Varga,Supplementary material for “A unit-distance graph in the plane with independence ratio below1/4”, available athttps://users.renyi.hu/~akos/ep1070/

  8. [8]

    Erdős,Problems and results in combinatorial geometry, in:Discrete Geometry and Con- vexity(New York, 1982), Ann

    P. Erdős,Problems and results in combinatorial geometry, in:Discrete Geometry and Con- vexity(New York, 1982), Ann. New York Acad. Sci., vol. 440, New York Acad. Sci., New York, 1985, pp. 1–11

    1982

  9. [9]

    Erdős,Some combinatorial and metric problems in geometry, in:Intuitive Geometry (Siófok, 1985), Colloq

    P. Erdős,Some combinatorial and metric problems in geometry, in:Intuitive Geometry (Siófok, 1985), Colloq. Math. Soc. János Bolyai, vol. 48, North-Holland, Amsterdam, 1987, pp. 167–177

    1985

  10. [10]

    Fisher and D

    D. Fisher and D. Ullman,The fractional chromatic number of the plane, Geombinatorics2 (1992), no. 1, 8–12

    1992

  11. [11]

    Fukuda,cddlib Reference Manual, version 094m, 2021

    K. Fukuda,cddlib Reference Manual, version 094m, 2021

    2021

  12. [12]

    Fukuda and A

    K. Fukuda and A. Prodon,Double description method revisited, in: M. Deza, R. Euler, and I. Manoussakis, editors,Combinatorics and Computer Science, Lecture Notes in Computer Science, vol. 1120, Springer, Berlin, 1996, pp. 91–111

    1996

  13. [13]

    brain-teasers

    M. Gardner,A new collection of “brain-teasers”, Sci. Amer.206(1960), no. 4, 172–180

    1960

  14. [14]

    Hadwiger,Überdeckung des Euklidischen Raumes durch kongruente Mengen, Portugaliae Math.4(1945), 238–242

    H. Hadwiger,Überdeckung des Euklidischen Raumes durch kongruente Mengen, Portugaliae Math.4(1945), 238–242

    1945

  15. [15]

    Hochberg and P

    R. Hochberg and P. O’Donnell,A large independent set in the unit distance graph, Geombi- natorics2(1993), no. 4, 83–84

    1993

  16. [16]

    S. L. Mahan,The fractional coloring number of the plane, Master’s thesis, University of Colorado Denver, 1995

    1995

  17. [17]

    Matolcsi, I

    M. Matolcsi, I. Z. Ruzsa, D. Varga, and P. Zsámboki,The fractional chromatic number of the plane is at least4, arXiv:2311.10069, 2023

    arXiv 2023

  18. [18]

    Moser and W

    L. Moser and W. Moser,Solution to problem 10, Canad. Math. Bull.4(1961), 187–189

    1961

  19. [19]

    Parts, comment onPolymath16, seventeenth thread: Declaring victory, Short, Fat Matri- ces, September 21, 2022

    J. Parts, comment onPolymath16, seventeenth thread: Declaring victory, Short, Fat Matri- ces, September 21, 2022. Available athttps://dustingmixon.wordpress.com/2021/02/01/ polymath16-seventeenth-thread-declaring-victory/#comment-37575

    2022

  20. [20]

    E. R. Scheinerman and D. H. Ullman,Fractional Graph Theory: A Rational Approach to the Theory of Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, New York, 1997. A UNIT-DISTANCE GRAPH IN THE PLANE WITH INDEPENDENCE RATIO BELOW 1/411

    1997

  21. [21]

    Soifer,The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators, Springer, New York, 2009

    A. Soifer,The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators, Springer, New York, 2009

    2009