On \(K^ 4\)-free subgraphs of random graphs

DOI10.1007/BF01200906zbMath0889.05068DBLPjournals/combinatorica/KohayakawaLR97OpenAlexW2054018639WikidataQ97694944 ScholiaQ97694944MaRDI QIDQ1385983

Vojtěch Rödl, Tomasz Łuczak, Yoshiharu Kohayakawa

Publication date: 6 May 1998

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01200906

zbMATH Keywords

graphregularity lemmarandom graphTurán type problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Extremal combinatorics (05D99)

Related Items (45)

Corrádi and Hajnal's Theorem for Sparse Random Graphs ⋮ On the Minimum Degree of Minimal Ramsey Graphs for Cliques Versus Cycles ⋮ Extremal subgraphs of random graphs ⋮ Dirac-type theorems in random hypergraphs ⋮ Triangle-free subgraphs of random graphs ⋮ Small subsets inherit sparse \(\varepsilon\)-regularity ⋮ Mantel's theorem for random graphs ⋮ A new proof of the KŁR conjecture ⋮ Extremal results for random discrete structures ⋮ Combinatorial theorems in sparse random sets ⋮ The threshold bias of the clique-factor game ⋮ Turán's theorem for pseudo-random graphs ⋮ The size‐Ramsey number of cubic graphs ⋮ On an anti-Ramsey threshold for random graphs ⋮ Lower tails via relative entropy ⋮ Turán‐type problems for long cycles in random and pseudo‐random graphs ⋮ Simple Containers for Simple Hypergraphs ⋮ Independent Sets in Hypergraphs and Ramsey Properties of Graphs and the Integers ⋮ Extremal results in sparse pseudorandom graphs ⋮ Almost all Steiner triple systems are almost resolvable ⋮ On the cycle space of a random graph ⋮ On the KŁR conjecture in random graphs ⋮ An analogue of the Erdős-Gallai theorem for random graphs ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ Extremal results for odd cycles in sparse pseudorandom graphs ⋮ Erdős–Ko–Rado in Random Hypergraphs ⋮ \(K_4\)-free subgraphs of random graphs revisited ⋮ Hypergraph containers ⋮ Turánnical hypergraphs ⋮ Triangle-Free Subgraphs of Random Graphs ⋮ Relative Turán Problems for Uniform Hypergraphs ⋮ Stability results for random discrete structures ⋮ Unnamed Item ⋮ The typical structure of sparse $K_{r+1}$-free graphs ⋮ Many \(T\) copies in \(H\)-free graphs ⋮ On Erdős–Ko–Rado for Random Hypergraphs II ⋮ Triangle-free subgraphs of hypergraphs ⋮ On Erdős–Ko–Rado for random hypergraphs I ⋮ On Komlós’ tiling theorem in random graphs ⋮ A note on counting orientations ⋮ On an anti-Ramsey property of random graphs ⋮ Towards the Kohayakawa–Kreuter conjecture on asymmetric Ramsey properties ⋮ Independent sets in hypergraphs ⋮ Upper bounds on probability thresholds for asymmetric Ramsey properties ⋮ The regularity method for graphs with few 4‐cycles

Cites Work

• Unnamed Item
• Large triangle-free subgraphs in graphs without \(K_ 4\)
• An extremal problem for random graphs and the number of graphs with large even-girth
• Random Ramsey graphs for the four-cycle
• Turán's extremal problem in random graphs: Forbidding even cycles
• Turán's extremal problem in random graphs: Forbidding odd cycles
• Poisson approximation for large deviations
• Subgraphs of a hypercube containing no small even cycles
• Szemerédi’s Regularity Lemma for Sparse Graphs
• Extremal subgraphs of random graphs
• The Induced Size-Ramsey Number of Cycles
• Threshold Functions for Ramsey Properties
• Arithmetic progressions of length three in subsets of a random set

This page was built for publication: On \(K^ 4\)-free subgraphs of random graphs