REVIEW 2 major objections 5 minor 28 references
On Domination Exponents for Pairs of Graphs
T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read The domination exponent is now exact for all path pairs and for even cycles.
desk verdict Strong paper with a real but fixable gap: the odd-odd path lower bound treats O-estimates as exact exponents, and the authors need to supply matching lower bounds. 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
Three constructions carry the argument. The weighted path blow-up from [4] is a target graph obtained by blowing up a long path with carefully chosen vertex and edge weights; its homomorphism counts produce the lower bound in the odd-odd path case. The projective-plane construction of Theorem 4.1 builds targets as unions of cliques on selected red lines of a large finite projective plane, and its homomorphism counts give matching lower bounds for even cycles; substituting $k+1/2$ for $k$ makes the same construction yield the odd-cycle lower bound. The 'tensor trick' (Lemma 4.5) converts inequalities with polynomial slack into exact domination inequalities, and a pruning argument reduces odd-cycle upper bounds to edgewise counts of labeled cycles. The tropical cone of Theorem 4.3, defined by explicit inequalities such as $y_{2i}-2y_{2i+2}+y_{2i+4}\ge0$ and Sidorenko-type bounds, encodes all valid pure binomial inequalities among densities of $C_2,C_4,\ldots,C_{2k}$.
What would settle it
Check the red-line projective-plane target $T_n$: if $\hom(C_{2k},T_n)$ can asymptotically exceed $O(n^{2k^2/(2k-1)})$, the lower-bound construction behind the even-cycle formula fails. Alternatively, for the odd-cycle upper bound, one graph $T$ with $t(C_5,T)<t(C_3,T)^{11/5}$ would refute the claimed bound $C(C_5,C_3)\le 11/5$.
Extended reading notes
Core claim
On the paper's own terms, the central discovery is that the domination exponent $C(H_1,H_2)$ is fully determined for two large natural families: all pairs of paths, and even cycles against arbitrary Hamiltonian-cycle graphs. In the previously open case, with $k<\ell$ both odd and $\ell=a(k+1)+r$, $0\le r\le k$, the paper proves $C(P_k,P_\ell)=(k+\ell-r)/((a+1)\ell)$. For even cycles it proves $C(C_{2k},H)=4k(k-1)/(2k\ell-2k-\ell)$ whenever $2k\ge\ell$ and $H$ has a Hamiltonian cycle on $\ell$ vertices; and for a longer odd cycle against a shorter odd cycle it proves an upper bound plus the lower bound $C(C_{2k+1},C_{2\ell+1})\ge(4k^2-1)/(4k\ell-1)$, so the value is determined asymptotically. The same circle of ideas shows that no finite collection of graph sequences can realize the even-cycle domination exponents, giving a structural negative answer to the finite-optimizer question, and yields the polyhedral cone describing the tropicalization of the edge-and-even-cycle profile.
Load-bearing premise
The completion of the path case depends on homomorphism-count estimates from an earlier paper that are quoted, not proved here: if those order-of-magnitude counts for the weighted path blow-up were wrong, the close-the-gap formula for odd-odd path pairs would not be established.
Editorial extensions
If this is right
- For every pair of paths, the value $C(P_k,P_\ell)$ is now explicit and rational, so the full list of pure binomial inequalities between path densities is known.
- For $k\ge \ell$, the even-cycle exponent is $C(C_{2k},C_{2\ell})=4k(k-1)/(4k\ell-2k-2\ell)$, and the same number governs $C_{2k}$ against any $\ell$-vertex graph with a Hamiltonian cycle.
- Since infinitely many optimizer families are needed for even cycles, no single graphon or finite family of graphons can serve as a universal witness for these exponents.
- The tropical cone description means that every valid pure binomial inequality involving edges and even cycles is a consequence of the displayed inequalities, allowing $C(G,H)$ to be computed for disjoint unions of edges and even cycles by linear programming.
Reading between the lines
- If the path construction's homomorphism counts are correct, the appearance of the division $\ell=a(k+1)+r$ suggests that path domination exponents obey a Euclidean-algorithm structure; one might expect exact values between longer paths to be computable recursively rather than case by case.
- The projective-plane construction's parameter $\alpha=k/(2k-1)$ is robust enough to survive the substitution $k\mapsto k+1/2$; a natural test is whether a similar fractional substitution closes the gap between the odd-cycle upper and lower bounds and yields an exact formula.
- The tropical cone for edges and even cycles gives a practical computational handle: any pair made of edges and even cycles can be evaluated by a finite linear program on that cone, which is likely how one would extend the list of explicit exponents further.
- Resolving the open inequality of Problem 6 would, as the paper notes, produce both an improved upper bound for $C(C_{2i+1},C_{2i-1})$ and a full tropicalization of the cycle number profile, so that inequality is a precise bottleneck for the next step.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the homomorphism density domination exponent C(H1,H2), the smallest c such that t(H1,T) ≥ t(H2,T)^c for all target graphs T. It proves that realizing all values of C requires infinitely many graph families, even for pairs of even cycles, resolving a question of Stoner. The main technical results are: a complete formula for C(P_k,P_l) for all path pairs, including the previously open odd-odd nondividing case; an exact value for C(C_{2k},H) whenever H has a Hamiltonian cycle on ℓ vertices and 2k ≥ ℓ; asymptotically sharp bounds for C(C_{2k+1},C_{2ℓ+1}); and a tropicalization computation for the density profile of edges and even cycles. The paper also establishes several miscellaneous values such as C(K_4-e, K_3)=2.
Significance. If the results are correct, the paper substantially advances the study of graph density profiles: it completes the determination of domination exponents for all path pairs, gives the first exact formulas for even-cycle domination exponents against arbitrary Hamiltonian-cycle graphs, and provides quantitative bounds for odd cycles. The projective-plane construction and the use of tropicalization are likely to be useful beyond the specific examples. The paper is honest about limitations, states open problems clearly, and credits prior work appropriately; the path blow-up results from [4] and the cycle-counting inequalities from [28] are used as black boxes with explicit references.
major comments (2)
- [Section 3, Lemma 3.1 and Example 3.2] The lower-bound argument for C(P_{2k-1}, P_{2kl+2m-1}) is derived from upper bounds only: the paper states hom(P_{2k-1};T_n)=O(n^{k·2l+1}) and hom(P_{2kl+2m-1};T_n)=O(n^{(kl+m)·2l+l+1}), then converts these to density bounds and reads off a log-ratio. This inference is not valid as written. A lower bound on the domination exponent requires a sequence whose log-ratio tends to at least the claimed value; an upper bound on a density gives only an upper bound on its logarithm, and if the true exponent of the longer path were larger than stated, the ratio could fall below the claimed value. The same issue affects the normalization: one needs v(T_n)=Θ(n^{2l+1}), not merely O(n^{2l+1}). Please either quote [4, Theorem 5.9] in a form giving matching Θ-bounds (or exact leading exponents) for these hom counts and for v(T_n), or supply a direct lower-bound argument. Example 3.2's assertion that O(n^{13}) and O(n^{31}) imply log-density limits of −17 and −39 is only justified with such matching bounds.
- [Section 4, Theorem 4.3] The proof that the rays r_i lie in trop(D_U) uses only upper bounds O(n^{...}) for the densities t(C_{2j}, T_{i,n}) on a random bipartite graph. For a sequence to realize a ray of the tropicalization, the normalized logarithms must converge to the stated exponent; this requires matching lower bounds, or at least a statement that each density is Θ(n^{...}) with high probability. If the intended claim is that the displayed O-bounds are actually tight for the random construction, please state this explicitly and provide the standard second-moment or concentration justification, or cite a theorem that supplies it. As written, the passage from O-bounds to exact log-limits is not justified.
minor comments (5)
- [Theorem 3.3, last line] The formula C(P_k,P_l)=(k+ℓ−r)/((a+1)ℓ) should be parenthesized as (k+ℓ−r)/((a+1)ℓ); the current typesetting in the statement is ambiguous.
- [Theorem 4.6, displayed exponent] In the proof of Theorem 4.6, the displayed denominator '4ℓ(k−ℓ+2)−(2ℓ+1)' appears inconsistent with the final bound '4ℓ(k−ℓ+1)−(2ℓ+1)'; the final expression is the one that matches Theorem 4.1, so the earlier display should be corrected.
- [Theorem 5.1(3)] The statement 'C(K2,H)=ν∗(H)−1' should read 'C(K2,H)=ν∗(H)^{-1}' (the reciprocal), as is used in Problem 1; the current typography suggests a subtraction.
- [Theorem 5.3] In the proof of Theorem 5.3, 'Berhend graph' should be 'Behrend graph', and the phrase 't(K4, GN)' should read 't(K4−e, GN)'.
- [Example 3.2] The diagram for the weighted path blow-up is difficult to read; a table listing the vertex weights and edge weights would make the construction easier to verify.
Circularity Check
No circularity: the paper's domination exponents are derived from explicit constructions and independent published inequalities, not from fitted inputs or self-referential definitions.
full rationale
The derivation chain for each new C(H1,H2) consists of an upper bound supplied by an independent inequality (Erdős–Simonovits, Sidorenko for even cycles, the spectral/Hölder inequality (4), Kruskal–Katona, or Tao's C(K4−e,K3) bound) and a lower bound supplied by an explicit graph sequence (projective-plane unions for cycles, random bipartite graphs for even-cycle tropicalization, and the weighted path blow-up for odd paths). None of these constructions is fitted to the claimed exponent, and none of the stated theorems appears as a hypothesis in its own proof. The one load-bearing overlap with the authors' prior work is the citation of [4] in Lemma 3.1 for homomorphism counts in a path blow-up; those counts are a published, parameter-specific computation that does not mention domination exponents, so the citation is independent evidence rather than a circular self-citation. A non-circular correctness concern should be flagged: in Lemma 3.1 the lower-bound proof records only O upper bounds on the two hom counts, and Example 3.2 reads O as an exact leading exponent; the odd-odd nondividing path case therefore appears to require matching lower bounds that are not stated. This is a proof gap, not a circularity, and it does not raise the circularity score.
Assumptions & free parameters
assumptions (8)
- standard math Sidorenko's inequality for even cycles: t(C_{2k},T) >= t(C_2,T)^{2k} for all T
- standard math Erdos-Simonovits inequality for paths [25,5]
- standard math Stoner's prior computation of C(P_k,P_ell) except the odd-odd nondividing case, and C(C_{2k},C_ell)=2k/ell for 2k<=ell [28]
- standard math Path blow-up construction and homomorphism counts from Blekherman and Raymond [4, Definition 5.7 and Theorem 5.9]
- standard math Spectral log-convexity of graph spectral moments
- standard math Kruskal-Katona theorem
- standard math Kopparty-Rossman linear programming characterization of the homomorphism domination exponent for chordal series-parallel graphs [16, Theorem 3.3]
- standard math Tao's inequality t(K4-e,W) >= t(K3,W)^2 log* t(K3,W), as cited in Lovasz [19, Exercise 16.21]
Cite this review
Pith. "Pith review of On Domination Exponents for Pairs of Graphs." pith.science (2026). https://pith.science/paper/S65QL5ND
@misc{pith2026250612151,
author = {Pith},
title = {Pith review of: On Domination Exponents for Pairs of Graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/S65QL5ND}},
note = {Machine review of arXiv:2506.12151}
}
abstract
Understanding graph density profiles is notoriously challenging. Even for pairs of graphs, complete characterizations are known only in very limited cases, such as edges versus cliques. This paper explores a relaxation of the graph density profile problem by examining the homomorphism density domination exponent $C(H_1, H_2)$. This is the smallest real number $c \geq 0$ such that $t(H_1, T) \geq t(H_2, T)^c$ for all target graphs $T$ (if such a $c$ exists) where $t(H,T)$ is the homomorphism density from $H$ to $T$. We demonstrate that infinitely many families of graphs are required to realize $C(H_1, H_2)$ for all connected graphs $H_1$, $H_2$. We derive the homomorphism density domination exponent for a variety of graph pairs, including paths and cycles. As a couple of typical examples, we obtain exact values when $H_1$ is an even cycle and $H_2$ contains a Hamiltonian cycle, and provide asymptotically sharp bounds when both $H_1$ and $H_2$ are odd cycles.
Reference graph
Works this paper leans on
-
[4]
G. Blekherman and A. Raymond. A Path Forward: Tropicalization in Extremal Combinatorics. Advances in Mathematics, 407:1–68, 2022
work page 2022
-
[28]
C. Stoner. The graph density domination exponent. arXiv:2211.09870, 2022. Georgia Institute of Technology Email address: greg@math.gatech.edu University of Massachusetts Amherst Email address: annieraymond@umass.edu University of Chicago and Steklov Mathematical Institute Email address: razborov@uchicago.edu Duke University Email address: fan.wei@duke.edu
work page Pith review arXiv 2022
-
[1]
R. Ahlswede and G.O.H. Katona. Graphs with maximal numbers of adjacent pairs of edges. Acta Math. Acad. Sci. Hungar., 32:97-120, 1978
work page 1978
-
[2]
D. Alessandrini. Logarithmic limit sets of real semi-algebraic sets. Adv. Geom.13(2013), no. 1, 155–190
work page 2013
-
[3]
N. Alon. On the number of subgraphs of prescribed type of graphs with a given number of edges. Israel J. Math, 38:116-130, 1981
work page 1981
-
[5]
G. Blekherman and A. Raymond. A New Proof of the Erd˝ os–Simonovits Conjecture on Walks. Graphs and Com- binatorics, 39:art. 53, 2023. 20 GRIGORIY BLEKHERMAN, ANNIE RAYMOND, ALEXANDER RAZBOROV, AND F AN WEI
work page 2023
-
[6]
G. Blekherman, A. Raymond, M. Singh, and R.R. Thomas. Tropicalization of Graph Profiles. Transactions of the American Mathematical Society, 375(9):6281–6310, 2022
work page 2022
-
[7]
G. Blekherman, A. Raymond, and F. Wei. Undecidability of polynomial inequalities in weighted graph homomor- phism densities. Forum Math. Sigma, 12 (2024): Paper No. e40
work page 2024
Show all 28 references
-
[8]
Bollob´ as
B. Bollob´ as. Relations between sets of complete subgraphs. Proc. Fifth British Comb. Conference, 79–84, 1975
1975
-
[9]
H. Chen, Y. Lin, J. Ma, and F. Wei. Undecidability of polynomial inequalities in tournaments. arXiv:2412.04972
-
[10]
Conlon, J
D. Conlon, J. Fox, and B. Sudakov. An Approximate Version of Sidorenko’s Conjecture. Geometric and Functional Analysis, 20(6): 1354–1366, 2010
2010
-
[11]
Conlon and J
D. Conlon and J. Lee. Domination inequalities and dominating graphs. arXiv:2303.01997
-
[12]
Dasc˘ alu and A
M. Dasc˘ alu and A. Raymond, Tropicalizing the Graph Profile of Some Almost-Stars, SIAM Journal on Discrete Mathematics, 2025
2025
-
[13]
Freedman, L
M. Freedman, L. Lov´ asz, and A. Schrijver. Reflection positivity, rank connectivity, and homomorphism of graphs. J. Amer. Math. Soc., 20(1):37–51, 2007
2007
-
[14]
Hatami, and S
H. Hatami, and S. Norine. Undecidability of linear inequalities in graph homomorphism densities. J. Amer. Math. Soc., 24(2):547–565, 2011
2011
-
[15]
Janson, K
S. Janson, K. Oleszkiewicz, and A. Ruci´ nski. Upper tails for subgraph counts in random graphs. Isr. J. Math., 142:61–92, 2004
2004
-
[16]
Kopparty and B
S. Kopparty and B. Rossman. The homomorphism domination exponent. European Journal of Combinatorics, 32(7):1097–1114, 2011
2011
-
[17]
Lov´ asz
L. Lov´ asz. Graph homomorphisms: Open problems. Manuscript available at https://web.cs.elte.hu/lovasz/ problems.pdf
-
[18]
Lov´ asz
L. Lov´ asz. Subgraph densities in signed graphons and the local Sidorenko conjecture. Electronic Journal of Com- binatorics, 18(1) 2011
2011
-
[19]
Lov´ asz.Large Networks and Graph Limits.Amer
L. Lov´ asz.Large Networks and Graph Limits.Amer. Math. Soc. Colloq. Publ. 60, AMS, Providence, RI, 2012
2012
-
[20]
Random graphons and a weak Positivstellensatz for graphs
L. Lov´ asz and B. Szegedy. “Random graphons and a weak Positivstellensatz for graphs.” J. Graph Theory70(2) (2012): 214–225
2012
-
[21]
Nikiforov
V. Nikiforov. The number of cliques in graphs of given order and size. Trans. Amer. Math. Soc. 363 (2011), 1599–1618
2011
-
[22]
Razborov
A.A. Razborov. Flag algebras. J. Symbolic Logic, 72(4):1239–1282, 2007
2007
-
[23]
Razborov
A.A. Razborov. On the minimal density of triangles in graphs. Combin. Probab. Comput.17 (2008), no. 4, 603–618
2008
-
[24]
C. Reiher. The clique density theorem. Ann. of Math.(2) 184 (2016), no. 3, 683–707
2016
-
[25]
Sa˘ glam
M. Sa˘ glam. Near Log-Convexity of Measured Heat in (Discrete) Time and Consequences. 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, 967–978, 2018
2018
-
[26]
Sidorenko
A. Sidorenko. A correlation inequality for bipartite graphs. Graphs and Combinatorics, 9:201–204, 1993
1993
-
[27]
Sidorenko
A. Sidorenko. Partially ordered set of functionals corresponding to graphs. Discrete Math, 131:263-277, 1994
1994
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.