Counting substructures. II: Hypergraphs

DOI10.1007/S00493-013-2638-2MaRDI QIDQ485550zbMATH OpenOpenAlexFDO

Authors Dhruv Mubayi

Publication date 9 January 2015

Published in Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

hypergraphshypergraph removal lemmacopies of graphs

Mathematics Subject Classification ID

Asymptotic enumeration (05A16) Enumeration in graph theory (05C30) Hypergraphs (05C65) Extremal set theory (05D05) Triple systems (05B07)

Abstract: For various triple systems $F$, we give tight lower bounds on the number of copies of $F$ in a triple system with a prescribed number of vertices and edges. These are the first such results for hypergraphs, and extend earlier theorems of Bollob'as, Frankl, F"uredi, Keevash, Pikhurko, Simonovits, and Sudakov who proved that there is one copy of $F$. A sample result is the following: F"uredi-Simonovits and independently Keevash-Sudakov settled an old conjecture of S'os by proving that the maximum number of triples in an $n$ vertex triple system (for $n$ sufficiently large and even) that contains no copy of the Fano plane is $p(n)=n/2choose2n.$ We prove that there is an absolute constant $c$ such that if $n$ is sufficiently large and $1leqlec{n}^2$, then every $n$ vertex triple system with $p(n)+q$ edges contains at least $6q(n/2choose4+(n/2-3)n/2choose3$$copiesoftheFanoplane.Thisissharpfor$qle n/2-2$. Our proofs use the recently proved hypergraph removal lemma and stability results for the corresponding Tur'an problem.

Recommendations

• On the number of copies of one hypergraph in another
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• The counting lemma for regular k‐uniform hypergraphs
• Graph removal lemmas
• Generalizations of the removal lemma

Cites work

• scientific article; zbMATH DE number 3821782 (Why is no real title available?)
• scientific article; zbMATH DE number 3561362 (Why is no real title available?)
• scientific article; zbMATH DE number 1496588 (Why is no real title available?)
• scientific article; zbMATH DE number 3262986 (Why is no real title available?)
• scientific article; zbMATH DE number 3188526 (Why is no real title available?)
• 4-books of three pages
• A hypergraph extension of Turán's theorem
• A new generalization of Mantel's theorem to \(k\)-graphs
• A new generalization of the Erdős-Ko-Rado theorem
• A variant of the hypergraph removal lemma
• An exact Turán result for the generalized triangle
• Applications of the regularity lemma for uniform hypergraphs
• Asymptotic solution of a Turán-type problem
• Counting substructures. I: Color critical graphs
• Hypergraph regularity and the multidimensional Szemerédi theorem
• On Triple Systems with Independent Neighbourhoods
• On a hypergraph Turán problem of Frankl
• On a theorem of Rademacher-Turán
• On the Minimal Density of Triangles in Graphs
• On the Turán number of triple systems
• Quadruple systems with independent neighborhoods
• Stability theorems for cancellative hypergraphs
• The Turán number of the Fano plane
• The counting lemma for regular k‐uniform hypergraphs
• The maximum size of 3-uniform hypergraphs not containing a Fano plane
• The number of cliques in graphs of given order and size
• Three-graphs without two triples whose symmetric difference is contained in a third
• Triple Systems Not Containing a Fano Configuration

Cited in

(5)

• Hypergraphs With Finitely Many Isomorphism Subtypes
• On the number of \(K_4\)-saturating edges
• Hypergraphs with no tight cycles
• Counting subgraphs in hyperbolic graphs with symmetry
• On the problem of finding small subdivision and homomorphism bases for classes of countable graphs

This page was built for publication: Counting substructures. II: Hypergraphs

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