Turánnical hypergraphs

DOI10.1002/RSA.20399MaRDI QIDQ4903276zbMATH OpenOpenAlexFDO

Authors

Publication date 21 January 2013

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

extremal combinatoricsrandom hypergraphsTurán's theorem

Mathematics Subject Classification ID

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

Abstract: This paper is motivated by the question of how global and dense restriction sets in results from extremal combinatorics can be replaced by less global and sparser ones. The result we consider here as an example is Turan's theorem, which deals with graphs G=([n],E) such that no member of the restriction set consisting of all r-tuples on [n] induces a copy of K_r. Firstly, we examine what happens when this restriction set is replaced just by all r-tuples touching a given m-element set. That is, we determine the maximal number of edges in an n-vertex such that no K_r hits a given vertex set. Secondly, we consider sparse random restriction sets. An r-uniform hypergraph R on vertex set [n] is called Turannical (respectively epsilon-Turannical), if for any graph G on [n] with more edges than the Turan number ex(n,K_r) (respectively (1+eps)ex(n,K_r), no hyperedge of R induces a copy of K_r in G. We determine the thresholds for random r-uniform hypergraphs to be Turannical and to epsilon-Turannical. Thirdly, we transfer this result to sparse random graphs, using techniques recently developed by Schacht [Extremal results for random discrete structures] to prove the Kohayakawa-Luczak-Rodl Conjecture on Turan's theorem in random graphs.

Recommendations

• scientific article; zbMATH DE number 5942358
• scientific article; zbMATH DE number 1439495
• A hypergraph extension of Turán's theorem
• Hypergraph Turán numbers of linear cycles
• Turán problems on non-uniform hypergraphs
• Hypergraph Turán numbers of vertex disjoint cycles
• The Turán density problem for hypergraphs
• The Turán problem for hypergraphs on fixed size
• Relative Turán numbers for hypergraph cycles

Cites work

• A combinatorial problem; stability and order for models and theories in infinitary languages
• Books versus triangles
• Erdős-Ko-Rado in random hypergraphs
• Hunting for sharp thresholds
• K₅‐free subgraphs of random graphs
• Large triangle-free subgraphs in graphs without \(K_ 4\)
• Local resilience of graphs
• On \(K^ 4\)-free subgraphs of random graphs
• On extremal subgraphs of random graphs
• On the density of families of sets
• On the structure of linear graphs
• Ramsey properties of random discrete structures
• Sharp thresholds of graph properties, and the k-sat problem
• Supersaturated graphs and hypergraphs
• The Turn Theorem for Random Graphs
• Threshold Functions for Ramsey Properties

Cited in

(10)

• Hypergraph Turán numbers of vertex disjoint cycles
• A randomized version of Ramsey's theorem
• scientific article; zbMATH DE number 5942358 (Why is no real title available?)
• Short proofs of some extremal results. III
• Combinatorial theorems in sparse random sets
• Turán's theorem in sparse random graphs
• An extension of Turán's theorem, uniqueness and stability
• Hypergraph Turán densities can have arbitrarily large algebraic degree
• Uniform chain decompositions and applications
• Random polynomial graphs for random Turán problems

This page was built for publication: Turánnical hypergraphs

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