Pith. sign in

REVIEW 2 major objections 4 minor 26 references

Coloring Hasse diagrams and disjointness graphs of curves

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For every positive integer $r$ and every sufficiently large $n$, some family of $n$ curves has a disjointness graph with girth at least $r$ and chromatic number at least $\Omega((1/r)\log n)$.

desk verdict Genuinely better lower-bound construction for cover graphs and curve disjointness graphs, but the proof of Theorem 4(ii) has a quantitative gap in the cycle-counting estimate that, as written, leaves the main theorem unproven. read the letter →

arxiv 1908.08250 v1 pith:VXOXEUIA submitted 2019-08-22 math.CO

Janos Pach , Istvan Tomon This is my paper · ORCID
classification math.CO MSC 05C1505C6205C8006A07
keywords disjointnessgraphsofcurvesstringHassediagramscoverchromaticnumbergirthuniquelygeneratedposetsrandomlayered
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper proves an existence result at the crossing of poset and geometric graph theory: for every positive integer $r$ and every sufficiently large $n$, some family of $n$ curves in the plane has a disjointness graph with no cycle shorter than $r$ and with chromatic number at least $\Omega((1/r)\log n)$. In such a graph, two curves are adjacent precisely when they do not intersect, so a proper coloring is an assignment in which disjoint curves receive different colors; the theorem says this may require logarithmically many colors even though the graph contains no short cycles. The proof is carried out in the language of partial orders, where the same graph is a cover graph (the graph of covering relations), and a known characterization translates it into a family of grounded curves. Along the way the paper improves the earlier lower bound for chromatic numbers of cover graphs and proves that, for uniquely generated posets, the new bound is the best possible.

What carries the argument

The load-bearing construction is a random layered graph. Vertices are divided into consecutive blocks $A_1,\ldots,A_k$ of size $m$, and for $i<j$ each $x\in A_i$ and $y\in A_j$ is joined independently with probability $2^{j-i}/m$, so edges become more likely as the layers are farther apart. The proof shows that, with positive probability, the graph simultaneously has no independent set larger than $7m$, fewer than $N/3$ bad pairs, and fewer than $N/3$ cycles of length below $r$; deleting one vertex from each bad pair and one from each short cycle leaves the desired $n$-vertex graph $G'$. The poset is then defined by comparability along monotone paths (paths whose vertices appear in increasing order) in $G'$, and the absence of bad pairs makes it uniquely generated with cover graph exactly $G'$. The matching upper bound rests on the observation that in a uniquely generated poset the set of predecessors of any vertex induces a tree, so a greedy linear-extension coloring cannot use color $k$ unless that tree has at least $2^{k-1}$ vertices.

What would settle it

For a fixed $r$, run the proof's random layered construction for a large $n$, delete the bad pairs and short cycles, and compute the chromatic number of the surviving cover graph; an infinite sequence on which it stayed below a constant times $\log n$ would disprove Theorem 3. A second check targets the transfer: exhibit a triangle-free cover graph that is not realizable as the disjointness graph of grounded curves, since Theorem 2 is derived through that equivalence.

Watch

Extended reading notes

Core claim

The central assertion is Theorem 3: for every positive integer $r$ and every sufficiently large $n$, there is an $n$-element poset whose cover graph has girth at least $r$ and chromatic number at least $\Omega((1/r)\log n)$. Theorem 1, quoted from earlier work, states that a triangle-free graph is a cover graph of a poset if and only if it is the disjointness graph of a family of grounded curves, so the poset statement yields the geometric Theorem 2 directly. The proof builds a random layered graph with vertex set split into intervals, deletes vertices to remove short cycles and 'bad pairs' (pairs joined by two edge-disjoint increasing paths), and shows the surviving graph is the cover graph of a uniquely generated poset with the required properties. Finally, a greedy linear-extension coloring shows that every uniquely generated poset on $n$ vertices has cover graph chromatic number at most $\lfloor \log_2 n\rfloor+1$, making the lower bound tight within this class.

Load-bearing premise

The curve conclusion depends on a quoted equivalence, Theorem 1, that a triangle-free graph is a cover graph of a poset exactly when it is the disjointness graph of some family of grounded curves; this equivalence is cited from earlier work and not reproved, so a hidden counterexample in either direction would break the transfer from the poset theorem to the geometric theorem.

Editorial extensions

If this is right

  • For every fixed $r$, one can build $n$-curve families whose disjointness graph has girth at least $r$ and chromatic number at least $c_r\log n$, so forbidding short cycles does not cap the color demand of curve disjointness graphs.
  • The construction cannot be reproduced with $x$-monotone curves: for those, the chromatic number of the corresponding cover graph is bounded by a constant, so the curves must bend or change direction.
  • Within uniquely generated posets the bound is tight: every such poset on $n$ vertices has cover graph chromatic number at most $\lfloor \log_2 n\rfloor+1$, while some require $\Omega((1/r)\log n)$ colors.
  • Because the transfer theorem applies to grounded curves, the resulting curve family can be assumed to lie in the nonnegative half-plane and touch the $y$-axis at one endpoint.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper, the delete-one-vertex-per-bad-pair framework looks reusable for other classes of graphs built from monotone paths, since the proof uses only the layered probability structure and the deletion step rather than special properties of partial orders.
  • The paper does not rule out a stronger lower bound for general cover graphs; its upper bound applies only to uniquely generated posets, so any improvement would have to exploit non-unique generation.
  • A computational instantiation of the construction for a small $r$ (say $r=4$) could turn the existential proof into explicit examples or reveal where the probabilistic constants need enlarging; the paper gives no such explicit family.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper studies the chromatic number of Hasse diagrams (cover graphs of posets) and disjointness graphs of curves. Its main result, Theorem 2, asserts that for every fixed r and all sufficiently large n there is a family of n curves whose disjointness graph has girth at least r and chromatic number Omega((1/r) log n). The proof proceeds through the equivalent poset statement, Theorem 3: for every fixed r there is an n-element poset whose cover graph has girth at least r and chromatic number Omega((1/r) log n). Theorem 3 is derived from a probabilistic construction of a random layered graph with three properties: no large independent set, few bad pairs, and few short cycles; deleting vertices then yields a graph of girth at least r and high chromatic number. In addition, Theorem 4 gives an upper bound of floor(log_2 n)+1 for the chromatic number of cover graphs of uniquely generated posets, and a matching lower bound construction. The geometric application uses a known characterization (Theorem 1, cited from [16,24]) that triangle-free cover graphs are exactly disjointness graphs of grounded curves.

Significance. If the proof is repaired, this is a solid contribution. It improves Bollobás's old Omega(log n/log log n) bound for chromatic numbers of Hasse diagrams with large girth to Omega((1/r) log n), and it isolates uniquely generated posets as a class for which this bound is tight. The greedy upper bound in Theorem 4(i) is clean and correct, and the probabilistic layered-graph idea is natural and potentially reusable. The transfer from posets to curves via Theorem 1 is legitimate and clearly attributed, so the geometric corollary rests on sound external groundwork rather than an unproved internal equivalence. The main weaknesses are confined to the quantitative estimates inside the proof of Theorem 4(ii), which contain repairable but load-bearing errors.

major comments (2)
  1. [Section 2, proof of Theorem 4(ii), condition 3] The estimate for E(Y), the expected number of short cycles, is not valid as written. With p = n^{-(r-1)/r} and N = 3n, the l-th term in the sum is N^l p^l = 3^l n^{l/r}. In particular, the l = r-1 term is 3^{r-1} n^{(r-1)/r}, which is larger than the displayed bound r N^{(r-1)/r} = r 3^{1-1/r} n^{(r-1)/r} for every r >= 2. Therefore the chain E(Y) < ... < r N^{(r-1)/r} < N/9 is false. Moreover, with the missing factor 3^{r-1} restored, the desired inequality E(Y) < N/9 at the stated threshold n >= 2^{10r} fails for r >= 7. Since the theorem only asserts existence for sufficiently large n, the gap is repairable by taking n large enough that 3^{r-1} n^{(r-1)/r} = o(n) (roughly n^{1/r} > C 3^r), but the proof as printed does not establish condition 3.
  2. [Section 2, proof of Theorem 4(ii), condition 2] The Markov bound for the number of bad pairs X is also incorrect. The displayed per-pair probability is bounded by k^2 2^{4k}/m^2 < 1/(9n). Since there are N(N-1)/2 unordered pairs and n = N/3, this gives E(X) < (N^2/2)/(9n) = N/6, not the claimed N/9. Consequently Markov's inequality yields P(X > N/3) < 1/2, not < 1/3, so the union bound over the events A, B, C does not guarantee existence of the graph G. This is a local arithmetic gap: for sufficiently large N the bound can be strengthened to < 1/(9N), giving E(X) < N/18 and P(X > N/3) < 1/6, so the condition is recoverable with adjusted constants.
minor comments (4)
  1. [Abstract and Theorem 2] The abstract says 'for every positive integer r and n', while Theorem 2 states 'for every sufficiently large n'; likewise the abstract says 'girth r' while the theorem proves 'girth at least r'. These should be harmonized.
  2. [Section 2, proof of Theorem 4(ii)] In the path-counting argument, '2k m^{l-1}' and '(2k m^{l-1})(2k m^{l'-1})' should read '2^k m^{l-1}' and '(2^k m^{l-1})(2^k m^{l'-1})'. Also, the sequence 'v0, v2, ..., vl' should be 'v0, v1, ..., vl'.
  3. [Theorem 3 and Theorem 4(ii)] Theorem 4(ii) is stated only for r > 3, while Theorem 3 is for every positive r. The r = 3 case of Theorem 3 follows from the r = 4 case (or from prior work on triangle-free constructions), but this should be stated explicitly instead of leaving the reader to infer it.
  4. [Throughout] There is a typo in 'We omit floors an ceilings for easier readability'; it should be 'and'. This is cosmetic but worth fixing in a revision.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular dependence; the poset construction is self-contained and the cited string-cover equivalence is external.

full rationale

The paper's derivation chain is: Theorem 4(ii) is proved by an explicit random graph construction on N vertices; Theorem 3 then follows immediately as a consequence, and Theorem 2 is obtained by transferring the poset result to curves via Theorem 1, quoted from external references [16] and [24]. No equation in the paper defines the target quantity in terms of itself, no fitted parameter is relabeled as a prediction, and the self-citations in the introduction are contextual background rather than load-bearing premises. Theorem 1 is an external equivalence theorem whose stated assumptions do not include the conclusion of Theorem 2, so using it to translate between posets and grounded curves does not make the geometric statement circular. The proof of Theorem 4(ii) contains apparent quantifier and constant issues in the estimates for E(X) and E(Y) relative to the stated threshold n >= 2^{10r}; those are correctness concerns and repairable by choosing n sufficiently large, not circularity. Overall, the central claim has independent mathematical content and no circular step was found.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

No empirically fitted parameters appear. The constants N=3n, k=(log_2 N)/(10r), m=N/k, and edge probabilities p_ij=2^{j-i}/m are explicit functions of n and r chosen inside the proof. No new physical or geometric primitives are introduced; the paper relies on standard probabilistic inequalities and on the cited curve-cover equivalence.

assumptions (2)
  • domain assumption Theorem 1: a triangle-free graph is a cover graph of a poset if and only if it is the disjointness graph of a family of grounded curves (Middendorf-Pfeiffer [16], Sinden [24]).
    Used in Section 1 to transfer Theorem 3 to Theorem 2; not proved in this paper.
  • standard math Probabilistic method: if three events each have probability greater than 2/3, their intersection is nonempty; Markov's inequality and union bounds are valid.
    Used throughout Section 2 to show that a random layered graph satisfies the three required conditions simultaneously.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Coloring Hasse diagrams and disjointness graphs of curves." pith.science (2026). https://pith.science/paper/VXOXEUIA

@misc{pith2026190808250,
  author       = {Pith},
  title        = {Pith review of: Coloring Hasse diagrams and disjointness graphs of curves},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VXOXEUIA}},
  note         = {Machine review of arXiv:1908.08250}
}
abstract

Given a family of curves $\mathcal{C}$ in the plane, its disjointness graph is the graph whose vertices correspond to the elements of $\mathcal{C}$, and two vertices are joined by an edge if and only if the corresponding sets are disjoint. We prove that for every positive integer $r$ and $n$, there exists a family of $n$ curves whose disjointness graph has girth $r$ and chromatic number $\Omega(\frac{1}{r}\log n)$. In the process we slightly improve Bollob\'as's old result on Hasse diagrams and show that our improved bound is best possible for uniquely generated partial orders.

Figures

Figures reproduced from arXiv: 1908.08250 by the authors.

Figure 1
Figure 1. A family of grounded curves and its disjointness graph. The first sign that the above concepts are intimately related was the following simple fact discovered by Golumbic, Rotem, Urrutia [9], and Lov´asz [15]: Every comparability graph is the disjointness graph of a collection of curves in the plane. A partial converse of this statement was established in [8]. A useful characterization of cover graphs in terms of st… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

  1. [1]

    Asplund, E., Gr¨ unbaum, B.: On a coloring problem. Math. S cand. 8, 181–188 (1960) Coloring Hasse diagrams and disjointness graphs of curves 7

    work page 1960

  2. [2]

    P roceedings of the Na- tional Academy of Sciences of the United States of America 45(11), 1607–1620 (1959)

    Benzer, S.: On the topology of the genetic fine structure. P roceedings of the Na- tional Academy of Sciences of the United States of America 45(11), 1607–1620 (1959)

    work page 1959

  3. [3]

    Algebra Universalis 7, 313–314 (1977)

    Bollob´ as, B.: Colouring lattices. Algebra Universalis 7, 313–314 (1977)

    work page 1977

  4. [4]

    Circle graphs are quadratically $\chi$-bounded

    Davies, J., McCarty, R.: Circle graphs are quadratically χ -bounded. arXiv:1905.11578

    work page Pith review arXiv 1905

  5. [5]

    E.: Intersection graphs of curves in the plane

    Ehrlich, G., Even, S., Tarjan, R. E.: Intersection graphs of curves in the plane. J. Combin. Theory, Ser. B 21(1), 8–20 (1976)

    work page 1976

  6. [6]

    Canadian J

    Erd˝ os, P.: Graph theory and probability. Canadian J. Mat h. 11, 34–38 (1959)

    work page 1959

  7. [7]

    Erd˝ os, P., Hajnal, A.: Some remarks on set theory. IX. Com binatorial problems in measure theory and set theory. Michigan Math. J. 11(2), 107–127 (1964)

    work page 1964

  8. [8]

    Fox, J., Pach, J.: String graphs and incomparability grap hs. Adv. Math. 230(3), 1381–1401 (2012)

    work page 2012

Show all 26 references
  1. [9]

    Discrete Math

    Golumbic, M., Rotem, D., Urrutia, J., Comparability grap hs and intersection graphs. Discrete Math. 43, 37–46 (1983)

    1983

  2. [10]

    L.: Problem 1, Open Problems at 5th Hungarian C olloquium on Com- binatorics (1976)

    Graham, R. L.: Problem 1, Open Problems at 5th Hungarian C olloquium on Com- binatorics (1976). in: Combinatorics, Vol. II (A. Hajnal an d V. T. S´ os, eds.), North- Holland, Amsterdam, 1195 (1978)

    1976

  3. [11]

    Discrete Math

    Gy´ arf´ as, A.: On the chromatic number of multiple inter val graphs and overlap graphs. Discrete Math. 55, 161–166 (1985)

    1985

  4. [12]

    Dis- crete Math 163(1-3), 299–305 (1997)

    Kostochka, A., Kratochv ´ ıl, J.: Covering and coloring p olygon-circle graphs. Dis- crete Math 163(1-3), 299–305 (1997)

    1997

  5. [13]

    Kratochv ´ ıl, J.: String graphs. I. The number of critical nonstring graphs is infinite. J. Combin. Theory Ser. B 52(1), 53–66 (1991)

    1991

  6. [14]

    Order 8(1), 41–48 (1991)

    Kˇ r ´ ıˇ z, I., Neˇ setˇ ril, J.: Chromatic number of Hasse diagrams, eyebrows and dimen- sion. Order 8(1), 41–48 (1991)

    1991

  7. [15]

    in: Selected Topics in Grap h Theory, vol

    Lov´ asz, L.: Perfect graphs. in: Selected Topics in Grap h Theory, vol. 2, Academic Press, London, 55–87 (1983)

    1983

  8. [16]

    in: Graph theory and combinatorics (Marseil le-Luminy, 1990), Dis- crete Math

    Middendorf, M., Pfeiffer, F.: Weakly transitive orienta tions, Hasse diagrams and string graphs. in: Graph theory and combinatorics (Marseil le-Luminy, 1990), Dis- crete Math. 111(1-3), 393–400 (1993)

    1993

  9. [17]

    arXiv:1802.0 9969

    M¨ utze, T., Walczak, B., Wiechert, V.: Realization of sh ift graphs as disjointness graphs of 1-intersecting curves in the plane. arXiv:1802.0 9969

  10. [18]

    Neˇ setˇ ril, J., R¨ odl, V.: A short proof of the existence of highly chromatic hyper- graphs without short cycles. J. Combin. Theory Ser. B 27(2), 225–227 (1979)

    1979

  11. [19]

    in: 33rd Interna- tional Symposium on Computational Geometry, SoCG 2017 , 77, Leibniz Zentrum, Dagstuhl, 59:1–59:15 (2017)

    Pach, J., Tardos, G., T´ oth, G.: Disjointness graphs of s egments. in: 33rd Interna- tional Symposium on Computational Geometry, SoCG 2017 , 77, Leibniz Zentrum, Dagstuhl, 59:1–59:15 (2017)

    2017

  12. [20]

    in: 35th International Symposium on Computational Geometry, S oCG 2019 , 129 Leibniz Zentrum, Dagstuhl, 54:1–54:17 (2019)

    Pach, J., Tomon, I.: On the chromatic number of disjointn ess graphs of curves. in: 35th International Symposium on Computational Geometry, S oCG 2019 , 129 Leibniz Zentrum, Dagstuhl, 54:1–54:17 (2019)

    2019

  13. [21]

    Discrete Comput

    Pach J., T¨ or˝ ocsik, J.: Some geometric applications ofDilworth’s theorem. Discrete Comput. Geom. 12(1), 1–7 (1994)

    1994

  14. [22]

    T., Walczak, B.:Triangle-free intersection graphs of line segments wit h large chromatic number

    Pawlik, A., Kozik, J., Krawczyk, T., Laso´ n, M., Micek, P , Trotter, W. T., Walczak, B.:Triangle-free intersection graphs of line segments wit h large chromatic number. J. Combin. Theory Ser. B 105, 6–10 (2014)

    2014

  15. [23]

    https://arxiv.org/abs/1312.1559

    Rok, A., Walczak, B.: Outerstring graphs are χ -bounded. https://arxiv.org/abs/1312.1559

    arXiv

  16. [24]

    W.: Topology of thin film RC-circuits

    Sinden, F. W.: Topology of thin film RC-circuits. Bell Sys tem Technical Journal 45, 1639–1662 (1966) 8 J´ anos Pach and Istv´ an Tomon

    1966

  17. [25]

    T´ oth, G.: Note on geometric graphs. J. Combin. Theory Se r. A 89(1), 126–132 (2000)

    2000

  18. [26]

    G.: Le¸ cons sur la r´ esolution alg´ ebrique des ´equations

    Vogt, H. G.: Le¸ cons sur la r´ esolution alg´ ebrique des ´equations. Nony, p. 91 (1895)

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.