Constructing dense grid-free linear 3-graphs

Gishboliner, Lior; Shapira, Asaf

doi:10.1090/proc/15673

Constructing dense grid-free linear $3$-graphs
HTML articles powered by AMS MathViewer

by Lior Gishboliner and Asaf Shapira PDF

Proc. Amer. Math. Soc. 150 (2022), 69-74 Request permission

Abstract:

We show that there exist linear $3$-uniform hypergraphs with $n$ vertices and $\Omega (n^2)$ edges which contain no copy of the $3 \times 3$ grid. This makes significant progress on a conjecture of Füredi and Ruszinkó. We also discuss connections to proving lower bounds for the $(9,6)$ Brown-Erdős-Sós problem and to a problem of Solymosi and Solymosi.

References

W. G. Brown, P. Erdős, and V. T. Sós, Some extremal problems on $r$-graphs, New directions in the theory of graphs (Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich., 1971) Academic Press, New York, 1973, pp. 53–63. MR 0351888
V. T. Sós, P. Erdős, and W. G. Brown, On the existence of triangulated spheres in $3$-graphs, and related problems, Period. Math. Hungar. 3 (1973), no. 3-4, 221–228. MR 323647, DOI 10.1007/BF02018585
D. Conlon, L. Gishboliner, Y. Levanzov, and A. Shapira, A new bound for the Brown–Erdos–Sós problem, preprint arXiv:1912.08834, 2019.
Zoltán Füredi and Miklós Ruszinkó, Uniform hypergraphs containing no grids, Adv. Math. 240 (2013), 302–324. MR 3046311, DOI 10.1016/j.aim.2013.03.009
Gennian Ge and Chong Shangguan, Sparse hypergraphs: new bounds and constructions, J. Combin. Theory Ser. B 147 (2021), 96–132. MR 4173984, DOI 10.1016/j.jctb.2020.10.003
A. Gyárfás and G. N. Sárközy, Turán and Ramsey numbers in linear triple systems, Discrete Mathematics, 344(3), p.112258, 2021.
I. Z. Ruzsa and E. Szemerédi, Triple systems with no six points carrying three triangles, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976) Colloq. Math. Soc. János Bolyai, vol. 18, North-Holland, Amsterdam-New York, 1978, pp. 939–945. MR 519318
Gábor N. Sárközy and Stanley Selkow, An extension of the Ruzsa-Szemerédi theorem, Combinatorica 25 (2005), no. 1, 77–84. MR 2109195, DOI 10.1007/s00493-005-0006-6
Chong Shangguan and Itzhak Tamo, Sparse hypergraphs with applications to coding theory, SIAM J. Discrete Math. 34 (2020), no. 3, 1493–1504. MR 4118679, DOI 10.1137/19M1248108
David Solymosi and Jozsef Solymosi, Small cores in 3-uniform hypergraphs, J. Combin. Theory Ser. B 122 (2017), 897–910. MR 3575235, DOI 10.1016/j.jctb.2016.11.001