Short proofs for long induced paths

We present a modification of the Depth first 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}_{ind}$$(P_n) \leq 5 \cdot 10^7n$, hus 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 Łuczak. We also provide a bound for the k-colour version, showing that ${\hat R}^k_{ind}$$(P_n) = O(K^3$ $\mathbf{log}^4$ $k)n$. Finally, we present a new short proof of the fact that the binomial random graph in the supercritical regime, $G(n, \frac {1+\epsilon}{n})$, contains typically an induced path of length $\Theta ({\epsilon}^2)n$.ISSN:0963-5483ISSN:1469-216