Counting substructures. II: Hypergraphs

DOI10.1007/S00493-013-2638-2zbMATH Open1313.05275arXiv0905.1963OpenAlexW2108398244MaRDI QIDQ485550FDOQ485550

Authors: Dhruv Mubayi 

Publication date: 9 January 2015

Published in: Combinatorica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

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)