Long paths and cycles in random subgraphs of H-free graphs

MaRDI QIDQ405113zbMATH OpenFDO

Authors Michael Krivelevich, Wojciech Samotij

Publication date 4 September 2014

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

Full work available at URL https://arxiv.org/abs/1303.1066, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p30

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

random graphsforbidden subgraphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Distance in graphs (05C12) Paths and cycles (05C38) Connectivity (05C40)

Abstract: Let $mathcalH$ be a given finite (possibly empty) family of connected graphs, each containing a cycle, and let $G$ be an arbitrary finite $mathcalH$-free graph with minimum degree at least $k$. For $pin[0,1]$, we form a $p$-random subgraph $G_p$ of $G$ by independently keeping each edge of $G$ with probability $p$. Extending a classical result of Ajtai, Koml'os, and Szemer'edi, we prove that for every positive $varepsilon$, there exists a positive $delta$ (depending only on $varepsilon$) such that the following holds: If $pgefrac1+varepsilonk$, then with probability tending to $1$ as $koinfty$, the random graph $G_p$ contains a cycle of length at least $n_{mathcalH}(deltak)$, where $n_{mathcalH}(k)>k$ is the minimum number of vertices in an $mathcalH$-free graph of average degree at least $k$. Thus in particular $G_p$ as above typically contains a cycle of length at least linear in $k$.

Recommendations

• Long paths and cycles in random subgraphs of graphs with large minimum degree
• Long cycles in random subgraphs of graphs with large minimum degree
• Holes in random graphs
• Paths and cycles in random subgraphs of graphs with large minimum degree
• The threshold probability for long cycles

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 1246230 (Why is no real title available?)
• scientific article; zbMATH DE number 1496607 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Cycle lengths in sparse graphs
• Cycles of even length in graphs
• Graph Theory and Probability
• Long cycles in random subgraphs of graphs with large minimum degree
• Long paths and cycles in random subgraphs of graphs with large minimum degree
• On a graph theorem by dirac
• On the non-planarity of a random subgraph
• Random Graphs
• Random graphs.
• The emergence of a giant component in random subgraphs of pseudo-random graphs
• The longest path in a random graph
• The phase transition in random graphs: a simple proof
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(11)

• scientific article; zbMATH DE number 3915301 (Why is no real title available?)
• Crux and Long Cycles in Graphs
• Large complete minors in random subgraphs
• Long cycles in random subgraphs of graphs with large minimum degree
• scientific article; zbMATH DE number 867706 (Why is no real title available?)
• Long paths and cycles in random subgraphs of graphs with large minimum degree
• On the probability that a random subgraph contains a circuit
• Expansion in supercritical random subgraphs of the hypercube and its consequences
• The threshold probability for long cycles
• Turán‐type problems for long cycles in random and pseudo‐random graphs
• Paths and cycles in random subgraphs of graphs with large minimum degree

This page was built for publication: Long paths and cycles in random subgraphs of \(\mathcal{H}\)-free graphs

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