Regular pairs in sparse random graphs I

DOI10.1002/rsa.10081zbMath1022.05076OpenAlexW1996372165WikidataQ105583188 ScholiaQ105583188MaRDI QIDQ4419289

Yoshiharu Kohayakawa, Vojtěch Rödl

Publication date: 31 July 2003

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

Full work available at URL: https://doi.org/10.1002/rsa.10081

zbMATH Keywords

random graphsregularity lemmasparse graphsepsilon-regular

Mathematics Subject Classification ID

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

Related Items

Corrádi and Hajnal's Theorem for Sparse Random Graphs ⋮ On the size-Ramsey number of grid graphs ⋮ Embedding graphs with bounded degree in sparse pseudorandom graphs ⋮ Small subsets inherit sparse \(\varepsilon\)-regularity ⋮ Turán's theorem for pseudo-random graphs ⋮ Sparse partition universal graphs for graphs of bounded degree ⋮ Extremal results in sparse pseudorandom graphs ⋮ Threshold behavior of multi-path random key pre-distribution for sparse wireless sensor networks ⋮ On the KŁR conjecture in random graphs ⋮ FORCING QUASIRANDOMNESS WITH TRIANGLES ⋮ \(K_4\)-free subgraphs of random graphs revisited ⋮ An approximate version of the Loebl-Komlós-Sós conjecture ⋮ A note on the Size-Ramsey number of long subdivisions of graphs ⋮ Asymmetric Ramsey properties of random graphs involving cliques ⋮ The tripartite Ramsey number for trees ⋮ Discrepancy and eigenvalues of Cayley graphs ⋮ Almost spanning subgraphs of random graphs after adversarial edge removal ⋮ On an anti-Ramsey property of random graphs ⋮ Short paths in \(\varepsilon \)-regular pairs and small diameter decompositions of dense graphs ⋮ Independent sets in hypergraphs ⋮ The poset of hypergraph quasirandomness ⋮ Upper bounds on probability thresholds for asymmetric Ramsey properties

Cites Work

• Large triangle-free subgraphs in graphs without \(K_ 4\)
• On universality of graphs with uniformly distributed edges
• Expanding graphs contain all small trees
• Explicit construction of linear sized tolerant networks
• The number of submatrices of a given type in a Hadamard matrix and related results
• Three hundred million points suffice
• Erratum: ``Three hundred million points suffice
• On the combinatorial problems which I would most like to see solved
• The size Ramsey number
• An extremal problem for random graphs and the number of graphs with large even-girth
• Random Ramsey graphs for the four-cycle
• Ramsey properties of random hypergraphs
• Sparse quasi-random graphs
• Turán's extremal problem in random graphs: Forbidding even cycles
• Turán's extremal problem in random graphs: Forbidding odd cycles
• Random graphs with monochromatic triangles in every edge coloring
• The Algorithmic Aspects of the Regularity Lemma
• Szemerédi’s Regularity Lemma for Sparse Graphs
• Rado Partition Theorem for Random Subsets of Integers
• Sharp thresholds for certain Ramsey properties of random graphs
• Hypergraph Packing and Graph Embedding
• On size Ramsey number of paths, trees, and circuits. I
• A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
• The Induced Size-Ramsey Number of Cycles
• Threshold Functions for Ramsey Properties
• Arithmetic progressions of length three in subsets of a random set
• Some remarks on the theory of graphs
• Quasi-random graphs
• On size Ramsey numbers of graphs with bounded degree
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Regular pairs in sparse random graphs I