Short proofs for long induced paths


الملخص بالإنكليزية

We present a modification of the DFS graph search algorithm, suited for finding long induced paths. We use it to give simple proofs of the following results. We show that the induced size-Ramsey number of paths satisfies $hat{R}_{mathrm{ind}}(P_n)leq 5cdot 10^7n$, thus giving an explicit constant in the linear bound, improving the previous bound with a large constant from a regularity lemma argument by Haxell, Kohayakawa and {L}uczak. We also provide a bound for the $k$-color version, showing that $hat{R}_{mathrm{ind}}^k(P_n)=O(k^3log^4k)n$. Finally, we present a new short proof of the fact that the binomial random graph in the supercritical regime, $G(n,frac{1+varepsilon}{n})$, contains typically an induced path of length $Theta(varepsilon^2) n$.

تحميل البحث