Extremal results in random graphs

DOI10.1007/978-3-642-39286-3_20MaRDI QIDQ5416091zbMATH OpenOpenAlexWikidataFDO

Authors Vojtěch Rödl, M. Schacht

Publication date 19 May 2014

Published in Bolyai Society Mathematical Studies (Search for Journal in Brave)

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

zbMATH Keywords

cliquescoloringextremal graphrandom graphTurán's theorem

Mathematics Subject Classification ID

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

Abstract: According to Paul ErdH{o}s [Some notes on Tur'an's mathematical work, J. Approx. Theory 29 (1980), page 4] it was Paul Tur'an who "created the area of extremal problems in graph theory". However, without a doubt, Paul ErdH{o}s popularized extremal combinatorics, by his many contributions to the field, his numerous questions and conjectures, and his influence on discrete mathematicians in Hungary and all over the world. In fact, most of the early contributions in this field can be traced back to Paul ErdH{o}s, Paul Tur'an, as well as their collaborators and students. Paul ErdH{o}s also established the probabilistic method in discrete mathematics, and in collaboration with Alfr'ed R'enyi, he started the systematic study of random graphs. We shall survey recent developments at the interface of extremal combinatorics and random graph theory.

Recommendations

• Extremal subgraphs of random graphs
• Turán's theorem in sparse random graphs
• On \(K^ 4\)-free subgraphs of random graphs
• Mantel's theorem for random graphs
• Combinatorial theorems in sparse random sets

Cited in

(32)

• An extremal problem for random graphs and the number of graphs with large even-girth
• An analogue of the Erdős-Gallai theorem for random graphs
• Extremal paths in inhomogenous random graphs
• Extremal cuts of sparse random graphs
• On random subgraphs of Kneser and Schrijver graphs
• The typical structure of sparse \(K_{r+1}\)-free graphs
• On ``stability in the Erdős-Ko-Rado theorem
• The number of \(C_{2\ell}\)-free graphs
• A detailed investigation into near degenerate exponential random graphs
• Extreme degrees in random subgraphs of regular graphs
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Transference for the Erdős-Ko-Rado theorem
• Graph limits and exchangeable random graphs
• Stability-type results for hereditary properties
• scientific article; zbMATH DE number 3961650 (Why is no real title available?)
• Extreme degrees in random graphs
• On an anti-Ramsey threshold for random graphs
• Turán's theorem in sparse random graphs
• A short nonalgorithmic proof of the containers theorem for hypergraphs
• On the cycle space of a random graph
• Extremal subgraphs of random graphs
• On Erdős-Ko-Rado for random hypergraphs. II
• Expected Maximum Block Size in Critical Random Graphs
• On Erdős-Ko-Rado for random hypergraphs. I
• Stability results for random discrete structures
• Random polynomial graphs for random Turán problems
• Turán theorems for even cycles in random hypergraph
• Dense circuit graphs and the planar Turán number of a cycle
• On the number of \(\mathcal{H}\)-free hypergraphs
• The planar Turán number of \({\left \{ C_6, C_7 \right \}}\)
• Planar Turán number of the 7-cycle
• A sharp threshold for a random version of Sperner's theorem

This page was built for publication: Extremal results in random graphs

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