{"id":"e7c9f5bd-5acf-48c9-ab2b-761e7e97202f","arxiv_id":"2411.16465","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Steiner determines the maximum ratio between fractional chromatic number and Hall ratio as (log n)^(1-o(1)), and constructs graphs with bounded Hall ratio, arbitrarily large fractional chromatic number, and every subgraph containing an independent set touching a constant fraction of its edges.","lead":"This paper solves two open problems about how much larger the fractional chromatic number can be than a natural lower bound called the Hall ratio. The results show the gap can be almost as large as log n, and give graphs with bounded Hall ratio but very large fractional chromatic number that also satisfy a strong independent-set property.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The printed edge-probability rule in Construction 2.1 is inconsistent with the proofs of Lemma 2.2 and Claim 4.2; the intended rule (p=1/|B_i| for i>j) is load-bearing and must be corrected.","rationale":"The reader's weakest assumption correctly identifies the construction/proof mismatch. I checked that all later uses—Lemma 2.2's exponent, Claim 3.2's p_max=1/|B_{i-2^j}|, Claim 4.2's expectation formula—are consistent with p=1/(size of the smaller part), not with the literal text. Under the literal rule the key inequality in Lemma 2.2 reverses because for i= (1/2) sum_{i != j} t_i t_j / |B_i| still holds; for k=2 with t_1=t_2=1 it reverses, so the claimed O(k^{1-log k}) union bound is not attained. This settles whether the construction statement must be corrected to p=1/|B_i| for i>j.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Construction 2.1 states that for u in B_i and v in B_j with i>j the edge probability is 1/|B_j|, i.e. inversely proportional to the larger part. But Lemma 2.2's union bound uses the factor (1-1/|B_j|) for ij (inversely proportional to the smaller part). Claim 4.2(2) likewise computes E[|E(G[B_ell cup B_ell'])|] = |B_ell||B_ell'| * 1/|B_ell'| = |B_ell| for ell= (1/2) sum_{i != j} t_i t_j / |B_i| has the wrong direction, so the upper bound on P[chi_f <= k/(10 log k)] collapses. The same mismatch invalidates Claim 4.2(1)'s use of (1/|B_{i-1}|)^{3s/2} as a maximum edge probability, since the literal rule gives larger probabilities for edges between larger parts. Thus the stated construction is not the graph actually analyzed; the central lower bounds on chi_f rest entirely on the unprinted rule p=1/|B_i| for i>j. This is very likely a typo, and the internal evidence in Claim 4.2 identifies the intended rule, but as written the main theorems are not self-contained or verifiable from the stated construction.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies the ratio between the fractional chromatic number and the Hall ratio. The first main result, Theorem 1.3, constructs, for every sufficiently large n, an n-vertex graph with chi_f(G) >= log n / (C log log n) and rho(G) <= C(log log n)^2, yielding g(n) = Omega(log n / (log log n)^3) = (log n)^{1-o(1)} and thereby almost closing the gap left by Dvorak, Ossona de Mendez, and Wu between Omega(log log n) and O(log n). The second main result, Theorem 1.5, answers an open problem of Dvorak et al. by constructing graphs with rho(G) <= 4 + delta, chi_f(G) >= log log n / (50 log log log n), and the property that every subgraph H has an independent set touching at least |E(H)|/(4+delta) edges. The proofs use a family of unbalanced random graphs with nested parts B_i of decreasing size; Lemma 2.2 gives a general lower bound on chi_f, while Lemmas 3.1 and 4.1 establish the required Hall-ratio and weight-touching properties via probabilistic union bounds.","tokens_in":13044,"tokens_out":12615,"duration_ms":105094,"significance":"If the technical issue identified below is corrected, these results would substantially resolve two open problems in the area. The proofs are detailed and mostly self-contained, the constructions are clean, and no parameters are fitted to data. The paper also supplies the correct asymptotic order for g(n) up to a (log log n)^3 factor, which is a significant strengthening of the previous Omega(log log n) lower bound. The second theorem affirmatively solves Problem 1.4 of Dvorak et al. with an explicit constant 4 + delta, so the contribution is likely to be influential.","major_comments":[{"comment":"The stated edge-probability rule in Construction 2.1 is inconsistent with the proof of Lemma 2.2. Construction 2.1 says that for u in B_i and v in B_j with i > j the edge probability is 1/|B_j|, which is inversely proportional to the larger part. However, the proof of Lemma 2.2 uses the factor (1 - 1/|B_j|) for i < j, which corresponds to the probability 1/|B_j| for i < j, i.e. inversely proportional to the smaller part. Under the printed rule the exponent in the union bound would contain sum_{i= (1/2) sum_{i != j} t_i t_j / |B_i| would have the wrong direction. Since this inequality is the step that produces the factor exp(-2 log k sum t_i), the entire upper bound on P[chi_f(G) <= k/(10 log k)] collapses if Construction 2.1 is read literally. This is a load-bearing error: the lower bound on chi_f in Theorem 1.3 depends directly on Lemma 2.2.","section":"Section 2, Construction 2.1 and Lemma 2.2"},{"comment":"The same probability-rule mismatch affects the proof of Theorem 1.5. In Claim 4.2(2) the computation E[|E(G[B_ell cup B_ell'])|] = |B_ell| |B_ell'| * 1/|B_ell'| = |B_ell| for ell < ell' reveals that the intended rule is p = 1/|B_ell'|, i.e. inverse to the smaller part. Similarly, Claim 4.2(1) uses (1/|B_{i-1}|)^{3s/2} as an upper bound on the probability that a prescribed set of 3s/2 edges is present; this is only valid when every edge between B_r and B_s with r < s has probability at most 1/|B_s|. Under the literal statement of Construction 2.1, the probability between B_{i-2} and B_{i-1} would be 1/|B_{i-2}|, which is larger than 1/|B_{i-1}|. Thus both parts of Lemma 4.1, and hence Theorem 1.5, rely on the unprinted inverse-to-smaller-part rule rather than on the construction as written. The internal evidence in Claim 4.2(2) makes it very plausible that this is a typographical error, but as printed the main theorems are not verifiable from the stated construction.","section":"Section 4, Claim 4.2 and Theorem 1.5"}],"minor_comments":[{"comment":"After correcting the probability rule, it would be clearer to state it symmetrically: for every pair of parts B_i and B_j with i != j, include edges with probability 1/|B_{max(i,j)}|. This avoids the confusing distinction between i > j and i < j.","section":"Construction 2.1"},{"comment":"The expression 2j in the interval bounds such as i - 2j and i - 2j + 1 + 1 should be 2^j. As typeset, the interval notation is ambiguous and makes the proof harder to follow.","section":"Claim 3.2 and Lemma 3.1"},{"comment":"The part size |B_i| is written as n^{1-4i epsilon}, but the proof uses 4^{i-1} epsilon in several places. Please use an unambiguous display such as n^{1-4^i epsilon} or n^{1-4^{i-1} epsilon} throughout.","section":"Lemma 4.1 statement"},{"comment":"The bound O(k^{1-log k}) is correct, but since the proof uses log k > 1 for k >= 3, it may be worth stating this explicitly when passing to exp(-2 log k sum t_i).","section":"Proof of Lemma 2.2"}],"recommendation":"major_revision","confidential_remarks":"The central flaw is very likely a typo in Construction 2.1, and the intended rule is clearly recoverable from Claim 4.2(2). However, the issue is load-bearing because both main theorems depend on Lemma 2.2 and Lemma 4.1, whose probability estimates use the smaller-part rule. Once the construction is corrected, the proofs appear sound. I therefore recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know. First, the paper does what it claims: it proves g(n) = (log n)^(1-o(1)), essentially settling Problem 4 from Dvořák et al., and it gives a positive answer to their Problem 5 with Hall ratio at most 4+δ. Second, the paper as posted is not fully self-contained because of a typo in the definition of the random graph. The stated edge probability is 1/|B_j| when i>j; every proof uses 1/|B_i|. That distinction is load-bearing. Under the printed rule the union bound in Lemma 2.2 goes the wrong direction, and Claim 4.2's expected-edge calculation would be wrong. The internal evidence makes it clear the intended rule is p=1/|B_i| for i>j, so this is a fixable typo, not a broken argument. But an arXiv reader cannot verify the main theorems from the stated construction.\n\nWhat's genuinely new: the near-tight bound on g(n) and the resolution of Problem 5. The construction is a variant of the Janzer–Steiner–Sudakov random graph, and the analysis is careful. I checked the main probabilistic bounds. Lemmas 2.2, 3.1, and 4.1 check out under the intended rule; the union bounds are fine, and the degenerate-subgraph argument in Section 4 is sound. The paper is self-contained, gives credit to [6] and [8] appropriately, and does not fit any parameters to data.\n\nThe soft spot is the typo. It's not just cosmetic: the graph GB is defined differently from the graph the proofs work with. The fix is a one-line correction in Construction 2.1 (and perhaps a note in the proof of Lemma 2.2 that the rule is used for ij$) for $k=10$ and part sizes like $|B_i|=2^{10-i}$, and check whether some independent set with total weight at least $9\\log k$ appears with probability that fails to vanish as $k$ grows; such a failure would show that the union-bound step in Lemma 2.2 breaks under the written construction.","tokens_in":12449,"feed_emoji":"🎲","tokens_out":18632,"duration_ms":137608,"temperature":0.7,"pith_summary":"The paper proves that the ratio between the fractional chromatic number and the Hall ratio, both natural lower bounds on the chromatic number, can be as large as $(\\log n)^{1-o(1)}$ for $n$-vertex graphs. This nearly matches the easy upper bound $O(\\log n)$ and closes the exponential gap left by an earlier result that had shown only a $\\log\\log n$ lower bound. The same random-graph construction also answers a second question from that earlier paper: there are graphs with bounded Hall ratio and arbitrarily large fractional chromatic number in which every subgraph has an independent set touching a constant fraction of its edges. The arguments rest on a family of unbalanced random graphs with part sizes decreasing rapidly, analyzed through a sparse-subgraph condition that controls the Hall ratio.","feed_headline":"Fractional chromatic number beats Hall ratio by nearly log n","feed_subtitle":"A random graph construction closes the gap between two coloring invariants and solves a second open problem.","key_machinery":"The object that carries the argument is the random graph of Construction 2.1: pairwise disjoint independent parts $B_1,\\ldots,B_k$ with $|B_1| \\ge \\cdots \\ge |B_k|$, where each edge between a vertex of a higher-indexed part and one of a lower-indexed part is present with probability given by the reciprocal of the smaller part's size. Lemma 2.2 shows that whenever every part has size at least $k$, the fractional chromatic number of such a random graph is at least $k/(10\\log k)$ with high probability; the proof assigns weight $1/|B_i|$ to the vertices of $B_i$ and uses a union bound over independent sets whose total weight is at least $9\\log k$. For Theorem 1.3 the part sizes are chosen as $|B_i| = n/3^i$, so a sparse-subgraph condition (Claim 3.2) implies that every subgraph has an independent set of linear-in-$s$ size, giving the polylogarithmic Hall-ratio bound. For Theorem 1.5 the part sizes are $|B_i| = n^{1-4i\\varepsilon}$ with $\\varepsilon = 1/\\sqrt{\\log n}$, and two sparsity conditions (Claim 4.2) ensure both the constant Hall-ratio bound and the existence of a 4-color class in the 'front' of any subgraph that is large and touches a constant fraction of the subgraph's edges, which yields the degree-weighted independent set.","core_discovery":"The paper's first main theorem, Theorem 1.3, asserts that for every sufficiently large $n$ there is an $n$-vertex graph $G$ with fractional chromatic number at least $\\log n/(C\\log\\log n)$ and Hall ratio at most $C(\\log\\log n)^2$ for an absolute constant $C$, so the maximum ratio $g(n) = \\max_{|V(G)|=n} \\chi_f(G)/\\rho(G)$ is $\\Omega(\\log n/(\\log\\log n)^3)$, which is $(\\log n)^{1-o(1)}$. The second main theorem, Theorem 1.5, states that for every fixed $\\delta > 0$ and all sufficiently large $n$ there is an $n$-vertex graph with Hall ratio at most $4+\\delta$, fractional chromatic number at least $\\log\\log n/(50\\log\\log\\log n)$, and the stronger property that for every subgraph $H$ some independent set of the whole graph touches at least $|E(H)|/(4+\\delta)$ edges of $H$. This answers two questions posed in the earlier paper that introduced the Hall-ratio separation.","pith_inferences":["The near-logarithmic growth of $g(n)$ suggests that the true value of $g(n)$ may be $\\Theta(\\log n)$, with the extra $(\\log\\log n)^2$ factor an artifact of the union-bound analysis rather than the truth.","The flexibility in choosing part sizes suggests a general scheme for attacking the open problem of whether Hall ratio $2+\\varepsilon$ with arbitrarily large fractional chromatic number is possible: use part sizes that decay just fast enough to keep every short block sparse, while tuning the sparsity threshold independently of the block length.","The two constructions suggest a possible trade-off: graphs with constant Hall ratio may only force fractional chromatic number around $\\log\\log n$, while allowing polylogarithmic Hall ratio gives fractional chromatic number near $\\log n$; exploring intermediate regimes could refine the known relationship between these parameters.","The edge-touching independent set property in Theorem 1.5 is stronger than what was asked, so it may be useful for other problems in fractional graph theory where degree-weighted independent sets appear, such as coloring with local constraints."],"forward_implications":["The maximum possible ratio $g(n)$ between fractional chromatic number and Hall ratio is now known to within a $(\\log\\log n)^3$ factor, so the qualitative answer to Problem 4 of [6] is settled: the gap really grows almost as fast as $\\log n$.","Any theorem that aims to bound $\\chi_f(G)$ in terms of $\\rho(G)$ and the number of vertices must allow the bound to grow almost linearly in $\\log n$, so Hall ratio alone cannot be a strong quantitative control.","The second construction shows that even the degree functions of subgraphs, a natural class of dual weight functions, cannot approximate the fractional chromatic number better than a constant factor for the graphs in Theorem 1.5.","The same template of rapidly shrinking independent parts, combined with sparsity conditions on short blocks of parts, is a reusable recipe for simultaneously controlling Hall ratio and independent-set sizes.","Since isolated vertices can be added freely, the constructions can be padded to exactly $n$ vertices without changing any of the invariants, making the bounds valid for every sufficiently large $n$."],"supporting_citations":[{"why":"Poses the two follow-up problems solved here and supplies the previous bounds $\\Omega(\\log\\log n) \\le g(n) \\le O(\\log n)$ that Theorems 1.3 and 1.5 improve.","marker":"[6]"},{"why":"Introduces the unbalanced random graph construction and a special-case lemma that Lemma 2.2 generalizes to the full Construction 2.1.","marker":"[8]"},{"why":"Provides the equivalent dual LP and weight-function representation of the fractional chromatic number that Lemma 2.2 uses to convert a small $\\chi_f$ into the existence of a heavy independent set.","marker":"[11]"}],"fun_headline_variants":["Coloring gap pinned to log n: nearly tight bound","Fractional chromatic vs Hall ratio: log n gap","Near-tight coloring gap and a second problem solved","Graph ratio gap is log n to 1-o(1)","Two open coloring problems resolved for Hall ratio"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument hinges on reading Construction 2.1 as putting an edge between $B_i$ and $B_j$ (for $i>j$) with probability $1/|B_i|$ (the reciprocal of the smaller part) rather than the $1/|B_j|$ written in the text, because with the literal rule the union bound in Lemma 2.2 is not an upper bound.","fun_headline_variants_meta":{"raw":{"variants":["Coloring gap pinned to log n: nearly tight bound","Fractional chromatic vs Hall ratio: log n gap","Near-tight coloring gap and a second problem solved","Graph ratio gap is log n to 1-o(1)","Two open coloring problems resolved for Hall ratio"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00037,"raw_usage":{"total_tokens":2046,"prompt_tokens":1076,"completion_tokens":970,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":692,"completion_tokens_details":{"reasoning_tokens":893}},"tokens_in":692,"tokens_out":970,"duration_ms":8663,"temperature":1.0,"reasoning_tokens":893,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T13:08:20.104630+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Construction 2.1 with the literally stated rule $1/|B_j|$ (for $i>j$) for $k=10$ and part sizes like $|B_i|=2^{10-i}$, and check whether some independent set with total weight at least $9\\log k$ appears with probability that fails to vanish as $k$ grows; such a failure would show that the union-bound step in Lemma 2.2 breaks under the written construction.","supporting_citations":[{"cited_title":"Dvoˇ r´ ak, P","cited_arxiv_id":null,"evidence_quote":"Poses the two follow-up problems solved here and supplies the previous bounds $\\Omega(\\log\\log n) \\le g(n) \\le O(\\log n)$ that Theorems 1.3 and 1.5 improve."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the equivalent dual LP and weight-function representation of the fractional chromatic number that Lemma 2.2 uses to convert a small $\\chi_f$ into the existence of a heavy independent set."}],"review_version":1}