Geodesic
Finite Hypergraph Families with Rich Extremal Turán Constructions via Mixing Patterns
Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e53

Voir la notice de l'article provenant de la source Cambridge University Press

We prove that, for any finite set of minimal r-graph patterns, there is a finite family $\mathcal F$ of forbidden r-graphs such that the extremal Turán constructions for $\mathcal F$ are precisely the maximum r-graphs obtainable from mixing the given patterns in any way via blowups and recursion. This extends the result by the second author [30], where the above statement was established for a single pattern.We present two applications of this result. First, we construct a finite family $\mathcal F$ of $3$-graphs such that there are exponentially many maximum $\mathcal F$-free $3$-graphs of each large order n and, moreover, the corresponding Turán problem is not finitely stable. Second, we show that there exists a finite family $\mathcal {F}$ of $3$-graphs whose feasible region function attains its maximum on a Cantor-type set of positive Hausdorff dimension. 
Liu, Xizhi; Pikhurko, Oleg. Finite Hypergraph Families with Rich Extremal Turán Constructions via Mixing Patterns. Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e53. doi: 10.1017/fms.2025.12
@article{10_1017_fms_2025_12,
     author = {Liu, Xizhi and Pikhurko, Oleg},
     title = {Finite {Hypergraph} {Families} with {Rich} {Extremal} {Tur\'an} {Constructions} via {Mixing} {Patterns}},
     journal = {Forum of Mathematics, Sigma},
     pages = {e53},
     year = {2025},
     volume = {13},
     number = {1},
     doi = {10.1017/fms.2025.12},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.12/}
}
TY  - JOUR
AU  - Liu, Xizhi
AU  - Pikhurko, Oleg
TI  - Finite Hypergraph Families with Rich Extremal Turán Constructions via Mixing Patterns
JO  - Forum of Mathematics, Sigma
PY  - 2025
SP  - e53
VL  - 13
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.12/
DO  - 10.1017/fms.2025.12
ID  - 10_1017_fms_2025_12
ER  - 
%0 Journal Article
%A Liu, Xizhi
%A Pikhurko, Oleg
%T Finite Hypergraph Families with Rich Extremal Turán Constructions via Mixing Patterns
%J Forum of Mathematics, Sigma
%D 2025
%P e53
%V 13
%N 1
%U http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.12/
%R 10.1017/fms.2025.12
%F 10_1017_fms_2025_12

[1] Baber, R. and Talbot, J., ‘Hypergraphs do jump’, Combin. Probab. Comput. 20(2) (2011), 161–171. Google Scholar | DOI

[2] Balogh, J., Clemen, F. C. and Luo, H., ‘Non-degenerate hypergraphs with exponentially many extremal constructions’, Preprint, 2022, . Google Scholar | arXiv

[3] Brown, W. G., ‘On an open problem of Paul Turán concerning 3-graphs’, in Studies in Pure Mathematics (Birkhäuser, Basel, 1983), 91–93. Google Scholar | DOI

[4] Cvetkovski, Z., Inequalities (Springer, Heidelberg, 2012). Theorems, techniques and selected problems. Google Scholar | DOI

[5] Erdős, P., ‘On extremal problems of graphs and generalized graphs’, Israel J. Math. 2 (1964), 183–190. Google Scholar | DOI

[6] Erdős, P., ‘Some recent results on extremal problems in graph theory. Results’, in Theory of Graphs (Internat. Sympos., Rome, 1966) (Gordon and Breach, New York, 1967), 117–123 (English); 124–130 (French). Google Scholar

[7] Erdős, P., ‘On the combinatorial problems I would most like to see solved’, Combinatorica 1 (1981), 25–42. Google Scholar | DOI

[8] Erdős, P. and Simonovits, M., ‘A limit theorem in graph theory’, Stud. Sci. Math. Hungar. 1 (1966), 51–57. Google Scholar

[9] Erdős, P. and Stone, A. H., ‘On the structure of linear graphs’, Bull. Amer. Math. Soc. 52 (1946), 1087–1091. Google Scholar | DOI

[10] Flaass, D. G. Fon-Der, ‘A method for constructing -graphs’, Mat. Zametki 44 (1988), 546–550. Google Scholar

[11] Frankl, P. and Füredi, Z., ‘An exact result for 3-graphs’, Discrete Math. 50 (1984), 323–328. Google Scholar | DOI

[12] Frankl, P., Peng, Y., Rödl, V. and Talbot, J., ‘A note on the jumping constant conjecture of Erdős’ J. Combin. Theory (B) 97 (2007), 204–216. Google Scholar | DOI

[13] Frankl, P. and Rödl, V., ‘Hypergraphs do not jump’, Combinatorica 4(2–3) (1984), 149–159. Google Scholar | DOI

[14] Frohmader, A., ‘More constructions for Turán’s -conjecture’, Electron. J. Combin. 15(1) (2008), Research Paper 137, 23. Google Scholar | DOI

[15] Hou, J., Li, H., Liu, X., Mubayi, D. and Zhang, Y., ‘Hypergraphs with infinitely many extremal constructions’, Discrete Anal. (2023), Paper No. 18, 34. Google Scholar

[16] Hutchinson, J. E., ‘Fractals and self-similarity’, Indiana Univ. Math. J. 30(5) (1981), 713–747. Google Scholar | DOI

[17] Katona, G., ‘A theorem of finite sets’, in Theory of Graphs (Proc. Colloq., Tihany, 1966) (Academic Press, New York-London, 1968), 187–207. Google Scholar

[18] Katona, G. O. H., Nemetz, T. and Simonovits, M., ‘On a graph problem of Turán (In Hungarian)’, Mat. Fiz. Lapok 15 (1964), 228–238. Google Scholar

[19] Keevash, P., ‘Hypergraph Turán problems’, in Surveys in Combinatorics 2011 (London Math. Soc. Lecture Note Ser.) vol. 392 (Cambridge Univ. Press, Cambridge, 2011), 83–139. Google Scholar | DOI

[20] Keevash, P., ‘Counting designs’, J. Europ. Math. Soc. 20 (2018), 903–927. Google Scholar | DOI

[21] Kirkman, T. P., ‘On a problem in combinations’, Cambridge and Dublin Math. J. 2 (1847), 191–204. Google Scholar

[22] Kostochka, A. V., ‘A class of constructions for Turán’s (3,4)-problem’, Combinatorica 2 (1982), 187–192. Google Scholar | DOI

[23] Kruskal, J. B., ‘The number of simplices in a complex’, in Mathematical Optimization Techniques (Univ. of California Press, Berkeley, CA, 1963), 251–278. Google Scholar

[24] Liu, X., ‘Cancellative hypergraphs and Steiner triple systems’, J. Combin. Theory Ser. B 167 (2024), 303–337, Google Scholar | DOI

[25] Liu, X. and Mubayi, D., ‘The feasible region of hypergraphs’, J. Comb. Theory, Ser. B 148 (2021), 23–59. Google Scholar | DOI

[26] Liu, X. and Mubayi, D., ‘A hypergraph Turán problem with no stability’, Combinatorica (2022), 1–30. Google Scholar

[27] Liu, X., Mubayi, D. and Reiher, C., ‘Hypergraphs with many extremal configurations ’, to appear, Israel. J. Math. Google Scholar

[28] Motzkin, T. S. and Straus, E. G., ‘Maxima for graphs and a new proof of a theorem of Turán’, Canadian J. Math. 17 (1965), 533–540. Google Scholar | DOI

[29] Norin, S. and Yepremyan, L., ‘Turán number of generalized triangles’, J. Combin. Theory (A) 146 (2017), 312–343. Google Scholar | DOI

[30] Pikhurko, O., ‘On possible Turán densities’, Israel J. Math. 201(1) (2014), 415–454. Google Scholar | DOI

[31] Pikhurko, O., ‘The maximal length of a gap between -graph Turán densities’, Electronic J. Combin. 22 (2015), 7pp. Google Scholar | DOI

[32] Pikhurko, O., Sliacǎn, J. and Tyros, K., ‘Strong forms of stability from flag algebra calculations’, J. Combin. Theory (B) 135 (2019), 129–178. Google Scholar | DOI

[33] Rödl, V. and Schacht, M., ‘Generalizations of the removal lemma’, Combinatorica 29(4) (2009), 467–501. Google Scholar | DOI

[34] Sidorenko, A., ‘What we know and what we do not know about Turán numbers’, Graphs Combin. 11(2) (1995), 179–199. Google Scholar | DOI

[35] Simonovits, M., ‘A method for solving extremal problems in graph theory, stability problems’, in Theory of Graphs (Proc. Colloq., Tihany, 1966) (Academic Press, New York, 1968), 279–319. Google Scholar

[36] Turán, P., ‘On an extremal problem in graph theory (in Hungarian)’, Mat. Fiz. Lapok 48 (1941), 436–452. Google Scholar

[37] Yan, Z. and Peng, Y., ‘Non-jumping Turán densities of hypergraphs’, Discrete Math. 346(1) (2023), Paper No. 113195, 11. Google Scholar

Cité par Sources :