Constructing dense grid-free linear 3-graphs

DOI10.1090/PROC/15673MaRDI QIDQ5164032zbMATH OpenOpenAlexFDO

Authors Lior Gishboliner, Asaf Shapira

Publication date 9 November 2021

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2010.14469

zbMATH Keywords

Brown-Erdős-Sós conjecturecores in hypergraphshypergraph regularity

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Hypergraphs (05C65)

Abstract: We show that there exist linear $3$-uniform hypergraphs with $n$ vertices and $Omega(n^2)$ edges which contain no copy of the $3imes3$ grid. This makes significant progress on a conjecture of F"{u}redi and Ruszink'{o}. We also discuss connections to proving lower bounds for the $(9,6)$ Brown-ErdH{o}s-S'{o}s problem and to a problem of Solymosi and Solymosi.

Recommendations

• Uniform hypergraphs containing no grids
• Superimposed codes and hypergraphs containing no grids.
• On an extremal hypergraph problem of Brown, Erdős and Sós
• Sparse hypergraphs: new bounds and constructions

Cites work

• An extension of the Ruzsa-Szemerédi theorem
• scientific article; zbMATH DE number 3609704 (Why is no real title available?)
• scientific article; zbMATH DE number 3407723 (Why is no real title available?)
• On the existence of triangulated spheres in 3-graphs, and related problems
• Small cores in 3-uniform hypergraphs
• Sparse hypergraphs with applications to coding theory
• Sparse hypergraphs: new bounds and constructions
• Turán and Ramsey numbers in linear triple systems
• Uniform hypergraphs containing no grids

Cited in

(8)

• A new bound for the Brown-Erdős-Sós problem
• The linear Turán number of small triple systems or why is the wicket interesting?
• Uniform hypergraphs containing no grids
• A note on the Brown-Erdős-Sós conjecture in groups
• Superimposed codes and hypergraphs containing no grids.
• The Turán number of the grid
• Local-vs-global combinatorics
• On the structure of pointsets with many collinear triples

This page was built for publication: Constructing dense grid-free linear 3-graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5164032)