Optimal universal hypergraph conjecture for partition-injective tree homomorphisms

Let DND\in\mathbb{N}. An (n,d,λ)(n,d,\lambda)-graph is a graph on nn vertices with degree dd and second eigenvalue bounded by λ\lambda. Let TT be a tree of maximum degree at most DD, and let

V(T)=T1TV(T)=T_1\cup\cdots\cup T_\ell

be a partition with Tiαn|T_i|\leq \alpha n for every i[]i\in[\ell]. Partition-injective tree homomorphism conjecture. For every DND\in\mathbb{N}, there exist dNd\in\mathbb{N} and α>0\alpha>0 such that, whenever GG is an (n,d,λ)(n,d,\lambda)-graph with λ=Θ(d)\lambda=\Theta(\sqrt d), every such tree TT admits a homomorphism ϕ ⁣:TG\phi\colon T\to G whose restriction to each TiT_i is injective. If true, this would replace the use of the random branching-walk lemma in the proof of the paper's universal-hypergraph theorem and yield the optimal bound O(nrr/d)O(n^{r-r/d}).

Sources & referencesView supporting material

Primary source

Rajko Nenadov, “Hypergraph universality via branching random walks”, arXiv:2411.19432 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.