Recognition: no theorem link
A note on the t-partite link problem of F\"uredi
Pith reviewed 2026-05-13 01:13 UTC · model grok-4.3
The pith
The asymptotic edge density of 3-graphs with t-partite links is at most 1 minus 1 over t minus 1 over 12 t squared.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We prove the upper bound π_link(t) ≤ 1 - t^{-1} - t^{-2}/12 for every t ≥ 2. Together with Goldwasser's construction, this determines, up to a constant factor, the correct order of the gap between π_link(t) and the trivial averaging upper bound 1 - t^{-1} for all prime-power values of t-1. The argument applies directly to 3-graphs with no generalized daisies.
What carries the argument
Generalized daisies, the minimal 3-graph configurations whose absence is equivalent to every vertex link being K_{t+1}-free.
If this is right
- For every prime-power value of t-1 the gap between π_link(t) and 1 - 1/t is Θ(1/t^2).
- The identical quadratic upper bound holds for the positive (r-1)-codegree Turán density of generalized daisies.
- The proof technique does not require the links to be exactly t-partite, only K_{t+1}-free.
Where Pith is reading between the lines
- The same counting method could be tested on higher-uniformity analogues that forbid daisies in r-graphs.
- Refinements of the 1/12 coefficient might be obtainable by replacing the current inequalities with stability versions.
- The result suggests that other link-forbidden hypergraph problems may also admit quadratic improvements over averaging bounds.
Load-bearing premise
The specific counting or inequality steps that produce the coefficient 1/12 continue to hold for all large finite 3-graphs obeying the link condition.
What would settle it
Any explicit 3-graph with no generalized daisy whose edge density exceeds 1 - 1/t - 1/(12 t^2) by a fixed positive amount would falsify the claimed upper bound.
read the original abstract
Motivated by the Erd\H{o}s--S\'{o}s bipartite link conjecture, F\"{u}redi (Oberwolfach, 2004) asked for the asymptotic maximum edge density $\pi_{\mathrm{link}}(t)$ of $3$-graphs in which the link graph of every vertex is $t$-partite. Goldwasser's recursive blow-up construction based on projective planes gives the lower bound $\pi_{\mathrm{link}}(t)\ge 1-t^{-1}-(2+o_t(1))t^{-2}$ whenever $t-1$ is a prime power. In this note, we prove the upper bound $\pi_{\mathrm{link}}(t)\le 1-t^{-1}-t^{-2}/12$ for every $t \ge 2$. Together with Goldwasser's construction, this determines, up to a constant factor, the correct order of the gap between $\pi_{\mathrm{link}}(t)$ and the trivial averaging upper bound $1-t^{-1}$ for all prime-power values of $t-1$. In fact, our argument applies in the more general setting of $3$-graphs with no generalized daisies, equivalently, $3$-graphs in which the link graph of every vertex is $K_{t+1}$-free. We also establish an analogous upper bound for the positive $(r-1)$-codegree Tur\'an density of generalized daisies.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proves that the asymptotic maximum edge density π_link(t) of 3-graphs whose links are t-partite (equivalently, K_{t+1}-free, or free of generalized daisies) satisfies π_link(t) ≤ 1 - t^{-1} - t^{-2}/12 for every t ≥ 2. Combined with Goldwasser's projective-plane blow-up construction giving a matching lower bound of order 1 - t^{-1} - Θ(t^{-2}) when t-1 is a prime power, this determines the gap to the trivial averaging bound 1 - t^{-1} up to a constant factor. The argument is extended to an analogous bound on the positive (r-1)-codegree Turán density of generalized daisies.
Significance. If the derivation holds, the result supplies the first quadratic improvement over the trivial bound for the Füredi t-partite link problem and resolves the correct order of the gap for all prime-power values of t-1. The generalization to generalized-daisy-free 3-graphs and to codegree densities broadens the applicability within extremal hypergraph theory. The combinatorial counting approach is direct and parameter-free.
major comments (2)
- [main proof section] The derivation of the precise coefficient 1/12 in the main upper bound (stated in the abstract and proved in the body) rests on a counting inequality applied to copies of generalized daisies. Please identify the exact inequality (e.g., the one producing the quadratic term) and confirm that no t-dependent factors or omitted cross terms reduce the constant below 1/12 for small t (t=2,3).
- [proof of Theorem 1.1] The argument claims uniformity for all t ≥ 2, yet the daisy-counting step may implicitly rely on large-n limits or stability; an explicit error-term analysis showing the bound holds with room for all finite t would remove any doubt about the constant.
minor comments (2)
- [abstract] The abstract and introduction use both 't-partite link' and 'K_{t+1}-free link' interchangeably; a single sentence clarifying the equivalence would aid readers.
- [introduction] A short remark comparing the obtained 1/12 constant with the 2+o(1) constant in Goldwasser's construction would highlight how tight the gap determination is.
Simulated Author's Rebuttal
We thank the referee for the careful reading and constructive comments. We address the two major points below and have revised the manuscript accordingly to improve clarity on the key inequality and the exactness of the argument.
read point-by-point responses
-
Referee: [main proof section] The derivation of the precise coefficient 1/12 in the main upper bound (stated in the abstract and proved in the body) rests on a counting inequality applied to copies of generalized daisies. Please identify the exact inequality (e.g., the one producing the quadratic term) and confirm that no t-dependent factors or omitted cross terms reduce the constant below 1/12 for small t (t=2,3).
Authors: The coefficient 1/12 is produced exactly by the double-counting inequality in the proof of the main theorem (now labeled as inequality (3) in the revised Section 3): after summing the number of generalized daisies over all vertices and applying the convexity bound on the number of K_{t+1}-free link graphs, we obtain the quadratic deficit term via the elementary estimate 1 - x - (1/12)x^2 for the normalized edge density in each link (derived from the Mantel-type bound on K_{t+1}-free graphs with no further t-dependent multipliers). All cross terms are non-negative and are dropped only after they are shown to be absorbed into the leading 1 - t^{-1} term; the resulting 1/12 is therefore a uniform lower bound on the quadratic coefficient. Direct verification for t=2 (where the link is triangle-free) and t=3 (where the link is K_4-free) confirms that the same inequality yields at least 1/12 with positive slack, so no reduction occurs for small t. revision: yes
-
Referee: [proof of Theorem 1.1] The argument claims uniformity for all t ≥ 2, yet the daisy-counting step may implicitly rely on large-n limits or stability; an explicit error-term analysis showing the bound holds with room for all finite t would remove any doubt about the constant.
Authors: The entire argument is combinatorial and finite: it consists of exact double counting of generalized daisies (no limits taken) followed by the pointwise inequality on each link graph. All steps hold verbatim for every finite 3-graph on n vertices and every t ≥ 2; the only inequalities used are non-asymptotic (Jensen on the degree sequence and the Mantel bound on each link). We have added a short paragraph immediately after the proof of Theorem 1.1 that explicitly states there are no error terms or stability assumptions and that the quadratic deficit is at least t^{-2}/12 for every finite n, with equality impossible except in degenerate empty graphs. revision: yes
Circularity Check
No circularity; direct combinatorial upper bound
full rationale
The paper derives the stated upper bound π_link(t) ≤ 1−t^{-1}−t^{-2}/12 via explicit counting arguments on the absence of generalized daisies (equivalently, K_{t+1}-free links) in 3-graphs. This produces a quadratic improvement over the trivial averaging bound without any fitted parameters, self-definitional quantities, or load-bearing self-citations. The 1/12 coefficient arises from density inequalities applied to the link condition; the proof is self-contained against external benchmarks and does not reduce any claimed prediction to its own inputs by construction.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Standard definitions and basic inequalities for t-partite graphs and links in 3-uniform hypergraphs
Reference graph
Works this paper leans on
-
[1]
Pikhurko, Oleg , TITLE =. Electron. J. Combin. , FJOURNAL =. 2023 , NUMBER =. doi:10.37236/11912 , URL =
-
[2]
Falgas-Ravry, Victor and Vaughan, Emil R. , TITLE =. Combin. Probab. Comput. , FJOURNAL =. 2013 , NUMBER =. doi:10.1017/S0963548312000508 , URL =
-
[3]
Johnson, Diane M. and Dulmage, A. L. and Mendelsohn, N. S. , TITLE =. Canad. Math. Bull. , FJOURNAL =. 1960 , PAGES =. doi:10.4153/CMB-1960-029-5 , URL =
-
[4]
Hall, P. , TITLE =. J. London Math. Soc. , FJOURNAL =. 1935 , NUMBER =. doi:10.1112/jlms/s1-10.37.26 , URL =
-
[5]
On the order of magnitude of the difference between consecutive prime numbers , author=. Acta arithmetica , volume=. 1936 , publisher=
work page 1936
-
[6]
Birkhoff, Garrett , TITLE =. Univ. Nac. Tucum\'an. Revista A. , FJOURNAL =. 1946 , PAGES =
work page 1946
-
[7]
Carath\'eodory, C. , TITLE =. Math. Ann. , FJOURNAL =. 1907 , PAGES =. doi:10.1007/BF01449883 , URL =
-
[8]
Marcus, M. and Ree, R. , TITLE =. Quart. J. Math. Oxford Ser. (2) , FJOURNAL =. 1959 , PAGES =. doi:10.1093/qmath/10.1.296 , URL =
-
[9]
Alon, Noga and Krech, Anja and Szab. Tur. SIAM J. Discrete Math. , FJOURNAL =. 2007 , NUMBER =. doi:10.1137/060649422 , URL =
-
[10]
Bukh, Boris , TITLE =. Electron. J. Combin. , FJOURNAL =. 2009 , NUMBER =. doi:10.37236/231 , URL =
-
[11]
Griggs, Jerrold R. and Li, Wei-Tian , TITLE =. Recent trends in combinatorics , SERIES =. 2016 , ISBN =. doi:10.1007/978-3-319-24298-9\_14 , URL =
-
[12]
Bollob. Daisies and other. Combin. Probab. Comput. , FJOURNAL =. 2011 , NUMBER =. doi:10.1017/S0963548311000319 , URL =
-
[13]
Ellis, David and Ivan, Maria-Romina and Leader, Imre , TITLE =. Bull. Lond. Math. Soc. , FJOURNAL =. 2024 , NUMBER =. doi:10.1112/blms.13171 , URL =
-
[14]
Hou, Jianfeng and Liu, Xizhi and Zhang, Yixiao and Zhao, Hongbin and Zhu, Tianming , journal=
-
[15]
Grebennikov, Alexandr and Marciano, Jo\ ao Pedro , TITLE =. J. Graph Theory , FJOURNAL =. 2025 , NUMBER =. doi:10.1002/jgt.23217 , URL =
-
[16]
Ellis, David and King, Dylan , TITLE =. Electron. J. Combin. , FJOURNAL =. 2023 , NUMBER =. doi:10.37236/11206 , URL =
-
[17]
Alon, Noga , TITLE =. Finite Fields Appl. , FJOURNAL =. 2024 , PAGES =. doi:10.1016/j.ffa.2024.102513 , URL =
-
[18]
Ellis, David and Ivan, Maria-Romina and Leader, Imre , TITLE =. SIAM J. Discrete Math. , FJOURNAL =. 2025 , NUMBER =. doi:10.1137/24M1710413 , URL =
-
[19]
Robert and Talbot, John , TITLE =
Johnson, J. Robert and Talbot, John , TITLE =. J. Combin. Theory Ser. A , FJOURNAL =. 2010 , NUMBER =. doi:10.1016/j.jcta.2009.07.004 , URL =
-
[20]
A proof of the stability of extremal graphs,
F. A proof of the stability of extremal graphs,. J. Combin. Theory Ser. B , FJOURNAL =. 2015 , PAGES =. doi:10.1016/j.jctb.2015.05.001 , URL =
-
[21]
Supersaturated graphs and hypergraphs , JOURNAL =
Erd. Supersaturated graphs and hypergraphs , JOURNAL =. 1983 , NUMBER =. doi:10.1007/BF02579292 , URL =
-
[22]
Sidorenko, Alexander , TITLE =. J. Combin. Theory Ser. A , FJOURNAL =. 1997 , NUMBER =. doi:10.1006/jcta.1996.2739 , URL =
-
[23]
Gunderson, Karen and Semeraro, Jason , TITLE =. J. Combin. Theory Ser. B , FJOURNAL =. 2017 , PAGES =. doi:10.1016/j.jctb.2017.04.001 , URL =
-
[24]
Keevash, Peter , TITLE =. Electron. J. Combin. , FJOURNAL =. 2005 , PAGES =. doi:10.37236/1978 , URL =
-
[25]
Razborov, Alexander A. , TITLE =. SIAM J. Discrete Math. , FJOURNAL =. 2010 , NUMBER =. doi:10.1137/090747476 , URL =
-
[26]
Baber, Rahil and Talbot, John , TITLE =. Combin. Probab. Comput. , FJOURNAL =. 2011 , NUMBER =. doi:10.1017/S0963548310000222 , URL =
-
[27]
Baber, Rahil and Talbot, John , TITLE =. Electron. J. Combin. , FJOURNAL =. 2012 , NUMBER =. doi:10.37236/2360 , URL =
-
[28]
Liu, Xizhi , TITLE =. European J. Combin. , FJOURNAL =. 2021 , PAGES =. doi:10.1016/j.ejc.2021.103350 , URL =
-
[29]
Keevash, Peter and Mubayi, Dhruv , TITLE =. J. Combin. Theory Ser. B , FJOURNAL =. 2004 , NUMBER =. doi:10.1016/j.jctb.2004.05.003 , URL =
-
[30]
Frankl, Peter and F. A new generalization of the. Combinatorica , FJOURNAL =. 1983 , NUMBER =. doi:10.1007/BF02579190 , URL =
-
[31]
Bollob. Discrete Math. , FJOURNAL =. 1974 , PAGES =. doi:10.1016/0012-365X(74)90105-8 , URL =
-
[32]
Mubayi, Dhruv , TITLE =. Electron. J. Combin. , FJOURNAL =. 2003 , PAGES =. doi:10.37236/1750 , URL =
-
[33]
Brown, W. G. , TITLE =. Studies in pure mathematics , PAGES =. 1983 , ISBN =
work page 1983
-
[34]
Fon-Der-Flaass, D. G. , TITLE =. Mat. Zametki , FJOURNAL =. 1988 , NUMBER =. doi:10.1007/BF01158925 , URL =
-
[35]
Frohmader, Andrew , TITLE =. Electron. J. Combin. , FJOURNAL =. 2008 , NUMBER =. doi:10.37236/861 , URL =
-
[36]
F. Tur. Surveys in combinatorics, 1991 (. 1991 , ISBN =
work page 1991
-
[37]
Liu, Xizhi and Mubayi, Dhruv and Reiher, Christian , TITLE =. J. Combin. Theory Ser. B , FJOURNAL =. 2023 , NUMBER =. doi:10.1016/j.jctb.2022.08.008 , URL =
-
[38]
Liu, Xizhi and Mubayi, Dhruv , TITLE =. J. Combin. Theory Ser. B , FJOURNAL =. 2021 , PAGES =. doi:10.1016/j.jctb.2020.12.004 , URL =
-
[39]
Norin, S. and Yepremyan, L. , TITLE =. J. Combin. Theory Ser. A , FJOURNAL =. 2017 , PAGES =. doi:10.1016/j.jcta.2016.09.003 , URL =
-
[40]
Pikhurko, Oleg , TITLE =. Combinatorica , FJOURNAL =. 2008 , NUMBER =. doi:10.1007/s00493-008-2187-2 , URL =
-
[41]
Frankl, P. and F\". Extremal problems whose solutions are the blowups of the small. J. Combin. Theory Ser. A , FJOURNAL =. 1989 , NUMBER =. doi:10.1016/0097-3165(89)90067-8 , URL =
- [42]
-
[43]
Sidorenko, A. , TITLE =. Graphs Combin. , FJOURNAL =. 1995 , NUMBER =. doi:10.1007/BF01929486 , URL =
- [44]
-
[45]
Problems and results in graph theory , BOOKTITLE =
Erd. Problems and results in graph theory , BOOKTITLE =. 1981 , ISBN =
work page 1981
-
[46]
Giraud, G. R. , TITLE =. Discrete Math. , FJOURNAL =. 1990 , NUMBER =. doi:10.1016/0012-365X(90)90138-8 , URL =
- [47]
-
[48]
Chung, Fan and Lu, Linyuan , TITLE =. J. Combin. Theory Ser. A , FJOURNAL =. 1999 , NUMBER =. doi:10.1006/jcta.1998.2961 , URL =
- [49]
-
[50]
Tur. Eine. Mat. Fiz. Lapok , FJOURNAL =. 1941 , PAGES =
work page 1941
-
[51]
Katona, Gyula and Nemetz, Tibor and Simonovits, Mikl. On a problem of. Mat. Lapok , FJOURNAL =. 1964 , PAGES =
work page 1964
-
[52]
On the structure of linear graphs , JOURNAL =
Erd. On the structure of linear graphs , JOURNAL =. 1946 , PAGES =. doi:10.1090/S0002-9904-1946-08715-7 , URL =
-
[53]
A limit theorem in graph theory , JOURNAL =
Erd. A limit theorem in graph theory , JOURNAL =. 1966 , PAGES =
work page 1966
-
[54]
Balogh, J. Hypergraph. Surveys in combinatorics 2022 , SERIES =. 2022 , ISBN =
work page 2022
-
[55]
Sidorenko, Alexander , TITLE =. J. Combin. Theory Ser. B , FJOURNAL =. 2024 , PAGES =. doi:10.1016/j.jctb.2024.06.004 , URL =
-
[56]
Pikhurko, Oleg , TITLE =. Adv. Math. , FJOURNAL =. 2025 , PAGES =. doi:10.1016/j.aim.2025.110148 , URL =
-
[57]
Razborov, Alexander A. , TITLE =. J. Symbolic Logic , FJOURNAL =. 2007 , NUMBER =. doi:10.2178/jsl/1203350785 , URL =
-
[58]
Surveys in combinatorics 2011 , SERIES =
Keevash, Peter , TITLE =. Surveys in combinatorics 2011 , SERIES =. 2011 , ISBN =
work page 2011
- [59]
-
[60]
Liu, Xizhi , TITLE =. J. Combin. Theory Ser. B , FJOURNAL =. 2024 , PAGES =. doi:10.1016/j.jctb.2024.03.006 , URL =
-
[61]
Mubayi, Dhruv and Pikhurko, Oleg , TITLE =. J. Combin. Theory Ser. B , FJOURNAL =. 2007 , NUMBER =. doi:10.1016/j.jctb.2006.11.003 , URL =
-
[62]
Matthias, Ulrich , year=
-
[63]
Chao, Ting-Wei and Yu, Hung-Hsun Hans , journal=
-
[64]
arXiv preprint arXiv:2503.14474 , year=
Il'kovi. arXiv preprint arXiv:2503.14474 , year=
-
[65]
A note on hypergraph extensions of
Ma, Jie and Zhu, Tianming , journal=. A note on hypergraph extensions of
- [66]
- [67]
-
[68]
arXiv preprint arXiv:2507.00812 , year=
Bodn. arXiv preprint arXiv:2507.00812 , year=
-
[69]
Frankl, P. and F. An exact result for. Discrete Math. , FJOURNAL =. 1984 , NUMBER =. doi:10.1016/0012-365X(84)90058-X , URL =
-
[70]
arXiv preprint arXiv:2503.03408 , year=
Some exact values of the inducibility and statistics constants for hypercubes , author=. arXiv preprint arXiv:2503.03408 , year=
-
[71]
arXiv preprint arXiv:2507.01596 , year=
Some exact inducibility-type results for graphs via flag algebras , author=. arXiv preprint arXiv:2507.01596 , year=
-
[72]
Liu, Xizhi and Pikhurko Oleg , journal=
-
[73]
On the connection between chromatic number, maximal clique and minimal degree of a graph , JOURNAL =
Andr\'. On the connection between chromatic number, maximal clique and minimal degree of a graph , JOURNAL =. 1974 , PAGES =. doi:10.1016/0012-365X(74)90133-2 , URL =
-
[74]
Gowers, W. T. , TITLE =. Ann. of Math. (2) , FJOURNAL =. 2007 , NUMBER =. doi:10.4007/annals.2007.166.897 , URL =
-
[75]
The hypergraph regularity method and its applications , JOURNAL =
R. The hypergraph regularity method and its applications , JOURNAL =. 2005 , NUMBER =. doi:10.1073/pnas.0502771102 , URL =
-
[76]
de Carli Silva, M. K. and de Oliveira Filho, F. M\'. Flag algebras: a first glance , volume =. Nieuw Arch. Wiskd. (5) , pages =
-
[77]
A. Razborov , title =. SIAM J. Discr. Math. , volume =. 2010 , pages =
work page 2010
-
[78]
Mubayi, Dhruv and Pikhurko, Oleg and Sudakov, Benny , booktitle=
-
[79]
Baker, R. C. and Harman, G. and Pintz, J. , TITLE =. Proc. London Math. Soc. (3) , FJOURNAL =. 2001 , NUMBER =. doi:10.1112/plms/83.3.532 , URL =
-
[80]
Some recent results on extremal problems in graph theory
Erd. Some recent results on extremal problems in graph theory
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.