Embedding graphs with bounded degree in sparse pseudorandom graphs

DOI10.1007/BF02787543MaRDI QIDQ1885587zbMATH OpenOpenAlexWikidataFDO

Authors Yoshiharu Kohayakawa, Vojtěch Rödl, Papa A. Sissokho

Publication date 11 November 2004

Published in Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02787543, https://doi-org.ez67.periodicos.capes.gov.br/10.1007/BF02787543

zbMATH Keywords

graph embeddingquasi-random graphtriangle-free graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Random graphs (graph-theoretic aspects) (05C80)

Review text

A quasi-random graph sequence \(G(n)\) is defined consisting of sparse graphs of increasing order \(n\). Conditions are given to find in \(G(n)\) the asymptotic number of labeled copies of a fixed triangle-free graph \(H\).

Recommendations

• Embedding large graphs into a random graph
• Triangle factors in sparse pseudo-random graphs
• Embedding nearly-spanning bounded degree trees
• Quasi-randomness and the distribution of copies of a fixed graph
• An improved upper bound on the density of universal random graphs

Cites work

• A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
• An Optimal Algorithm for Checking Regularity
• Eigenvalues and expanders
• Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
• Explicit construction of linear sized tolerant networks
• Explicit Ramsey graphs and orthonormal labelings
• Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs
• scientific article; zbMATH DE number 4027516 (Why is no real title available?)
• scientific article; zbMATH DE number 4099367 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• On universality of graphs with uniformly distributed edges
• Quasi-random graphs
• Quasi-random tournaments
• Regular pairs in sparse random graphs I
• Sparse quasi-random graphs
• Szemerédi's regularity lemma for sparse graphs
• The Algorithmic Aspects of the Regularity Lemma
• The number of submatrices of a given type in a Hadamard matrix and related results
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The Turn Theorem for Random Graphs
• Threshold Functions for Ramsey Properties

Cited in

(11)

• Counting results for sparse pseudorandom hypergraphs. I.
• Extremal results in sparse pseudorandom graphs
• Discrepancy and eigenvalues of Cayley graphs
• A counting lemma for sparse pseudorandom hypergraphs
• Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process
• EMBEDDING SPANNING BOUNDED DEGREE GRAPHS IN RANDOMLY PERTURBED GRAPHS
• The poset of hypergraph quasirandomness
• A sequence of triangle-free pseudorandom graphs
• Factors and loose Hamilton cycles in sparse pseudo‐random hypergraphs
• Subgraphs of the projective norm graph
• Turán's theorem for pseudo-random graphs

This page was built for publication: Embedding graphs with bounded degree in sparse pseudorandom graphs

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