2022/11/09 by Han, Jie, Yang, Donglei · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2211.04758
Given integers n≥ Δ≥ 2, let T(n, Δ) be the collection of all n-vertex trees with maximum degree at most Δ. A question of Alon, Krivelevich and Sudakov in 2007 asks for determining the best possible spectral gap condition forcing an (n, d,λ)-graph to be T(n, Δ)-universal, namely, it contains all members of T(n, Δ) as a subgraph simultaneously. In this paper we show that for sufficiently large integer n and all Δ∈ ℕ, every (n, d,λ)-graph with λ≤\fracd2Δ5√(log n) is T(n, Δ)-universal. As an immediate corollary, this implies that Alon's ingenious construction of triangle-free sparse expander is T(n, Δ)-universal, which provides an explicit construction of such graphs and thus solves a question of Johannsen, Krivelevich and Samotij. Our main result is formulated under a much more general context, namely, the (n,d)-expanders. More precisely, we show that there exist absolute constants C,c>0 such that the following statement holds for sufficiently large integer n. (1).For all Δ∈ ℕ, every (n, Δ5√(log n))-expander is T(n, Δ)-universal. (2).For all Δ∈ ℕ with Δ≤ c√(n), every (n, CΔn1/2)-expander is T(n, Δ)-universal. Both results significantly improve a result of Johannsen, Krivelevich and Samotij, and have further implications in locally sparse expanders and Maker-Breaker games that also improve previously known results drastically.