{"id":"93696694-d9af-432c-beea-cabbab543d58","arxiv_id":"1908.08250","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For every girth r, there are n curves whose disjointness graph has girth at least r and chromatic number at least a constant times (1/r) log n, improving Bollobás's bound and matching it for uniquely generated posets.","lead":"Given any number of curves in the plane, this paper builds a set of n curves whose disjointness graph has no short cycles yet needs many colors. It improves a long-standing lower bound from log n over log log n to log n and proves the new bound is optimal for a large class of partial orders.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proof of Theorem 4(ii) has a quantifier/constant gap: the stated n≥2^{10r} does not yield the claimed bounds on E(Y) and on bad pairs; a much larger n0(r) is needed.","rationale":"The reader's weakest assumption was the external geometric characterization in Theorem 1. That is indeed standard, and I do not dispute it. The more immediate load-bearing issue is in the proof of the combinatorial half: several displayed inequalities in Theorem 4(ii) are not justified by the stated assumption n≥2^{10r}, and one line mixes 1/(9n) with 1/(9N). The probabilistic construction itself is sound: for each fixed r one can choose n so large that all three events A,B,C have failure probability below 1/3, and then the deletion argument and the uniquely generated poset argument go through. Thus the main claim is very likely correct, but the proof needs a corrected threshold and a consistent set of constants before it can be regarded as complete. This does not warrant rejection; it warrants a conditional acceptance with a request to fix the constant/quantifier details.","tokens_in":6386,"tokens_out":34451,"duration_ms":327659,"concrete_test":"Fix r=10 and set n=2^{10r}, N=3n. Using the paper's p=n^{-(r-1)/r}, compute the upper bound sum_{l=3}^{r-1} N^l p^l and compare it with N/9; it exceeds N/9, so the proof fails at its stated threshold. Then repeat with n=(9r3^r)^r and verify that this sum is below N/9, and that the corrected bad-pair bound k^2 2^{4k}/m^2 < 1/(9N) makes Markov's inequality give failure probability <1/3. This distinguishes a purely quantitative typo from a real flaw in the construction.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In the proof of Theorem 4(ii), the authors assume n≥2^{10r}, set N=3n and p=n^{-(r-1)/r}, then claim E(Y)<rN^{(r-1)/r}<N/9 for the expected number of cycles of length <r. With N=3n, the terms satisfy N^l p^l = 3^l n^{l/r}, so the sum is bounded by r3^{r-1}n^{(r-1)/r}; the inequality r3^{r-1}n^{(r-1)/r}<N/9 is equivalent to n^{1/r}>3^r r, which fails at n=2^{10r} for r≥7. The text appears to use an N-based p or to drop a 3^r factor. There is a similar inconsistency in the bad-pair count: the displayed bound is k^2 2^{4k}/m^2 < 1/(9n), but the next line uses 1/(9N) in the expectation. Since 1/(9n)=1/(3N), using the displayed bound with at most N^2/2 pairs gives E(X)<N/6, so Markov yields P(X>N/3)<1/2, not <1/3; the union bound over A,B,C then does not guarantee existence. These are repairable by taking n large enough depending on r, and the construction is not invalid, but the proof as written does not establish the theorem under its stated threshold.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":6681,"tokens_out":25349,"duration_ms":239709,"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":[{"comment":"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.","section":"Section 2, proof of Theorem 4(ii), condition 3"},{"comment":"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.","section":"Section 2, proof of Theorem 4(ii), condition 2"}],"minor_comments":[{"comment":"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.","section":"Abstract and Theorem 2"},{"comment":"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'.","section":"Section 2, proof of Theorem 4(ii)"},{"comment":"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.","section":"Theorem 3 and Theorem 4(ii)"},{"comment":"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.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The two errors in the proof of Theorem 4(ii) are arithmetic and appear to be local; the construction is sound in spirit and the theorem is very likely correct after choosing N large enough depending on r. I recommend asking the authors to rewrite the probabilistic estimates with correct factors and to state an explicit or clearly implicit threshold for 'sufficiently large n'. The paper is a short note, the results are worthwhile, and the credits to prior work are appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things worth knowing up front. The upper bound for uniquely generated posets, Theorem 4(i), is clean and correct: the greedy coloring argument with the T(v) trees is standard and works. The lower-bound construction in Theorem 4(ii) has a real gap: the estimate on the expected number of short cycles does not hold as written.\n\nWhat is genuinely new is the random layered graph with edge probabilities p_{ij}=2^{j-i}/m, followed by deleting bad pairs and short cycles. If the proof can be repaired, this improves Bollobás's Ω(log n / log log n) to Ω((1/r) log n), and the transfer to curve disjointness graphs via the quoted grounded-curve equivalence is a solid step. The matching upper bound for uniquely generated posets is also new and plausibly tight.\n\nThe soft spot is the cycle count. After setting p=n^{-(r-1)/r}, the proof claims ∑_{l=3}^{r-1} N^l p^l < r N^{(r-1)/r}. But N^l p^l = 3^l n^{l/r}, so the last term alone is 3^{r-1} n^{(r-1)/r}, which exceeds r N^{(r-1)/r} by a factor exponential in r. At the stated threshold n≥2^{10r}, the inequality fails for r≥7. Consequently, condition 3 (few short cycles) is not established, and the union bound over the three events does not go through. The bad-pair line has a minor typo—the bound should presumably be 1/(9N) rather than 1/(9n)—and with that reading the expectation works. But the cycle gap is not a typo; the calculation is off by a large factor.\n\nThe construction itself may be salvageable; the graph is sparse enough that a sharper count, or a larger n0(r), could give E(Y)<N/9. But the proof as written does not deliver the theorem.\n\nThis is a short paper from two strong authors, aimed at extremal graph theorists and geometric graph theorists. The upper bound and the construction idea are worth knowing, but the main theorem is unproven in this version. I would send it to a serious referee and expect the referee to ask for a corrected cycle estimate before acceptance.","headline":"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.","tokens_in":7198,"tokens_out":18642,"would_cite":false,"duration_ms":152222,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C62","05C80","06A07"],"pacs":[],"model":"deepseek-v4-flash","headline":"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)$.","keywords":["disjointness graphs of curves","string graphs","Hasse diagrams","cover graphs","chromatic number","girth","uniquely generated posets","random layered graphs"],"falsifier":"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.","tokens_in":6190,"feed_emoji":"📐","tokens_out":17909,"duration_ms":209351,"temperature":0.7,"pith_summary":"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.","feed_headline":"Curves with no short cycles can force logarithmically many colors","feed_subtitle":"Random layered cover graphs realize n-curve disjointness graphs with girth r and chromatic number about (log n)/r.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"This supplies one half of Theorem 1, connecting cover graphs of posets to disjointness graphs of grounded curves.","marker":"[16]"},{"why":"This supplies the other half of the same equivalence, completing the bridge from posets to curves.","marker":"[24]"},{"why":"This gives the earlier lower bound for chromatic numbers of cover graphs with large girth, which Theorem 3 improves.","marker":"[3]"},{"why":"This is the previous triangle-free construction of curve disjointness graphs with high chromatic number, which the present paper extends to arbitrary prescribed girth.","marker":"[19]"}],"fun_headline_variants":["Curves with high girth force logarithmic color counts","Tight log bound for coloring high-girth cover graphs","Girth-r curve graphs: chromatic number ~ log n over r","High-girth posets: cover graphs need Ω((log n)/r) colors"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Curves with high girth force logarithmic color counts","Tight log bound for coloring high-girth cover graphs","Girth-r curve graphs: chromatic number ~ log n over r","High-girth posets: cover graphs need Ω((log n)/r) colors"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001515,"raw_usage":{"total_tokens":6029,"prompt_tokens":857,"completion_tokens":5172,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":473,"completion_tokens_details":{"reasoning_tokens":5098}},"tokens_in":473,"tokens_out":5172,"duration_ms":495042,"temperature":1.0,"reasoning_tokens":5098,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:48:21.848264+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"in: Graph theory and combinatorics (Marseil le-Luminy, 1990), Dis- crete Math","cited_arxiv_id":null,"evidence_quote":"This supplies one half of Theorem 1, connecting cover graphs of posets to disjointness graphs of grounded curves."},{"cited_title":"W.: Topology of thin film RC-circuits","cited_arxiv_id":null,"evidence_quote":"This supplies the other half of the same equivalence, completing the bridge from posets to curves."},{"cited_title":"Algebra Universalis 7, 313–314 (1977)","cited_arxiv_id":null,"evidence_quote":"This gives the earlier lower bound for chromatic numbers of cover graphs with large girth, which Theorem 3 improves."},{"cited_title":"in: 33rd Interna- tional Symposium on Computational Geometry, SoCG 2017 , 77, Leibniz Zentrum, Dagstuhl, 59:1–59:15 (2017)","cited_arxiv_id":null,"evidence_quote":"This is the previous triangle-free construction of curve disjointness graphs with high chromatic number, which the present paper extends to arbitrary prescribed girth."}],"review_version":1}