pith. sign in

arxiv: 2606.30010 · v1 · pith:LNJW3GJ5new · submitted 2026-06-29 · 🧮 math.CO

L^p-form of the KNRS conjecture

Yuqi Zhao This is my paper

Pith reviewed 2026-06-30 05:33 UTC · model grok-4.3

classification 🧮 math.CO
keywords KNRS conjecturegraphonslocally dense graphsL^p normsHolder uniformizationSidorenko conjecturetheta-subdivisions
0
0 comments X

The pith

For p at least binom(n,2)/m every rho-locally dense graphon satisfies the L^p lower bound on homomorphic copies of any fixed graph F.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes an L^p relaxation of the KNRS conjecture in the graphon setting. For any graph F with m edges and n non-isolated vertices, when p meets or exceeds binom(n,2)/m, every rho-locally dense graphon W obeys t(F, W composed with p) at least rho to the power pm. This is the same as saying the L^p norm of the product of W over the edges of F is at least rho to the number of edges. The result follows from a Holder uniformization step over vertex relabellings and yields additional comparison and subdivision theorems as corollaries.

Core claim

If p is at least binom(n,2)/m then for every rho-locally dense graphon W, t(F, W to the circle p) is at least rho to the pm, equivalently the L^p norm of W_F is at least rho to the e(F). The proof proceeds by Holder uniformization over vertex relabellings. A comparison principle with edge-transitive KNRS supergraphs gives sharper exponents in some cases, and positive-semidefinite methods show that Sidorenko-good graphs are closed under uniform theta-subdivisions, that the non-uniform theta theorem lifts after removing the parity restriction, and that uniform theta-subdivisions of KNRS graphs are regular-KNRS.

What carries the argument

Holder uniformization over vertex relabellings, which converts the local-density hypothesis on W into the desired L^p lower bound on the edge-product function W_F.

If this is right

  • Every graph with at least one edge satisfies the stated L^p form of the KNRS conjecture.
  • Sharper exponents hold whenever F embeds into an edge-transitive KNRS graph.
  • Sidorenko-good graphs remain Sidorenko-good under arbitrary uniform theta-subdivisions.
  • Uniform theta-subdivisions of KNRS graphs are regular-KNRS.
  • The non-uniform theta theorem admits a Sidorenko-good lift after removing the parity restriction under the same divisibility assumptions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The L^p bound may serve as an intermediate step toward the full KNRS conjecture if it can be upgraded by letting p grow or by combining it with other density-increment arguments.
  • Edge-transitive graphs appear to play a distinguished role because the comparison principle improves the exponent precisely when such a supergraph exists.
  • The subdivision closure results suggest that both the Sidorenko and KNRS properties are stable under uniform theta-subdivision operations.

Load-bearing premise

A Holder uniformization step over vertex relabellings exists that converts the local-density hypothesis into the L^p lower bound under the needed uniformity and measurability conditions on the graphon.

What would settle it

A concrete graph F, exponent p equal to binom(n,2)/m, and rho-locally dense graphon W for which the L^p norm of the edge-product W_F falls strictly below rho to the power e(F).

read the original abstract

The Kohayakawa--Nagle--R\"odl--Schacht conjecture predicts that locally dense graphs contain, asymptotically, at least as many homomorphic copies of any fixed graph as the random graph of the same edge density. We prove that every graph with at least one edge satisfies a natural $L^p$ relaxation of this conjecture in the graphon setting. More precisely, let $F$ be a graph with $m>0$ edges, and let $n$ be the number of non-isolated vertices of $F$. If $$ p\ge \binom {n}{2}/m, $$ then for every $\rho$-locally dense graphon $W$, $$ t(F,W^{\circ p})\ge \rho^{pm}. $$ Equivalently, if $$ W_F(\mathbf x)=\prod_{ij\in E(F)}W(x_i,x_j), $$ then $$ \|W_F\|_{L^p}\ge \rho^{e(F)}. $$ The proof is based on a H\"older uniformization over vertex relabellings, in the spirit of Conlon--Lee. We also prove a more general comparison principle with edge-transitive KNRS supergraphs, yielding sharper exponents whenever $F$ embeds into an edge-transitive KNRS graph. Finally, positive-semidefinite methods give theta-subdivision results: Sidorenko-good graphs are closed under arbitrary uniform theta-subdivisions; the non-uniform theta theorem of Im--Li--Liu admits a Sidorenko-good lift, under the same divisibility assumptions, after removing the parity restriction; and uniform theta-subdivisions of KNRS graphs are regular-KNRS.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper proves an L^p relaxation of the KNRS conjecture in the graphon setting: for a graph F with m>0 edges and n non-isolated vertices, if p ≥ binom(n,2)/m then every ρ-locally dense graphon W satisfies t(F, W^{∘p}) ≥ ρ^{p m}, or equivalently ||W_F||_{L^p} ≥ ρ^{e(F)}. The proof uses Hölder uniformization over vertex relabellings in the spirit of Conlon-Lee. It also establishes a comparison principle yielding sharper exponents for F embeddable in edge-transitive KNRS graphs, and positive-semidefinite results on theta-subdivisions: Sidorenko-good graphs are closed under uniform theta-subdivisions, the Im-Li-Liu non-uniform theta theorem lifts to Sidorenko-good graphs without parity restriction under divisibility assumptions, and uniform theta-subdivisions of KNRS graphs are regular-KNRS.

Significance. If the central L^p inequality holds, the result supplies a natural and potentially useful relaxation of the full KNRS conjecture, together with a technique (Hölder uniformization) that may extend to stronger statements. The comparison principle and the subdivision closure results are of independent interest and strengthen the known landscape around Sidorenko and KNRS properties. The manuscript gives a clean, parameter-free statement of the exponent threshold and credits the Conlon-Lee inspiration explicitly.

major comments (1)
  1. [Proof of the main theorem (Hölder uniformization step)] The proof of the main L^p inequality (the statement in the abstract and presumably Theorem 1.1) proceeds by averaging t(F, W^σ) over vertex relabellings σ and applying Hölder to pass from the ρ-local-density hypothesis on each W^σ to the desired bound on ||W_F||_{L^p}. This step requires that the map σ ↦ W^σ preserve measurability and that the local-density lower bound transfers to the averaged object; the manuscript invokes the uniformization 'in the spirit of Conlon-Lee' but does not record the σ-algebra on the space of relabellings or the precise integrability class of W needed for the integrals defining t(F, W^{∘p}) to be well-defined and interchangeable with the supremum over σ.
minor comments (1)
  1. [Abstract] In the abstract the notation W^{∘p} and W_F(𝐱) is used before the definitions that appear later in the text; a brief parenthetical reminder would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the need for greater measure-theoretic precision in the Hölder uniformization argument. We address the single major comment below and will incorporate the requested clarifications in the revised manuscript.

read point-by-point responses

  1. Referee: The proof of the main L^p inequality (the statement in the abstract and presumably Theorem 1.1) proceeds by averaging t(F, W^σ) over vertex relabellings σ and applying Hölder to pass from the ρ-local-density hypothesis on each W^σ to the desired bound on ||W_F||_{L^p}. This step requires that the map σ ↦ W^σ preserve measurability and that the local-density lower bound transfers to the averaged object; the manuscript invokes the uniformization 'in the spirit of Conlon-Lee' but does not record the σ-algebra on the space of relabellings or the precise integrability class of W needed for the integrals defining t(F, W^{∘p}) to be well-defined and interchangeable with the supremum over σ.

    Authors: We agree that the current write-up leaves the underlying measure space implicit. In the revision we will add a short subsection (or appendix paragraph) that (i) models the space of relabellings as the compact group of measure-preserving transformations of [0,1] equipped with its Haar probability measure, (ii) verifies that σ ↦ W^σ is measurable with respect to the product σ-algebra and preserves the L^1 (or L^∞) class of W, (iii) shows that the ρ-local-density lower bound passes to the averaged graphon by Fubini, and (iv) justifies the interchange of the integral defining t(F,W^{∘p}) with the supremum over σ via the dominated-convergence theorem under the standing assumption that W is bounded (as is standard for graphons). These additions will make the Hölder-uniformization step fully rigorous while remaining in the spirit of the Conlon–Lee argument. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation proceeds via Holder on averaged relabellings

full rationale

The paper states that the L^p lower bound follows from the rho-local-density hypothesis by averaging t(F, W^sigma) over vertex relabellings sigma and applying Holder, in the spirit of Conlon-Lee. This is an inequality step from the given assumption to the claimed bound on ||W_F||_L^p, with no reduction of the left-hand side to fitted constants, no self-definitional equivalence, and no load-bearing self-citation for the central claim. The reference to Conlon-Lee supplies the averaging technique but does not make the present result equivalent to prior inputs by construction. No steps match the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The argument rests on standard analytic inequalities and the definition of graphons and local density; no new free parameters or invented entities are introduced.

axioms (2)
  • standard math Holder's inequality applies to the product functions arising from graphons
    Invoked in the uniformization step described in the abstract.
  • domain assumption Graphons are measurable functions [0,1]^2 → [0,1] and homomorphism densities are well-defined integrals
    Background assumption of the graphon setting used throughout.

pith-pipeline@v0.9.1-grok · 5827 in / 1411 out tokens · 48504 ms · 2026-06-30T05:33:31.894396+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Tensor Amplification and Spectral Transfer for Sidorenko-Type Inequalities

    math.CO 2026-07 unverdicted novelty 6.0

    Tensor-amplification framework proves equality regularization and spectral equivalence for C-Sidorenko graphs in admissible graphon classes.

Reference graph

Works this paper leans on

13 extracted references · 10 canonical work pages · cited by 1 Pith paper

  1. [1]

    Counting subgraphs in locally dense graphs.Israel Journal of Mathematics, 2025

    Domagoj Bradaˇ c, Benny Sudakov, and Yuval Wigderson. Counting subgraphs in locally dense graphs.Israel Journal of Mathematics, 2025. To appear

    2025

  2. [2]

    Kohayakawa–Nagle–R¨ odl–Schacht conjecture for subdivisions.arXiv preprint arXiv:2407.10861, 2024

    Hao Chen, Yupeng Lin, and Jie Ma. Kohayakawa–Nagle–R¨ odl–Schacht conjecture for subdivisions.arXiv preprint arXiv:2407.10861, 2024

    work page arXiv 2024

  3. [3]

    Sidorenko’s conjecture for blow-ups.Discrete Anal- ysis, pages Paper No

    David Conlon and Joonkyung Lee. Sidorenko’s conjecture for blow-ups.Discrete Anal- ysis, pages Paper No. 2, 13 pp., 2021. doi: 10.19086/da.21472

    work page doi:10.19086/da.21472 2021

  4. [4]

    Some advances on Sidorenko’s conjecture.Journal of the London Mathematical Society, 98(3):593–608,

    David Conlon, Jeong Han Kim, Choongbum Lee, and Joonkyung Lee. Some advances on Sidorenko’s conjecture.Journal of the London Mathematical Society, 98(3):593–608,

  5. [5]

    doi: 10.1112/jlms.12142

    work page doi:10.1112/jlms.12142

  6. [6]

    A limit theorem in graph theory.Studia Scientiarum Mathematicarum Hungarica, 1:51–57, 1966

    Paul Erd˝ os and Mikl´ os Simonovits. A limit theorem in graph theory.Studia Scientiarum Mathematicarum Hungarica, 1:51–57, 1966

    1966

  7. [7]

    Sidorenko’s conjecture for subdivisions and theta substitutions.Combinatorics, Probability and Computing, 35(2):269–279, 2026

    Seonghyuk Im, Ruonan Li, and Hong Liu. Sidorenko’s conjecture for subdivisions and theta substitutions.Combinatorics, Probability and Computing, 35(2):269–279, 2026. doi: 10.1017/S0963548325100242

    work page doi:10.1017/s0963548325100242 2026

  8. [8]

    Forcing Graphs to Be Forcing.arXiv preprint arXiv:2412.12904, 2024

    Aldo Kiem, Olaf Parczyk, and Christoph Spiegel. Forcing Graphs to Be Forcing.arXiv preprint arXiv:2412.12904, 2024

    work page arXiv 2024

  9. [9]

    Weak hypergraph regularity and linear hypergraphs.Journal of Combinatorial Theory, Series B, 100(2):151–160, 2010

    Yoshiharu Kohayakawa, Brendan Nagle, Vojtˇ ech R¨ odl, and Mathias Schacht. Weak hypergraph regularity and linear hypergraphs.Journal of Combinatorial Theory, Series B, 100(2):151–160, 2010. doi: 10.1016/j.jctb.2009.05.005

    work page doi:10.1016/j.jctb.2009.05.005 2010

  10. [10]

    On some graph densities in locally dense graphs.Random Structures & Algorithms, 58(2):322–344, 2021

    Joonkyung Lee. On some graph densities in locally dense graphs.Random Structures & Algorithms, 58(2):322–344, 2021. doi: 10.1002/rsa.20974

    work page doi:10.1002/rsa.20974 2021

  11. [11]

    Counting odd cycles in locally dense graphs.Journal of Combinatorial Theory, Series B, 105:1–5, 2014

    Christian Reiher. Counting odd cycles in locally dense graphs.Journal of Combinatorial Theory, Series B, 105:1–5, 2014. doi: 10.1016/j.jctb.2013.12.002. 17

    work page doi:10.1016/j.jctb.2013.12.002 2014

  12. [12]

    Sidorenko

    Alexander Sidorenko. A correlation inequality for bipartite graphs.Graphs and Com- binatorics, 9(2):201–204, 1993. doi: 10.1007/BF02988307

    work page doi:10.1007/bf02988307 1993

  13. [13]

    Inequalities for doubly nonnegative functions.The Electronic Journal of Combinatorics, 28(1):Paper No

    Alexander Sidorenko. Inequalities for Doubly Nonnegative Functions.The Electronic Journal of Combinatorics, 28(1):#P1.32, 2021. doi: 10.37236/8947. 18 A Proof of the relations between the notions Proof of Theorem 1.4.For (1), letWbe aρ-locally dense graphon. TakingS= [0,1] in the definition of local density gives t(K2, W) = Z [0,1]2 W(x, y) dxdy≥ρ. IfGis ...

    work page doi:10.37236/8947 2021