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

forbidden subgraphsrandom graphs

Mathematics Subject Classification ID

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

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$.

Review text

Summary: Let \(\mathcal{H}\) be a given finite (possibly empty) family of connected graphs, each containing a cycle, and let \(G\) be an arbitrary finite \(\mathcal{H}\)-free graph with minimum degree at least \(k\). For \(p \in [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 \textit{M. Ajtai} et al. [Combinatorica 1, 1--12 (1981; Zbl 0489.05052)], we prove that for every positive \(\epsilon\), there exists a positive \(\delta\) (depending only on \(\epsilon\)) such that the following holds: If \(p \geq \frac{1+\epsilon}{k}\), then with probability tending to \(1\) as \(k \to \infty\), the random graph \(G_p\) contains a cycle of length at least \(n_{\mathcal{H}}(\delta k)\), where \(n_\mathcal{H}(k)>k\) is the minimum number of vertices in an \(\mathcal{H}\)-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

• Cycle lengths in sparse graphs
• Cycles of even length in graphs
• Graph Theory and Probability
• 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?)
• 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

(13)

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

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)