Triangle-free subgraphs of hypergraphs

DOI10.1007/S00373-021-02388-5MaRDI QIDQ2053717zbMATH OpenOpenAlexFDO

Authors Jiaxi Nie, Sam Spiro, J. Verstraëte

Publication date 30 November 2021

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

hypergraph containerloose trianglemaximum degreerandom hypergraph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80)

Abstract: In this paper, we consider an analog of the well-studied extremal problem for triangle-free subgraphs of graphs for uniform hypergraphs. A loose triangle is a hypergraph $T$ consisting of three edges $e,f$ and $g$ such that $|ecapf|=|fcapg|=|gcape|=1$ and $ecapfcapg=emptyset$. We prove that if $H$ is an $n$-vertex $r$-uniform hypergraph with maximum degree $riangle$, then as $riangleightarrowinfty$, the number of edges in a densest $T$-free subhypergraph of $H$ is at least [ frac{e(H)}{ riangle^{frac{r-2}{r-1} + o(1)}}.] For $r=3$, this is tight up to the $o(1)$ term in the exponent. We also show that if $H$ is a random $n$-vertex triple system with edge-probability $p$ such that $p{n}^{3}ightarrowinfty$ as $nightarrowinfty$, then with high probability as $nightarrowinfty$, the number of edges in a densest $T$-free subhypergraph is [ minBigl{(1-o(1))p{nchoose3},p^{frac{1}{3}}n^{2-o(1)}Bigr}.] We use the method of containers together with probabilistic methods and a connection to the extremal problem for arithmetic progressions of length three due to Ruzsa and Szemer'{e}di.

Recommendations

• List coloring triangle-free hypergraphs
• The independent neighborhoods process
• Hypergraph Ramsey numbers: triangles versus cliques
• Counting Independent Sets in Hypergraphs
• The number of the maximal triangle-free graphs

Cites work

• An extremal problem for random graphs and the number of graphs with large even-girth
• An extremal theorem in the hypercube
• Combinatorial theorems in sparse random sets
• Erdős-Ko-Rado in random hypergraphs
• Exact solution of some Turán-type problems
• Extremal results for random discrete structures
• scientific article; zbMATH DE number 3609704 (Why is no real title available?)
• scientific article; zbMATH DE number 903456 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• Hypergraph containers
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Large subgraphs without short cycles
• Mantel's theorem for random graphs
• On \(K^ 4\)-free subgraphs of random graphs
• On Certain Sets of Integers
• On the combinatorial problems which I would most like to see solved
• On the triangle space of a random graph
• Ramsey properties of random discrete structures
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• The history of degenerate (bipartite) extremal graph problems
• The method of hypergraph containers
• The number of \(C_{2\ell}\)-free graphs
• The number of \(K_{s,t}\)-free graphs
• The number of hypergraphs without linear cycles
• The probabilistic method

Cited in

(8)

• Some induced subgraphs of strongly regular graphs with no triangles
• Triforce and corners
• Counting hypergraphs with large girth
• Random polynomial graphs for random Turán problems
• Turán theorems for even cycles in random hypergraph
• Sidorenko hypergraphs and random Turán numbers
• Random Turán theorem for expansions of spanning subgraphs of tight trees
• Supersaturation of odd linear cycles

This page was built for publication: Triangle-free subgraphs of hypergraphs

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