{"id":"b481ad7b-0b57-4727-989c-fc572d843bd2","arxiv_id":"2506.12151","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Exact homomorphism density domination exponents are determined for all path pairs and for even cycles against Hamiltonian-cycle graphs, with asymptotically sharp bounds for odd cycles.","lead":"This paper computes the exact domination exponent for many pairs of graph patterns, measuring how fast one pattern's density can be bounded below by another pattern's density power in any large graph. The results finish the classification for all path pairs and most cycle pairs, and show that infinitely many different test-graph families are needed to realize these exponents.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.1's lower bound for odd-odd paths uses O upper bounds on hom counts, which do not alone determine the log-ratio; matching lower bounds are needed to complete the path formula.","rationale":"The paper contains substantial new results: a complete path formula, exact even-cycle values and Hamiltonian-cycle generalizations, a tropicalization of the even-cycle density profile, and asymptotic odd-cycle bounds. The reader correctly identified the reliance on [4, Theorem 5.9] as the weakest point. My stress-test sharpens this: the issue is not only whether the cited counts are correct, but whether the form in which they are used is sufficient. A lower bound on a supremum requires exhibiting a sequence with ratio at least the claimed value, and O-estimates do not certify that. The manuscript's own Example 3.2 reads exact exponents off O statements, confirming that matching lower bounds are being implicitly assumed. This is load-bearing because the odd-odd nondividing path case is the only part of Theorem 3.3 that was previously open. Other possible concerns, such as minor denominator typos in Theorem 4.6 or terse random-graph count justifications in Theorem 4.3, do not appear to threaten the central claims as directly. If the requested check confirms Theta-bounds in [4], the verdict can remain ACCEPT; otherwise the path formula's proof is incomplete and the paper should be accepted only conditionally on supplying the missing lower bounds.","tokens_in":19155,"tokens_out":30749,"duration_ms":347350,"concrete_test":"Re-derive the leading exponents of hom(P_{2k-1}; T_n) and hom(P_{2kl+2m-1}; T_n) directly from the weighted path blow-up in [4, Definition 5.7], for instance by expanding the weighted-walk generating function for the base path and checking that there is a walk with the stated exponent and positive coefficient. If [4, Theorem 5.9] is checked and supplies Theta(n^d) estimates with positive constants, the concern is resolved; if it only supplies O(n^d), the lower bound in Lemma 3.1 is not established and the odd-odd nondividing path case needs a new argument.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In Section 3, Lemma 3.1, the lower bound for C(P_{2k-1}, P_{2kl+2m-1}) is derived by citing [4, Theorem 5.9] for 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 converting these to density estimates and reading off the log-ratio. But the domination exponent is a supremum over target graphs, so a lower bound requires a sequence whose log-ratio is at least the claimed value. Big-O estimates are upper bounds on the hom counts: if the true exponent for the long path were larger in magnitude than the stated one while the short path remained at its bound, the ratio log t(P_{2k-1}, T_n)/log t(P_{2kl+2m-1}, T_n) could fall below the claimed value. Thus, unless [4, Theorem 5.9] actually provides matching Theta-bounds, or the paper supplies lower bounds on these hom counts from the weighted blow-up construction, the proof has a logical gap in the previously open odd-odd nondividing case of Theorem 3.3. Example 3.2 tacitly treats the O estimates as exact leading exponents, but that inference is not justified in the text.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":19403,"tokens_out":43065,"duration_ms":473555,"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":[{"comment":"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":"Section 3, Lemma 3.1 and Example 3.2"},{"comment":"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.","section":"Section 4, Theorem 4.3"}],"minor_comments":[{"comment":"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.","section":"Theorem 3.3, last line"},{"comment":"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.","section":"Theorem 4.6, displayed exponent"},{"comment":"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.","section":"Theorem 5.1(3)"},{"comment":"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)'.","section":"Theorem 5.3"},{"comment":"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.","section":"Example 3.2"}],"recommendation":"major_revision","confidential_remarks":"The paper contains substantial results and the main theorems appear defensible, but the proof of Lemma 3.1 has a genuine logical gap in the lower-bound argument, and Theorem 4.3 has a similar O-versus-Theta issue. Both are fixable by citing or supplying matching asymptotic bounds. The dependence on [4] for the exact hom counts is acceptable if the exact statement is quoted, but the current text is not sufficiently explicit. I recommend major revision rather than rejection, because the results and methods are valuable and the gaps are local rather than fatal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe headline is that this is a serious piece of work that resolves Stoner's question and completes the path classification, but it has one genuine soft spot in the proof of the previously open odd-odd path case. The even-cycle results, the Hamiltonian-cycle generalization, and the tropicalization of the even-cycle profile all look solid. The infinite-realizers result via Ramsey is clever and correct.\n\nWhat's actually new: the exact formula for C(P_k,P_ell) in the odd-odd nondividing case, the first exact even-cycle values in the 2k>ell regime, the tropicalization of edges-plus-even-cycles profile, and the proof that no finite family of optimizers suffices. The projective-plane construction in Theorem 4.1 is a nice piece of extremal thinking; the upper bound via spectral Hölder is clean.\n\nThe soft spot is in Lemma 3.1. To get a lower bound on C(P_{2k-1},P_{2kl+2m-1}), the proof cites [4, Theorem 5.9] for hom counts that are O(n^{...}) and then reads off the log-ratio of densities as if the O were a two-sided asymptotic. It isn't, at least not as stated in the text. With only upper bounds on the hom counts, the true densities could have different leading exponents, and the ratio of logs could be smaller than claimed. Example 3.2 does the same thing: \"O(n^13)\" does not imply the log-density tends to -17. If [4, Theorem 5.9] actually provides matching lower bounds (Theta), then this is an expository fix; if not, the previously open case of Theorem 3.3 is not established. The authors should be asked to state the two-sided bound or prove it. Everything else in the paper checks out.\n\nThe citation to [4] is appropriate; this is not a circularity problem. The self-citation is to a published theorem, and the lower bounds for cycles come from explicit constructions.\n\nWho is this for? Anyone working on graph density profiles, Sidorenko-type inequalities, or tropicalization of graph limits. It deserves a serious referee. My recommendation: send to review, but the referee should push for a clarification or correction in Lemma 3.1. With that fixed, the paper is a clear accept; without it, the path classification is incomplete.\n\nReading group: yes, I'd bring it up. I'd cite the even-cycle formula and the tropicalization result.","headline":"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.","tokens_in":19979,"tokens_out":3416,"would_cite":true,"duration_ms":40449,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C38"],"pacs":[],"model":"deepseek-v4-flash","headline":"The domination exponent is now exact for all path pairs and for even cycles.","keywords":["graph density profiles","homomorphism density","domination exponent","pure binomial inequalities","tropicalization","paths and cycles","projective plane construction","Sidorenko inequality"],"falsifier":"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$.","tokens_in":18942,"feed_emoji":"📈","tokens_out":9527,"duration_ms":103249,"temperature":0.7,"pith_summary":"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.","feed_headline":"Exact domination exponents for all path pairs and even cycles","feed_subtitle":"The paper closes the odd-odd path case and pins even cycles against Hamiltonian graphs; longer odd cycles get asymptotically sharp bounds.","key_machinery":"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}$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Earlier computation of domination exponents for most path pairs and for even cycles; it sets the cases and lower bounds this paper completes, and leaves the odd-odd path case open.","marker":"[28]"},{"why":"Constructs the weighted path blow-up and gives the homomorphism counts whose order of magnitude supplies the lower bound in the odd-odd path case.","marker":"[4]"},{"why":"Erdős–Simonovits inequality for walks, used to prove the upper-bound side of the path domination exponent.","marker":"[25, 5]"},{"why":"Defines the homomorphism domination exponent and supplies the linear-programming machinery used in the cycle-inequality lemma.","marker":"[16]"},{"why":"Lovász's concavity statement for even cycles, used alongside the new projective-plane argument for even-cycle domination values.","marker":"[18]"},{"why":"Establishes that valid pure binomial inequalities are captured by tropicalization, the basis for the edge/even-cycle tropical cone result.","marker":"[6]"}],"fun_headline_variants":["Exact domination exponents for every pair of paths","Even cycles: exact domination exponents vs Hamiltonian graphs","Odd cycles: asymptotically sharp domination exponents","No finite families can realize even-cycle domination exponents","Paths fully solved, even cycles exact, odd cycles sharp"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Exact domination exponents for every pair of paths","Even cycles: exact domination exponents vs Hamiltonian graphs","Odd cycles: asymptotically sharp domination exponents","No finite families can realize even-cycle domination exponents","Paths fully solved, even cycles exact, odd cycles sharp"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000879,"raw_usage":{"total_tokens":3839,"prompt_tokens":1021,"completion_tokens":2818,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":637,"completion_tokens_details":{"reasoning_tokens":2746}},"tokens_in":637,"tokens_out":2818,"duration_ms":25501,"temperature":1.0,"reasoning_tokens":2746,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T00:59:18.046863+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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$.","supporting_citations":[{"cited_title":"The Graph Density Domination Exponent","cited_arxiv_id":"2211.09870","evidence_quote":"Earlier computation of domination exponents for most path pairs and for even cycles; it sets the cases and lower bounds this paper completes, and leaves the odd-odd path case open."},{"cited_title":"Blekherman and A","cited_arxiv_id":null,"evidence_quote":"Constructs the weighted path blow-up and gives the homomorphism counts whose order of magnitude supplies the lower bound in the odd-odd path case."},{"cited_title":"Kopparty and B","cited_arxiv_id":null,"evidence_quote":"Defines the homomorphism domination exponent and supplies the linear-programming machinery used in the cycle-inequality lemma."},{"cited_title":"Lov´ asz","cited_arxiv_id":null,"evidence_quote":"Lovász's concavity statement for even cycles, used alongside the new projective-plane argument for even-cycle domination values."},{"cited_title":"Blekherman, A","cited_arxiv_id":null,"evidence_quote":"Establishes that valid pure binomial inequalities are captured by tropicalization, the basis for the edge/even-cycle tropical cone result."}],"review_version":1}