pith. sign in

arxiv: 1303.1066 · v2 · pith:JHO5WYVOnew · submitted 2013-03-05 · 🧮 math.CO

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

classification 🧮 math.CO
keywords mathcalleastcyclegraphrandomvarepsiloncontainsdegree
0
0 comments X p. Extension
pith:JHO5WYVO Add to your LaTeX paper What is a Pith Number?
\usepackage{pith}
\pithnumber{JHO5WYVO}

Prints a linked pith:JHO5WYVO badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more

read the original abstract

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 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 $p \ge \frac{1+\varepsilon}{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$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.