Pith. sign in

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 →

arxiv 2506.12151 v2 pith:S65QL5ND submitted 2025-06-13 math.CO

classification math.CO MSC 05C3505C38
keywords graphdensityprofileshomomorphismdominationexponentpurebinomialinequalitiestropicalizationpathsandcyclesprojectiveplaneconstructionSidorenkoinequality
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

For two fixed graphs $H_1,H_2$, the domination exponent $C(H_1,H_2)$ is the least $c\ge 0$ such that every target graph $T$ satisfies $t(H_1,T)\ge t(H_2,T)^c$, where $t$ is homomorphism density. The paper closes the one open case for paths, giving the exact formula $C(P_k,P_\ell)=(k+\ell-r)/((a+1)\ell)$ when $k<\ell$ are both odd and $\ell=a(k+1)+r$, so the domination exponent is now known for every pair of paths. It also proves the exact value $C(C_{2k},H)=4k(k-1)/(2k\ell-2k-\ell)$ for every graph $H$ on $\ell$ vertices that contains a Hamiltonian cycle when $2k\ge\ell$, and it gives asymptotically sharp bounds for a longer odd cycle versus a shorter odd cycle. A further result is that realizing all even-cycle exponents requires infinitely many graph families, and the tropicalization of the edge-and-even-cycle density profile is explicitly described. These are the sharp inequalities that organize the whole set of pure binomial density constraints for paths and for cycles.

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$.

Watch

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

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

  • 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.
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 / 5 minor

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)
  1. [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.
  2. [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)
  1. [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.
  2. [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.
  3. [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.
  4. [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)'.
  5. [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

0 steps flagged · score 0.0 of 10

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 0 free parameters · 8 assumptions · 0 invented entities

The paper introduces no new entities or fitted constants. Its central results are proved from standard theorems and prior published results in extremal combinatorics. Proof parameters such as alpha=k/(2k-1) in the projective-plane construction are chosen to balance inequalities, not fitted to data.

assumptions (8)
  • standard math Sidorenko's inequality for even cycles: t(C_{2k},T) >= t(C_2,T)^{2k} for all T
    Used in the upper bound of Theorem 4.1 and in Theorem 4.3; this is a theorem, not the open conjecture, for cycles.
  • standard math Erdos-Simonovits inequality for paths [25,5]
    Used in Lemma 3.1 to derive the upper bound for the odd path case.
  • 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]
    The paper completes these open cases; the prior results serve as the base for the new derivations.
  • standard math Path blow-up construction and homomorphism counts from Blekherman and Raymond [4, Definition 5.7 and Theorem 5.9]
    Provides the lower bound construction in Lemma 3.1 for the missing path case.
  • standard math Spectral log-convexity of graph spectral moments
    Used to prove inequality (4) in Theorem 4.1, via l^p norm interpolation on normalized eigenvalues.
  • standard math Kruskal-Katona theorem
    Used in the proof of Theorem 5.1(1) for the case v(H1) <= v(H2).
  • standard math Kopparty-Rossman linear programming characterization of the homomorphism domination exponent for chordal series-parallel graphs [16, Theorem 3.3]
    Used in Lemma 6.1 to compute HDE(C_2^{2i-2} C^c_{2i+1}, C_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]
    Used in Theorem 5.3 to obtain the upper bound C(K4-e,K3) <= 2.

how reviews work

0 comments
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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages

  1. [4]

    Blekherman and A

    G. Blekherman and A. Raymond. A Path Forward: Tropicalization in Extremal Combinatorics. Advances in Mathematics, 407:1–68, 2022

  2. [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

  3. [1]

    Ahlswede and G.O.H

    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

  4. [2]

    Alessandrini

    D. Alessandrini. Logarithmic limit sets of real semi-algebraic sets. Adv. Geom.13(2013), no. 1, 155–190

  5. [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

  6. [5]

    Blekherman and A

    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

  7. [6]

    Blekherman, A

    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

  8. [7]

    Blekherman, A

    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

Show all 28 references
  1. [8]

    Bollob´ as

    B. Bollob´ as. Relations between sets of complete subgraphs. Proc. Fifth British Comb. Conference, 79–84, 1975

  2. [9]

    H. Chen, Y. Lin, J. Ma, and F. Wei. Undecidability of polynomial inequalities in tournaments. arXiv:2412.04972

  3. [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

  4. [11]

    Conlon and J

    D. Conlon and J. Lee. Domination inequalities and dominating graphs. arXiv:2303.01997

  5. [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

  6. [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

  7. [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

  8. [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

  9. [16]

    Kopparty and B

    S. Kopparty and B. Rossman. The homomorphism domination exponent. European Journal of Combinatorics, 32(7):1097–1114, 2011

  10. [17]

    Lov´ asz

    L. Lov´ asz. Graph homomorphisms: Open problems. Manuscript available at https://web.cs.elte.hu/lovasz/ problems.pdf

  11. [18]

    Lov´ asz

    L. Lov´ asz. Subgraph densities in signed graphons and the local Sidorenko conjecture. Electronic Journal of Com- binatorics, 18(1) 2011

  12. [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

  13. [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

  14. [21]

    Nikiforov

    V. Nikiforov. The number of cliques in graphs of given order and size. Trans. Amer. Math. Soc. 363 (2011), 1599–1618

  15. [22]

    Razborov

    A.A. Razborov. Flag algebras. J. Symbolic Logic, 72(4):1239–1282, 2007

  16. [23]

    Razborov

    A.A. Razborov. On the minimal density of triangles in graphs. Combin. Probab. Comput.17 (2008), no. 4, 603–618

  17. [24]

    C. Reiher. The clique density theorem. Ann. of Math.(2) 184 (2016), no. 3, 683–707

  18. [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

  19. [26]

    Sidorenko

    A. Sidorenko. A correlation inequality for bipartite graphs. Graphs and Combinatorics, 9:201–204, 1993

  20. [27]

    Sidorenko

    A. Sidorenko. Partially ordered set of functionals corresponding to graphs. Discrete Math, 131:263-277, 1994

Pith tools

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