Short proofs for long induced paths

2021/06/16 by Draganić, Nemanja, Glock, Stefan, Krivelevich, Michael
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2106.08975

Abstract

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 R_ind(P_n)≤ 5⋅ 10⁷n, 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 Łuczak. We also provide a bound for the k-color version, showing that R_ind^k(P_n)=O(k³log⁴k)n. Finally, we present a new short proof of the fact that the binomial random graph in the supercritical regime, G(n,(1+ε)/(n)), contains typically an induced path of length Θ(ε²) n.

Related

• Long induced paths in a configuration model
• Longest paths in random hypergraphs
• Note on induced paths in sparse random graphs
• The multicolour size Ramsey number of a path
• On the Performance of the Depth First Search Algorithm in Supercritical Random Graphs