REVIEW 2 major objections 4 minor 11 references
Fractional chromatic number vs. Hall ratio
T0 review · 2 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read This paper proves that the ratio of fractional chromatic number to Hall ratio can be as large as (log n)^{1-o(1)} for n-vertex graphs, nearly matching the trivial upper bound, and also settles a second open problem about degree-weighted…
desk verdict Real results with a fixable typo: the stated random graph construction does not match the graph analyzed, but the intended rule is clear and the proofs are sound once corrected. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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$.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (2)
- [Section 2, Construction 2.1 and Lemma 2.2] 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<j} t_i t_j / |B_i| instead of sum_{i<j} t_i t_j / |B_j|, and the displayed inequality S >= (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 4, Claim 4.2 and Theorem 1.5] 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.
minor comments (4)
- [Construction 2.1] 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.
- [Claim 3.2 and Lemma 3.1] 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.
- [Lemma 4.1 statement] 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.
- [Proof of Lemma 2.2] 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).
Circularity Check
No significant circularity: the derivation is a self-contained probabilistic construction with lemmas proven in the paper; the edge-probability typo in Construction 2.1 is a correctness concern, not circularity.
full rationale
The paper's central claims are derived from scratch. Lemma 2.2 proves a lower bound on the fractional chromatic number of the random graph GB by choosing an explicit vertex weight w(v)=1/|B_i| and union-bounding the probability of a large-weight independent set; the fractional chromatic number is then bounded via the LP dual representation (M). Lemma 3.1 and Claim 4.2 prove Hall-ratio and sparsity properties by direct union-bound arguments over the random graph model. No parameter is fitted to the target quantity and no prediction is merely a renamed input: the Hall ratio bound and the independent-set edge-touching property are proved separately from the construction. The paper does cite prior work [8] for a special case of the construction, but the footnote at Lemma 2.2 explicitly says the earlier proof method does not transfer and the needed lemma is proven in full generality in the paper. The use of [8] for the idea of rapidly decreasing part sizes in Section 4 is not load-bearing in a circular way, because the probabilistic estimates are carried out here, not imported as black-box results. The only notable issue is that the printed edge-probability rule in Construction 2.1 (1/|B_j| for i>j) is inconsistent with the computations in Lemma 2.2 and Claim 4.2, which use the smaller-part rule 1/|B_i| for i>j. This affects correctness as written, but it is a typo/consistency error rather than circular reasoning: the argument does not assume the conclusion it is trying to prove, and the intended rule is identifiable from the proof's own expected-edge calculations. Therefore the paper is not circular.
Assumptions & free parameters
assumptions (4)
- standard math Linear programming duality between the set-cover and fractional chromatic number formulations.
- standard math Probabilistic method and union bound over random graph events.
- standard math Standard bound α(F) ≥ |V(F)|^2 / (2|E(F)| + |V(F)|) for any graph F.
- standard math 2-degeneracy implies 3-colorability, used to bound independence number of certain induced subgraphs.
Cite this review
Pith. "Pith review of Fractional chromatic number vs. Hall ratio." pith.science (2026). https://pith.science/paper/4ZN4GEDS
@misc{pith2026241116465,
author = {Pith},
title = {Pith review of: Fractional chromatic number vs. Hall ratio},
year = {2026},
howpublished = {\url{https://pith.science/paper/4ZN4GEDS}},
note = {Machine review of arXiv:2411.16465}
}
abstract
Given a graph $G$, its Hall ratio $\rho(G)=\max_{H\subseteq G}\frac{|V(H)|}{\alpha(H)}$ forms a natural lower bound on its fractional chromatic number $\chi_f(G)$. A recent line of research studied the fundamental question of whether $\chi_f(G)$ can be bounded in terms of a (linear) function of $\rho(G)$. In a breakthrough-result, Dvo\v{r}\'{a}k, Ossona de Mendez and Wu gave a strong negative answer by proving the existence of graphs with bounded Hall ratio and arbitrarily large fractional chromatic number. In this paper, we solve two natural follow-up problems that were raised by Dvo\v{r}\'{a}k et al. The first problem concerns determining the growth of $g(n)$, defined as the maximum ratio $\frac{\chi_f(G)}{\rho(G)}$ among all $n$-vertex graphs. Dvo\v{r}\'{a}k et al. obtained the bounds $\Omega(\log\log n) \le g(n)\le O(\log n)$, leaving an exponential gap between the lower and upper bound. We almost fully resolve this problem by proving that the truth is close to the upper bound, i.e., $g(n)=(\log n)^{1-o(1)}$. The second problem posed by Dvo\v{r}\'{a}k et al. asks for the existence of graphs with bounded Hall ratio, arbitrarily large fractional chromatic number and such that every subgraph contains an independent set that touches a constant fraction of its edges. We affirmatively solve this second problem by showing that such graphs indeed exist.
Reference graph
Works this paper leans on
-
[6]
Z. Dvoˇ r´ ak, P. O. de Mendez, and H. W u. 1-subdivisions, t he fractional chromatic number and the Hall ratio. Combinatorica, 40:759–774, 2020
work page 2020
- [8]
-
[1]
J. B´ ar´ any. A short proof of Kneser’s conjecture. Journal of Combinatorial Theory, Series A , 25(3):325–326, 1978
work page 1978
-
[2]
J. B. Barnett. The fractional chromatic number and the Hall ratio . PhD thesis, Auburn University, 2016
work page 2016
-
[3]
A. Blumenthal, B. Lidick´ y, R. R. Martin, S. Norin, F. Pfe nder, and J. Volec. Counterexamples to a conjecture of Harris on Hall ratio. SIAM Journal on Discrete Mathematics , 36(3):1678– 1686, 2022
work page 2022
-
[4]
M. Cropper, A. Gy´ arf´ as, and J. Lehel. Hall ratio of the M ycielski graphs. Discrete mathe- matics, 306(16):1988–1990, 2006
work page 1988
-
[5]
A. Daneshgar, A. J. Hilton, and P. D. Johnson Jr. Relation s among the fractional chromatic, choice, Hall, and Hall-condition numbers of simple graphs. Discrete Mathematics , 241(1- 3):189–199, 2001
work page 2001
-
[7]
D. G. Harris. Some results on chromatic number as a functi on of triangle count. SIAM Journal on Discrete Mathematics , 33(1):546–563, 2019
work page 2019
Show all 11 references
-
[9]
P. D. Johnson Jr. The fractional chromatic number, the Ha ll ratio, and the lexicographic product. Discrete mathematics , 309(14):4746–4749, 2009
2009
-
[10]
Lov´ asz
L. Lov´ asz. Kneser’s conjecture, chromatic number, an d homotopy. Journal of Combinatorial Theory, Series A , 25(3):319–324, 1978
1978
-
[11]
E. R. Scheinerman and D. H. Ullman. Fractional graph theory: a rational approach to the theory of graphs . Dover publications Inc., 2011
2011
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.