Large holes in quasi-random graphs

MaRDI QIDQ1010779zbMATH OpenFDO

Authors Joanna Polcyn

Publication date 7 April 2009

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/129773, http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1r60.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

density of large subsetslargest size empty subgraphslargest size of complete bipartite induced subgraphsquasi random graphs

Mathematics Subject Classification ID

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

Review text

Summary: Quasi-random graphs have the property that the densities of almost all pairs of large subsets of vertices are similar, and therefore we cannot expect too large empty or complete bipartite induced subgraphs in these graphs. In this paper we answer the question what is the largest possible size of such subgraphs. As an application, a degree condition that guarantees the connection by short paths in quasi-random pairs is stated.

Recommendations

• Large holes in sparse random graphs
• Sparse quasi-random graphs
• Quasi-random graphs of given density and Ramsey numbers
• Quasi-randomness and the distribution of copies of a fixed graph
• Quasi-random graphs

Cited in

(2)

• Short paths in \(\varepsilon \)-regular pairs and small diameter decompositions of dense graphs
• The size of the largest hole in a random graph

This page was built for publication: Large holes in quasi-random graphs

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