Hypergraph universality via branching random walks

Rajko Nenadov School of Computer Science, University of Auckland, New Zealand. Email: [email protected]. Research supported by the Marsden Fund of the Royal Society of New Zealand.

Abstract

Given a family of hypergraphs $\mathcal{H}$ , we say that a hypergraph $\Gamma$ is $\mathcal{H}$ -universal if it contains every $H\in\mathcal{H}$ as a subgraph. For $D,r\in\mathbb{N}$ , we construct an $r$ -uniform hypergraph with $\Theta\left(n^{r-r/D}\log^{r/D}(n)\right)$ edges which is universal for the family of all $r$ -uniform hypergraphs with $n$ vertices and maximum degree at most $D$ . This almost matches a trivial lower bound $\Omega(n^{r-r/D})$ coming from the number of such hypergraphs.

On a high level, we follow the strategy of Alon and Capalbo used in the graph case, that is $r=2$ . The construction of $\Gamma$ is deterministic and based on a bespoke product of expanders, whereas showing that $\Gamma$ is universal is probabilistic. Two key new ingredients are a decomposition result for hypergraphs of bounded density, based on Edmond’s matroid partitioning theorem, and a tail bound for branching random walks on expanders.

1 Introduction

A graph $\Gamma$ is universal for a family of graphs $\mathcal{H}$ if every $H\in\mathcal{H}$ is a subgraph of $\Gamma$ , not necessarily induced. Constructions of sparse graphs which are universal for families $\mathcal{H}$ of interest has been studied extensively in the past decades. This includes families of graphs with bounded degree [4, 5, 6, 7, 8], which are also the central family considered in this paper, trees and forests [16, 18, 17, 23] and, more generally, graphs with bounded degeneracy [2, 33], as well as families of graphs with additional structural properties such as planar graphs [10, 22] and, more generally, graphs with small separators [13, 14, 15]. Other than being an interesting problem in its own right, motivation for studying sparse universal graphs comes from applications in VLSI circuit design [12], data storage [19], and simulation of parallel computer architecture [11], to name a few.

We are interested in the family $\mathcal{H}^{(r)}(D,n)$ consisting of all $r$ -uniform hypergraphs with $n$ vertices and maximum degree at most $D$ . The case $r=2$ was first studied by Alon, Capalbo, Kohayakawa, Rödl, Ruciński, and Szemerédi [7], where they constructed an $\mathcal{H}^{(2)}(D,n)$ -universal graph with $\Theta\left(n^{2-1/D}\log^{1/D}(n)\right)$ edges. This was improved in a series of papers [4, 5, 8], culminating with the work of Alon and Capalbo [6] where they constructed a universal graph with $\Theta\left(n^{2-2/D}\right)$ edges. A simple counting argument based on the size of the family $\mathcal{H}^{(2)}(D,n)$ gives a lower bound $\Omega\left(n^{2-2/D}\right)$ , showing that the construction of Alon and Capalbo is optimal.

The hypergraph case $r\geq 3$ was considered by Parczyk and Person [34] and Hetterich, Parczyk, and Person [27]. By reducing the problem to the graph case, they showed that for even $r$ there exists an $r$ -uniform hypergraph ( $r$ -graph for short) with $\Theta\left(n^{r-r/D}\right)$ edges which is $\mathcal{H}^{(r)}(D,n)$ -universal. They also obtained the same bound in the case $r$ is odd and $D=2$ . Similarly as in the graph case, a simple counting argument based on the size of the family $\mathcal{H}^{(r)}(D,n)$ shows that this is optimal. In the case of odd $r$ and $D>2$ , they constructed a universal hypergraph with $\Theta\left(n^{r-(r+1)/\Delta}\right)$ edges, where $\Delta=\lceil(r+1)D/r\rceil$ . This falls short of the lower bound $\Omega\left(n^{r-r/D}\right)$ by a polynomial factor for every such $r$ and $D$ . Our main result is the existence of universal $r$ -graphs which are off only by a small logarithmic factor.

Theorem 1.1.

For every $r,D\in\mathbb{N}$ there exists $C=C(r,D)>0$ such that the following holds: For every $n\in\mathbb{N}$ there exists an $r$ -graph $\Gamma$ with

e(\Gamma)\leq Cn^{r-r/D}\log^{r/D}(n),

which is $\mathcal{H}^{(r)}(D,n)$ -universal.

On a high-level, our proof follows the construction based on a product of expander graphs used by Alon and Capalbo [5, 6]. To show that the obtained hypergraph is $\mathcal{H}^{(r)}(D,n)$ -universal, we employ two new ingredients. The first one, Lemma 2.1, provides a collection of graphs with a simple structure (namely unicyclic) which together underpin a given hypergraph $H$ . The construction of $\Gamma$ is tailored to make use of this. The second one is a first step towards generalising a classic result of Gilman [25] on tail bounds for random walks on expanders to branching random walks which follow a given ‘blueprint’ tree with bounded degree. This is used to show that a combination of certain graph homomorphisms together form an injection – and thus an embedding of $H$ in $\Gamma$ . We consider this tail bound for branching random walks to be our main technical contribution, and an interesting research direction in its own right, thus we describe it next.

1.1 Tail bound for branching random walks

In the simplest form, a random walk of length $\ell$ on a graph $G$ is defined as follows: Let $v_{1}$ be a vertex in $V(G)$ chosen uniformly at random, and for each $i\in\{2,\ldots,\ell-1\}$ , sequentially, take $v_{i}$ to be a neighbour of $v_{i-1}$ chosen uniformly at random. In the case $G$ has bounded degree, this gives an efficient way of sampling $\ell$ vertices from $G$ in terms of the number of random bits. Indeed, compared to $\ell\log(|V(G)|)$ bits required to sample $\ell$ vertices completely uniformly and independently, random walk requires only $\log(|V(G)|)+(\ell-1)\log(D)$ , where $D$ is the maximum degree in $G$ . This is of great importance in theoretical computer science, and it prompts the question of how much sampling vertices using a random walk resembles the uniform distribution. While the vertices in a random walk are very much dependent locally, it turns out that globally the two distributions exhibit similar phenomena. This was first observed by Ajtai, Komlós, and Szemerédi [1] who studied the probability that a random walk stays confined to a given subset. Their result was significantly strengthened by Gillman [25], who showed that that if $G$ is a good expander, then the probability that a random walk hits a given set $S\subseteq V(G)$ significantly more that $\ell|S|/|V(G)|$ times is similar to what Chernoff-Hoeffding inequality gives when all vertices are sampled uniformly and independently. Since then, there has been a great interest in generalising these results and by now there is a large body of research on tail bounds for random walks on expander graphs and, more generally, finite state Markov chains (e.g. see [20, 24, 26, 29, 30, 31, 32, 35, 37]).

We propose the study of similar questions for a certain class of branching random walks. For a rooted tree $T$ and a graph $G$ , we define a random $T$ -walk on $G$ to be a homomorphism $\phi\colon T\to G$ given by the following random process. Let $t_{1},\ldots,t_{N}$ be any ordering of the vertices in $T$ such that $t_{1}$ is the root, and if $t_{i}$ is closer to the root than $t_{j}$ then $i<j$ . Choose $\phi(t_{1})$ uniformly at random from $V(G)$ , and for $i\geq 2$ , sequentially, choose $\phi(t_{i})$ uniformly at random among the set of neighbours of $\phi(p_{i})$ , where $p_{i}$ is the parent of $t_{i}$ (thus precedes it in the considered ordering). Note that the choice of the ordering is irrelevant for the outcome of the process, as long as it satisfies the stated property. In this terminology, a random walk of length $\ell-1$ corresponds to a random $P_{\ell}$ -walk where $P_{\ell}$ is a path with $\ell$ vertices.

Recall that an $(n,d,\lambda)$ -graph is a $d$ -regular graph with $n$ vertices, such that the second largest absolute value of its adjacency matrix is at most $\lambda$ . The following lemma is our main technical contribution.

Lemma 1.2.

There exist constants $K_{0}>1$ and $\alpha>0$ such that the following holds. Let $T$ be a rooted tree with maximum degree $D$ , and suppose $G$ is an $(n,d,\lambda)$ -graph with $\lambda<\alpha d/D$ . Given a non-empty subset $U\subseteq V(T)$ and a vertex $x\in V(G)$ , let $X$ denote the number of vertices from $U$ which are mapped to $x$ in a random $T$ -walk on $G$ . Then $\mathbb{E}[X]=|U|/n$ and

\Pr\left[X>K\mathbb{E}[X]\right]\leq e^{-(K-K_{0})\mathbb{E}[X]},

for every $K>K_{0}$ .

On the one hand, Lemma 1.2 is weaker than the previously discussed result of Gillman [25] in two ways: (i) we require $K$ to be sufficiently large, and (ii) we only bound the number of times a particular vertex $x\in V(G)$ is being hit, rather than a subset of vertices. On the other hand, it is stronger in the sense that it supports any tree $T$ and not just a path, and it also counts the number of times a particular subset of vertices of $T$ hits $x$ , instead of the whole of $T$ . In the case of random walks, this corresponds to the number of times a particular set of steps has landed on $x$ . A common generalisation would be to consider a set of functions $f_{t}:V(G)\to[0,1]$ , one for each pair $t\in V(T)$ , and establish a tail bound for the random variable $X=\sum_{t\in V(T)}f_{t}(\phi(t))$ . In the case of random walks, this has been done by Rao and Regev [35]. Another, rather obvious, open problem is to improve the lower bound on $K_{0}$ for which the conclusion of Lemma 1.2 holds. We leave these as interesting directions for future research.

2 Decomposition Lemma

Given a hypergraph $H$ , recall the usual definition of the maximal density of $H$ :

m(H)=\max_{H^{\prime}\subseteq H}\frac{e(H^{\prime})}{v(H^{\prime})}.

Lemma 2.1.

Let $H$ be an $r$ -graph with $m(H)\leq a/b$ , for some $a,b\in\mathbb{N}$ with $b>r-1$ and $a>b/(r-1)$ . Then there exists a family of graphs (that is, $2$ -graphs) $H_{1},\ldots,H_{a}$ on the vertex set $V(H)$ such that the following holds:

(D1)

Each connected component of every $H_{i}$ is unicyclic and the maximum degree of $H_{i}$ is at most $2D$ , where $D$ is the maximum degree in $H$ , and
(D2)

For each hyperedge $h\in E(H)$ there exist forests $F_{1}^{(h)}\subseteq H_{1},\ldots,F_{a}^{(h)}\subseteq H_{a}$ on the vertex set $h$ (recall that $h\subseteq V(H)$ is a subset of size $r$ ) such that $\sum_{i=1}^{a}e(F_{i}^{(h)})=b$ .

It is crucial that each $F_{i}^{(h)}$ is a forest and not just a unicyclic graph, like what we require in 1. The proof of Lemma 2.1 uses Edmonds’ matroid partitioning theorem [21]. Recall that a finite matroid $M$ is a pair $(E,\mathcal{I})$ where $E$ is a finite set and $\mathcal{I}$ is a family of subsets of $E$ with the following properties:

•

$\emptyset\in\mathcal{I}$ ,
•

If $A^{\prime}\subseteq A\subseteq E$ and $A\in\mathcal{I}$ , then $A^{\prime}\in\mathcal{I}$ , and
•

If $A,B\in\mathcal{I}$ and $|A|>|B|$ , then there exists $x\in A\setminus B$ such that $B\cup\{x\}\in\mathcal{I}$ .

The set in $\mathcal{I}$ are referred to as independent sets.

Theorem 2.2 (Edmonds’ partitioning theorem).

Let $M=(E,\mathcal{I})$ be a finite matroid, and let

k(M)=\max_{S\subseteq E}\left\lceil\frac{|S|}{r(S)}\right\rceil,

where $r(S)$ denotes the size of a largest independent set from $\mathcal{I}$ which is contained in $S$ . Then there exists a partition $E=I_{1}\cup I_{2}\cup\ldots\cup I_{k(M)}$ such that $I_{i}\in\mathcal{I}$ for each $i\in\{1,\ldots,k(M)\}$ .

We are now ready to prove Lemma 2.1.

Proof of Lemma 2.1.

Given an $r$ -uniform $H$ with $m(H)\leq a/b$ , we construct a bipartite graph $B$ on vertex sets $U$ and $V$ as follows. The set $V$ corresponds to the vertex set $V(H)$ , and for each hyperedge $h\in H$ there are $b$ vertices in $U$ corresponding to $h$ . We put an edge between $u\in U$ and $v\in V$ iff the hyperedge in $H$ corresponding to $u$ contains $v$ .

Let $\mathcal{I}$ be the family of all subsets $X\subseteq U$ such that: (i) $X$ contains at most $r-1$ vertices corresponding to each hyperedge, and (ii) for each nonempty $X^{\prime}\subseteq X$ we have $|N_{B}(X^{\prime})|\geq|X^{\prime}|$ . We claim that $M=(U,\mathcal{I})$ is a matroid with $\mathcal{I}$ being the family of independent sets. We trivially have $\emptyset\in\mathcal{I}$ , and by the definition we have that $Y\in\mathcal{I}$ and $X\subseteq Y$ implies $X\in\mathcal{I}$ . It remains to verify the augmentation axiom, that is, for each $X,Y\in\mathcal{I}$ such that $|X|<|Y|$ , there exists $x\in Y\setminus X$ such that $X\cup\{x\}\in\mathcal{I}$ . This can be seen as follows. We can assume that if $X_{h}\subseteq X$ and $Y_{h}\subseteq Y$ denote subsets which corresponds to vertices associated with a hyperedge $h$ and $|X_{h}|\leq|Y_{h}|$ , then $X_{h}\subseteq Y_{h}$ . This is because each vertex in $Y_{h}$ has the same neighbourhood, thus we can reassign vertices such that this holds. By the definition of $\mathcal{I}$ and Hall’s condition, there exist matchings $M_{X}$ and $M_{Y}$ in $B$ which saturate $X$ and $Y$ , respectively. Now $M_{X}\cup M_{Y}$ contains an augmenting path which gives a matching saturating $X\cup\{x\}$ for some $x\in Y\setminus X$ . Therefore, $|N(X^{\prime})|\geq|X^{\prime}|$ for every $X^{\prime}\subseteq X\cup\{x\}$ . By the initial assumption, we have that the number of vertices in $X\cup\{x\}$ corresponding to each hyperedge is, again, at most $r-1$ , thus $X\cup\{x\}\in\mathcal{I}$ .

Now that we have established that $M$ is a matroid, we can state a claim that is the heart of the proof of the lemma.

Claim 2.3.

There exists a partition $U=U_{1}\cup\ldots\cup U_{a}$ such that $U_{1},\ldots,U_{a}\in\mathcal{I}$ .

Proof of Claim 2.3.

By Edmonds’ partition theorem, it suffices to show $|Z|/r(Z)\leq a$ for every $Z\subseteq U$ , where $r(Z)$ denotes the rank of $Z$ , that is, the size of a largest independent set from $M$ which is contained in $Z$ .

Consider some $Z\subseteq U$ , and let $Z^{\prime}\subseteq Z$ be obtained from $Z$ by removing all but at most $r-1$ vertices corresponding to each hyperedge from $H$ . Then $r(Z)$ is equal to the size of a largest matching in $B$ between $Z^{\prime}$ and $V$ . By König’s theorem, $r(Z)=|C|$ where $C$ is a smallest vertex cover of the induced bipartite subgraph $B[Z^{\prime},V]$ . Let $Z_{C}=Z^{\prime}\cap C$ , $\hat{Z}_{C}=Z^{\prime}\setminus C$ , $V_{C}=V\cap C$ , and $\hat{V}_{C}=V\setminus V_{C}$ . Note that there is no edge in $B$ between $\hat{Z}_{C}$ and $\hat{V}_{C}$ . Moreover, the smallest vertex cover in $B[\hat{Z}_{C},V_{C}]$ is of size $|V_{C}|$ , and in $B[Z_{C},\hat{V}_{C}]$ of size $|Z_{C}|$ . Therefore, a largest matching between $\hat{Z}_{C}$ and $V_{C}$ is of size $|V_{C}|$ , and a largest matching between between $Z_{C}$ and $\hat{V}_{C}$ is of size $|Z_{C}|$ . As every hyperedge corresponding to a vertex in $\hat{Z}_{C}$ is fully contained in $V_{C}$ , we conclude

|\hat{Z}_{C}|\leq(r-1)\cdot m(H)|V_{C}|\leq\frac{(r-1)a}{b}|V_{C}|.

(1)

We have $|Z|\leq b|Z^{\prime}|/(r-1)$ , thus

\frac{|Z|}{r(Z)}=\frac{|Z|}{|Z_{C}|+|V_{C}|}\leq\frac{b}{r-1}\cdot\frac{|Z^{\prime}|}{|Z_{C}|+|V_{C}|}=\frac{b}{r-1}\cdot\frac{|Z_{C}|+|\hat{Z}_{C}|}{|Z_{C}|+|V_{C}|}\leq\frac{b}{r-1}\cdot\max\{1,|\hat{Z}_{C}|/|V_{C}|\}.

From $b/(r-1)<a$ and (1), we conclude $|Z|/r(Z)\leq a$ , as desired. ∎

For each hyperedge $h\in H$ fix a cyclic ordering of its vertices. Let us denote with $h(v)$ the successor of a vertex $v\in h$ in such an ordering for a hyperedge $h$ . By the definition of $\mathcal{I}$ and Hall’s condition, for every independent set $X\in\mathcal{I}$ there exists a matching in $B$ which saturates $X$ . Let $\phi\colon U_{i}\rightarrow V$ denote such a matching saturating $U_{i}$ . We form $H_{i}$ by taking an edge $\{\phi(u),h_{u}(\phi(u))\}$ for each $u\in U_{i}$ , where $h_{u}\in H$ is the hyperedge in $H$ corresponding to $u$ . A vertex is incident to at most two edges coming from each hyperedge it is part of, and every connected component of $H_{i}$ contains at most one cycle (one can think of the obtained graph as being a directed graph with out-degree at most $1$ ), thus 1 is satisifed.A forest $F_{i}^{(h)}$ corresponding to the hyperedge $h\in H$ is simply a (possibly empty) collection of paths given by the union of edges $\{\phi(u),h(\phi(u))\}$ for $u\in U_{i}$ corresponding to $h$ . Note that this is indeed a forest, and not a cycle, as $U_{i}$ contains at most $r-1$ vertices from $U$ corresponding to $h$ . Each vertex in $U$ corresponding to $h$ contributes exactly one edge to some $F_{i}^{(h)}$ , thus 2 holds as well. ∎

3 Branching random walk on expanders

In this section we prove Lemma 1.2. The proof follows the strategy of Rao and Regev [35], with the following lemma being the key new ingredient. This lemma is also the main difference compared to [35], which deals with the simpler case of random $P_{\ell}$ -walks.

Lemma 3.1.

Let $T$ be a rooted tree with maximum degree $D$ , and suppose $G$ is an $(n,d,\lambda)$ -graph, for some $\lambda<d/(2^{10}D)$ . Consider a random $T$ -walk on $G$ . For a subset $W\subseteq V(T)$ and $x\in V(G)$ , let $I_{x}(W)$ be the indicator random variable for the event that all the vertices in $W$ are mapped to $x$ . Then for any $x\in V(G)$ , a subset $U\subseteq V(T)$ , and $1\leq k\leq|U|$ , we have

\mathbb{E}\left[\sum_{W\in\binom{U}{k}}I_{x}(W)\right]\leq\sum_{i=1}^{k}\binom{k-1}{i-1}\frac{(2^{8}|U|/n)^{i}}{i!}\left(2^{9}D\;\frac{\lambda}{d}\right)^{k-i},

(2)

where $\binom{U}{k}$ denotes the family of all $k$ -element subsets of $U$ .

In the proof of Lemma 3.1 we use the following well known property of random walks on expanders, see, e.g., [28].

Lemma 3.2.

Let $G$ be an $(n,d,\lambda)$ -graph, and consider a random walk starting in a given vertex $v\in V(G)$ . The probability that after exactly $\ell$ steps we finish in a vertex $w\in V(G)$ is at most

1/n+(\lambda/d)^{\ell}.

The proof of Lemma 3.1 is combinatorial in nature, based on a careful encoding of a depth-first search traversal of the given tree.

Proof of Lemma 3.1.

Let us denote with $r$ the root of $T$ . For a subset $X\subseteq V(T)$ , let $X^{\uparrow}\subseteq V(T)$ denote the set of all vertices $v\in T$ which lie on the path from some $v\in X$ to the root $r$ , including $X$ and $r$ (that is, all vertices ‘above’ $X$ in a top-down drawing of $T$ ).

Let us first describe the overall strategy of the proof and establish some important notation. For each $W\in\binom{U}{k}$ , we define the ordering $\sigma(W)=(w_{0},\ldots,w_{k-1})$ of $W$ such that $w_{i}\not\in W_{i}^{\uparrow}$ for every $i\in\{1,\ldots,k-1\}$ , where $W_{i}=\{w_{0},\ldots,w_{i-1}\}$ . For example, taking $\sigma(W)$ to be an ordering induced by the distance of a vertex from the root, tie-breaking in some arbitrary way, satisfies this property. However, it will be important for us that $\sigma(W)$ can be encoded efficiently, thus our algorithm for producing $\sigma$ is more involved and based on depth-first search. We postpone this until it becomes relevant. Next, let $h_{i}\in W_{i}^{\uparrow}$ be the closest vertex in $W_{i}^{\uparrow}$ to $w_{i}$ , and let $d_{i}$ denote their distance. Note that $d_{i}$ is a function of $i$ and $W$ (that is, of $\sigma(W)$ ), thus we write $d_{i}(W)$ to signify this. Conditioned on the outcome of the $T[W_{i}^{\uparrow}]$ -walk $\phi$ , $w_{i}$ is mapped onto the last vertex in a random walk of length $d_{i}$ starting from $\phi(h_{i})$ . Note that $\Pr[\phi(w_{0})=x]=1/n$ as the stationary distribution is uniform, thus by Lemma 3.2 we have

\mathbb{E}[I_{x}(W)]=\Pr[I_{x}(W)=1]\leq\frac{1}{n}\prod_{i=1}^{k-1}\left(\frac{1}{n}+(\lambda/d)^{d_{i}}\right).

(3)

We now use the trick of Rao and Regev [35] and ‘unroll’ the right hand side,

\mathbb{E}[I_{x}(W)]\leq\sum_{f\in\{0,1\}^{k-1}}\left(\frac{1}{n}\right)^{k-|f|}\prod_{i\colon f_{i}=1}(\lambda/d)^{d_{i}},

(4)

where $|f|$ denotes the number of 1’s in $f=(f_{1},\ldots,f_{k-1})$ . Consider some $f\in\{0,1\}^{k-1}$ , and let $W_{\bar{f}}=\{w_{0}\}\cup\{w_{i}\colon f_{i}=0\}$ . Now fix some $F\in\binom{U}{k-|f|}$ , and iterate over all sets $W\in\binom{U}{k}$ such that $W_{\bar{f}}=F$ . Our goal is to show

\sum_{\begin{subarray}{c}W\in\binom{U}{k}\\ W_{\bar{f}}=F\end{subarray}}\prod_{i\colon f_{i}=1}(\lambda/d)^{d_{i}(W)}\leq 256^{k-|f|}\left(2^{9}D\;\frac{\lambda}{d}\right)^{|f|}.

(5)

Together with (4), this implies the desired bound:

	$\displaystyle\mathbb{E}\left[\sum_{W\in\binom{U}{k}}I_{x}(W)\right]$	$\displaystyle\stackrel{{\scriptstyle\eqref{eq:estimate_IxW}}}{{\leq}}\sum_{W\in\binom{U}{k}}\sum_{f\in\{0,1\}^{k-1}}\left(\frac{1}{n}\right)^{k-\|f\|}\prod_{i\colon f_{i}=1}(\lambda/d)^{d_{i}(W)}$
		$\displaystyle=\sum_{f\in\{0,1\}^{k-1}}\left(\frac{1}{n}\right)^{k-\|f\|}\sum_{F\in\binom{U}{k-\|f\|}}\sum_{\begin{subarray}{c}W\in\binom{U}{k}\\ W_{\bar{f}}=F\end{subarray}}\prod_{i\colon f_{i}=1}(\lambda/d)^{d_{i}(W)}$
		$\displaystyle\stackrel{{\scriptstyle\eqref{eq:estimate_f}}}{{\leq}}\sum_{f\in\{0,1\}^{k-1}}\left(\frac{2^{8}}{n}\right)^{k-\|f\|}\binom{\|U\|}{k-\|f\|}\left(2^{9}D\;\frac{\lambda}{d}\right)^{\|f\|}$
		$\displaystyle\leq\sum_{i=0}^{k-1}\binom{k-1}{i}\frac{(2^{8}\|U\|/n)^{k-i}}{(k-i)!}\left(2^{9}D\;\frac{\lambda}{d}\right)^{i}.$

After changing the indexing, we obtain (2).

Let us now outline the strategy for estimating (5). For a fixed $f\in\{0,1\}^{k-1}$ with $|f|\geq 1$ , let $I_{f}=\{i\colon f_{i}=1\}$ . Our aim is to show that there is an injection $\psi_{f,F}$ from the family of all $W\in\binom{U}{k}$ such that $W_{\bar{f}}=F$ to the set of $4$ -tuples $(B,R,(b_{i})_{i\in I_{f}},(\mathbf{c}_{i})_{i\in I_{f}})$ , where $B,R\subseteq\{1,\ldots,4k\}$ , $b_{i}\in\mathbb{N}_{0}$ , and $\mathbf{c}_{i}$ is a sequence of finite length with each element being in $\{1,\ldots,D\}$ . The mapping $\psi_{f,F}$ also has the following important property: if $\psi_{f,F}(W)=(B,R,(b_{i})_{i\in I_{f}},(\mathbf{c}_{i})_{i\in I_{f}})$ , then $d_{i}(W)=|\mathbf{c}_{i}|\geq\max(1,b_{i})$ for every $i\in I_{f}$ . We are not yet in a position to say where such a $4$ -tuple comes from, other than hint the reader that it is an encoding of a certain traversal of the vertices in $W$ within $T$ . Assuming we have such an injection $\psi_{f,F}$ , we easily obtain (5):

	$\displaystyle\sum_{\begin{subarray}{c}W\in\binom{U}{k}\\ W_{f}=F\end{subarray}}\prod_{i\colon f_{i}=1}(\lambda/d)^{d_{i}(W)}$	$\displaystyle\leq 4^{4k}\left(\sum_{b_{i}=1}^{\infty}\sum_{d_{i}=b_{i}}^{\infty}D^{d_{i}}(\lambda/d)^{d_{i}}\right)^{\|f\|}$
		$\displaystyle=4^{4k}\left(\sum_{b_{i}=1}^{\infty}\frac{\kappa^{b_{i}}}{1-\kappa}\right)^{\|f\|}\leq 256^{k-\|f\|}\left(\frac{256\kappa}{1-2\kappa}\right)^{\|f\|},$

where $\kappa=D\lambda/d<1/4$ . Now (5) follows from $1-2\kappa>1/2$ . The importance of the property $b_{i}\leq|\mathbf{c}_{i}|=d_{i}(W)$ is evident from the calculation.

It remains to describe $\psi_{f,F}$ . To do so, we first describe the algorithm which produces the ordering $\sigma(W)$ .

The ordering $\sigma(W)$ .

Fix an arbitrary ordering $\pi$ of the vertex set of $T$ , and for each vertex $v\in T$ fix an ordering $\pi_{v}$ on the set of children of $v$ . Whenever we refer to the $k$ -th child of a vertex $v\in T$ , we mean $k$ -th according to $\pi_{v}$ . We denote with $T_{v}$ the subtree of $T$ rooted in $v$ , which we identify with its set of vertices.

Consider some $W\in\binom{U}{k}$ . We define the ordering $\sigma(W)=(w_{0},\ldots,w_{k-1})$ on $W$ using the depth-first search over a portion of $T$ , with a very specific choice of the next vertex to visit. Throughout the procedure we maintain a number of sets, sequences, and indices, initially set as $S=(r)$ , $\widehat{W}=W$ , $B=R=\emptyset$ , and $j=0$ . If $r\in W$ , then set $w_{0}=r$ and $j=1$ , and remove $r$ from $\widehat{W}$ . Intuitively, $\widehat{W}$ is the set of vertices in $W$ which we have not yet visited, $S$ is the stack which keeps track of important vertices on the path from the root to the current vertex, $B$ tells us whether in a particular step we continued the exploration in the subtree “below” the current vertex, and $R$ tells us whether in a particular step in which we removed a vertex from the stack, we stayed in the subtree of the next vertex from the top of the stack (i.e. we moved to the “right” of the current vertex). Finally, whenever we move to a new vertex $w_{j}$ , we record how we got to it in terms of a number $b_{i}$ – recording how many steps to go “back” towards the root from the current vertex – and a sequence $\mathbf{c}_{i}$ – recording the sequence of moves which tell us how to move through the part of $T$ which has not yet been explored, in order to reach $w_{i}$ .

Throughout the procedure we use $t$ to denote the ordinal number of the current iteration. As long as $S$ is not empty, repeat:

(1)

Let $s$ be the last vertex in $S$ (that is, the top of the stack).
(2)

If $T_{s}\cap\widehat{W}\neq\emptyset$ , add $t$ to the set $B$ and choose $w_{j}\in T_{s}\cap\widehat{W}$ to be the closest vertex to $s$ , tie-breaking according to $\pi$ . Let $d_{j}$ denote the distance from $s$ to $w_{j}$ and $\mathbf{c}_{j}\in[D]^{d_{j}}$ a sequence describing how to get from $s$ to $u$ in $T$ (recall that $T$ has maximum degree at most $D$ and the children of each node are ordered). For completeness, set $b_{j}=0$ . Add $w_{j}$ to the end of $S$ , and remove it from $\widehat{W}$ . Increase $j$ , and proceed to the next round.
(3)
Otherwise, we have $T_{s}\cap\widehat{W}=\emptyset$ .
- •
  
  Remove $s$ from $S$ . If $S$ is now empty terminate the procedure.
- •
  
  Let $s^{\prime}$ be the new vertex on the top of $S$ (that is, the end of $S$ ). If $T_{s^{\prime}}\cap\widehat{W}=\emptyset$ , proceed to the next round.
- •
  
  Otherwise, add $t$ to $R$ . For each $u\in T_{s^{\prime}}\cap\widehat{W}$ , let $h(u)$ denote the vertex on the path from $s^{\prime}$ to $s$ which is closest to $u$ . Note that it cannot happen that $h(u)=s$ , though it could be $h(u)=s^{\prime}$ .
- •
  
  Take $u\in T_{s^{\prime}}\cap\widehat{W}$ with $h(u)$ closest to $s$ (i.e. furthest away from $s^{\prime}$ ). If there are multiple such vertices take the one which itself is closest to $s$ , that is, the one for which the path from $h(u)$ to $u$ is shortest (tie breaking according to $\pi$ ).
- •
  
  If $h(u)\neq s^{\prime}$ then add $h(u)$ to the end of $S$ .
- •
  
  Add $u$ to the end of $S$ and set $w_{j}=u$ . Set $b_{j}$ to be the distance from $s$ to $h(u)$ (denoting how many steps we need to go “back” towards $s^{\prime}$ ), $d_{j}$ to be the distance from $h(u)$ to $u$ , and $\mathbf{c}_{j}\in[D]^{d_{j}}$ the description of how to get from $h(u)$ to $u$ in $T$ . Increase $j$ , and remove $u$ from $\widehat{W}$ . Proceed to the next round.

Observe the following two crucial properties. First, for every $j\in\{0,\ldots,k-1\}$ for which $w_{j}$ was defined in (3) we have $b_{j}\leq d_{j}$ . If this was not the case, then we would have chosen $w_{j}$ before $w_{j-1}$ . Second, the procedure terminates after $t\leq 4k$ rounds.

The mapping $\psi_{f,F}$ .

Fix $f\in\{0,1\}^{k-1}$ with $|f|\geq 1$ and $F\subseteq\binom{U}{k-|f|}$ . Consider some $W\in\binom{U}{k}$ such that $W_{\bar{f}}=F$ . Run the previously described algorithm on $W$ , and let $B,R\subseteq\{1,\ldots,4k\}$ , $(b_{i})_{i\in[k]}$ , and $(\mathbf{c}_{i})_{i\in[k]}$ be as given by the algorithm upon its termination. Define

\psi_{f,F}(W):=(B,R,(b_{i})_{i\in I_{f}},(\mathbf{c}_{i})_{i\in I_{f}}).

The intuition here is that if we know $f$ and $F=W_{\bar{f}}$ , and for each $i\in\{1,\ldots,k-1\}$ such that $f_{i}=1$ we have enough information on how to reach $w_{i}$ , which is precisely what is encoded in $\psi_{f,F}(W)$ , then we can uniquely reconstruct the whole set $W$ . Therefore, $\psi_{f,F}$ is necessarily injective.

To reconstruct $W$ from $f$ , $F=W_{\bar{f}}$ , and $\psi_{f,F}(W)$ , we repeat the algorithm for determining $\sigma(W)$ with the following modification: in the steps corresponding to choosing $w_{i}$ for $i\in I_{f}$ , instead of taking a vertex from $W$ we follow steps described by $b_{i}$ and $\mathbf{c}_{i}$ . The sets $B$ and $R$ tell us exactly when this is applied. We now make this precise.

Start with $S=(r)$ , $\widehat{F}=F$ , and $j=0$ . If $r\in F$ , then set $w_{0}=r$ , $j=1$ , and remove $r$ from $\widehat{F}$ . Throughout the algorithm, we again use $t$ do denote the ordinal number of the current iteration. As long as $S$ is not empty, repeat the following:

(i)

Let $s$ be the last vertex in $S$ .
(ii)
If $t\in B$ :
- •
  
  If $j=0$ or $f_{j}=0$ , then take $w_{j}\in\hat{F}$ to be the closest vertex to $s$ , with tie-breaking according to $\pi$ , and remove it from $\hat{F}$ .
- •
  
  Otherwise, take $w_{j}$ to be the vertex given by following $\mathbf{c}_{j}$ from $s$ .
Add $w_{j}$ to the end of $S$ , and increase $j$ .
(iii)
Otherwise, we have $t\notin B$ . Remove $s$ from $S$ , and if $S$ is empty terminate the procedure. If $t\notin R$ , proceed to the next round. Else:
1. (a)
  
  If $f_{j}=0$ (note that we cannot have $j=0$ at this point), proceed the same as in the original algorithm: Take $u\in T_{s^{\prime}}\cap\hat{F}$ for which $h(u)$ is the closest to $s$ , and if there are multiple such vertices take the one for which the path from $h(u)$ to $u$ is shortest, tie-breaking according to $\pi$ . Let $h_{j}=h(u)$ .
2. (b)
  
  If $f_{j}=1$ , then let $h_{j}$ be the vertex $b_{j}$ steps back from $s$ towards the root in the tree $T$ , and then let $w_{j}$ be obtained by following $\mathbf{c}_{j}$ from $h_{j}$ .
If $h_{j}\neq s^{\prime}$ add $h_{j}$ to the end of $S$ . Add $w_{j}$ to the end of $S$ , remove it from $\hat{F}$ (relevant only if $w_{j}$ was obtained in (a)), and increase $j$ .

By comparing the two algorithms, we see that they output the same ordering $\sigma(W)$ . Therefore, we can uniquely reconstruct $W$ from $\psi_{f,F}(W)$ . ∎

With Lemma 3.1 at hand, the proof of Lemma 1.2 is identical to the proof of [35, Theorem 1.1]. We repeat the argument for convenience of the reader.

Proof of Lemma 1.2.

Consider some $x\in V(G)$ and a subset $U\subseteq V(T)$ . Given a random $T$ -walk $\phi$ on $G$ , let $X$ denote the number of vertices $v\in U$ such that $\phi(v)=x$ . Our aim is to show

\mathbb{E}\left[e^{X}\right]=\sum_{q=0}^{\infty}\frac{\mathbb{E}[X^{q}]}{q!}\leq e^{K_{0}\mathbb{E}[X]},

(6)

from which we derive the desired tail bound using Markov’s inequality,

\Pr\left[X>K\mathbb{E}[X]\right]=\Pr\left[e^{X}>e^{K\mathbb{E}[X]}\right]<\mathbb{E}[e^{X}]e^{-K\mathbb{E}[X]}\stackrel{{\scriptstyle\eqref{eq:moment_gen}}}{{\leq}}e^{-(K-K_{0})\mathbb{E}[X]}.

Recall the notation of Lemma 3.1: given $W\subseteq V(T)$ , let $I_{x}(W)$ be the indicator random variable for the event that all the vertices in $W$ are mapped to $x$ . When $W=\{w\}$ , we simply write $I_{x}(w)$ . Note that $X=\sum_{w\in U}I_{x}(w)$ . Consider some $q\in\mathbb{N}$ . Then

X^{q}=\left(\sum_{w\in U}I_{x}(w)\right)^{q}=\sum_{k=1}^{q}\genfrac{\{}{\}}{0.0pt}{}{q}{k}k!\sum_{W\in\binom{U}{k}}Z_{x}(W),

where $\genfrac{\{}{\}}{0.0pt}{}{}{}$ denotes the Stirling number of the second kind. By the linearity of expectation, we have

\mathbb{E}[X^{q}]=\sum_{k=1}^{q}\genfrac{\{}{\}}{0.0pt}{}{q}{k}k!\;\mathbb{E}\Bigl{[}\sum_{W\in\binom{U}{k}}I_{x}(W)\Bigr{]}.

Combined with Lemma 3.1, this gives the following upper bound on $\mathbb{E}\left[e^{X}\right]$ :

\sum_{q=0}^{\infty}\frac{\mathbb{E}\left[X^{q}\right]}{q!}\leq 1+\sum_{q=1}^{\infty}\frac{1}{q!}\sum_{k=1}^{q}\genfrac{\{}{\}}{0.0pt}{}{q}{k}k!\sum_{i=0}^{k-1}\binom{k-1}{i}\frac{(2^{8}\mathbb{E}[X])^{k-i}}{(k-i)!}\left(2^{9}D\;\frac{\lambda}{d}\right)^{i}.

Rearranging the sums, we get

1+\sum_{i=1}^{\infty}\frac{(2^{8}\mathbb{E}[X])^{i}}{i!}\sum_{k=i}^{\infty}\binom{k-1}{i-1}\left(2^{9}D\;\frac{\lambda}{d}\right)^{k-i}\sum_{q=k}^{\infty}\genfrac{\{}{\}}{0.0pt}{}{q}{k}\frac{k!}{q!}.

(7)

Using the following identity [36, Eq. 1.94(b)],

\sum_{q=k}^{\infty}\genfrac{\{}{\}}{0.0pt}{}{q}{k}\frac{1}{q!}=\frac{(e-1)^{k}}{k!}<\frac{2^{k}}{k!},

we further upper bound (7) as

1+\sum_{i=1}^{\infty}\frac{(2^{8}\mathbb{E}[X])^{i}}{i!}2^{i}\sum_{k=i}^{\infty}\binom{k-1}{i-1}\left(2^{9}D\;\frac{\lambda}{d}\right)^{k-i}.

Now using the identity

\sum_{k=i}^{\infty}\binom{k-1}{i-1}x^{k-i}=\frac{1}{(1-x)^{i}}

for $|x|<1$ , the inner sum further evaluates to

\left(1-2^{9}D\;\frac{\lambda}{d}\right)^{-i}<2^{i}.

We finally get

\mathbb{E}\left[e^{X}\right]<1+\sum_{i=1}^{\infty}\frac{(2^{10}\mathbb{E}[X])^{i}}{i!}=e^{2^{10}\mathbb{E}[X]}.

∎

4 Universal hypergraphs

In this section we prove Theorem 1.1. In fact, we prove a more general result, Theorem 4.1, on universality of bounded-degree hypergraphs with an additional bound on the density. Universality for such a family of graphs was recently studied by Alon et al. [9]. Theorem 4.1 also improves the bound in [9, Theorem 1.4].

Let $\mathcal{H}^{(r)}(q,D,n)$ the family of all $n$ -vertex $r$ -graphs $H$ with maximum degree at most $D$ and density $m(H)\leq q$ , where $m(H)$ is as defined in Section 2. An $r$ -uniform hypergraph $H$ with maximum degree $D$ and $v$ vertices contains at most $Dv/r$ edges, thus $m(H)\leq D/r$ . Therefore $\mathcal{H}^{(r)}(D,n)\subseteq\mathcal{H}^{(r)}(D/r,D,n)$ , thus Theorem 4.1 implies Theorem 1.1.

Theorem 4.1.

For every $r,D,n\in\mathbb{N}$ and $q\in\mathbb{Q}$ , $q>1/(r-1)$ , there exists $C=C(r,D,q)>0$ and an $r$ -graph $\Gamma$ with

e(\Gamma)\leq Cn^{r-1/q}\log^{1/q}(n)

edges which is $\mathcal{H}^{(r)}(q,D,n)$ -universal.

Proof.

Fix smallest $a,b\in\mathbb{N}$ such that $b>r-1$ and $q=a/b$ . We first describe the construction of $\Gamma$ , and then prove that it contains every hypergraph $H\in\mathcal{H}^{(r)}(q,D,n)$ . We say that $H$ is an $(\leq r)$ -uniform hypergraph, or $(\leq r)$ -graph for short, if every hyperedge in $H$ has size at most $r$ . For brevity, throughout the proof we ignore ceilings and floors.

Construction.

Let $m=(n/\log(n))^{1/a}$ , and let $d\in\mathbb{N}$ be sufficiently large with respect to $D$ . Let $G$ be an $(m,d,\lambda)$ -graph on the vertex set $[m]$ , for some $\lambda<\alpha d/D$ where $\alpha$ is as given by Lemma 1.2. Explicit construction of such a graph, for any $m\geq m_{0}(d)$ , was obtained by Alon [3]. Let $G^{2}$ be the graph obtained from $G$ by adding an edge between every two vertices at distance at most $2$ in $G$ . Note that the maximum degree in $G^{2}$ is at most $d^{2}$ .

We first form an $(\leq r)$ -graph $\Gamma^{\prime}$ as follows: $V(\Gamma^{\prime})=[m]^{a}$ , and $r^{\prime}\leq r$ vertices $\mathbf{v}^{(1)},\ldots,\mathbf{v}^{(r^{\prime})}\in[m]^{a}$ , $\mathbf{v}^{(j)}=(v_{1}^{(j)},\ldots,v_{a}^{(j)})$ , form a hyperedge if there exist forests $F_{1},\ldots,F_{a}$ , each on the vertex set $[r]$ , such that:

•

$\sum_{i=1}^{a}e(F_{i})\geq b$ , and
•

for each $i\in[a]$ there exists a homomorphism $f_{i}\colon[r]\to\{v_{1}^{(i)},\ldots,v_{r^{\prime}}^{(i)}\}$ of $F_{i}$ in $G^{2}$ .

This construction is guided by the statement of Lemma 2.1.

Next, take $\Gamma$ to be an $r$ -graph obtained as the $(C\log n)$ -blowup of $\Gamma^{\prime}$ , for $C$ being a sufficiently large constant. That is, for each vertex $\mathbf{v}\in V(\Gamma^{\prime})$ we introduce a set $B_{\mathbf{v}}$ of size $C\log n$ , and for each hyperedge $\mathbf{v}^{(1)}\cdots\mathbf{v}^{(r^{\prime})}\in\Gamma^{\prime}$ , for some $1\leq r^{\prime}\leq r$ , we add all the subsets of $\bigcup_{i=1}^{r^{\prime}}B_{\mathbf{v}^{(i)}}$ of size exactly $r$ as hyperedges in $\Gamma$ .

Let us first count the number of edges in $\Gamma^{\prime}$ . Consider forests $F_{1},\ldots,F_{a}$ on $[r]$ , such that $\sum_{i=1}^{a}e(F_{i})\geq b$ . Then $c(F_{1})+\ldots+c(F_{a})\leq ra-b$ , where $c(F)$ denotes the number of connected components in $F$ . As the maximum degree in $G^{2}$ is $d^{2}$ , a homomorphism of a forest $F$ in $G^{2}$ can be chosen in at most $m^{c(F)}(d^{2})^{r-c(F)}$ ways. Altogether, this gives at most

\sum_{F_{1},\ldots,F_{a}}\prod_{i=1}^{a}m^{c(F_{i})}(d^{2})^{r-c(F_{i})}\leq r^{ra}m^{ra-b}(d^{2})^{ra}=r^{a}d^{2ra}\left(\frac{n}{\log n}\right)^{r-b/a}

hyperedges in $\Gamma^{\prime}$ , where the first sum goes over $a$ -tuples $(F_{1},\ldots,F_{a})$ of forests on $[r]$ such that $c(F_{1})+\ldots+c(F_{a})\leq r$ .

Each hyperedge in $\Gamma^{\prime}$ gives rise to less than $(rC\log n)^{r}$ hyperedges in $\Gamma$ . Therefore, $\Gamma$ has

O\left(n^{r-1/q}\log^{1/q}(n)\right)

hyperedges.

Universality.

We now show that $\Gamma$ is $\mathcal{H}(q,D,n)$ -universal. Consider an $r$ -graph $H\in\mathcal{H}^{(r)}(d,D,n)$ . Let $H_{1},\ldots,H_{a}$ be graphs on the vertex set $V(H)$ given by Lemma 2.1, and for each edge $h\in H$ let $F_{1}^{(h)}\subseteq H_{1},\ldots,F_{a}^{(h)}\subseteq H_{a}$ be forests corresponding to 2. For each $i\in[a]$ , let $T_{i}$ be a forest on $V(H)$ with maximum degree at most $2D$ such that $H_{i}\subseteq T_{i}^{2}$ , that is, if $\{v,w\}$ is an edge in $H_{i}$ then $\{v,w\}$ are at distance at most $2$ in $T_{i}$ . Such $T_{i}$ can be obtained from $H_{i}$ by replacing each cycle $x_{1},\ldots,x_{\ell}$ in $H_{i}$ by a path $x_{1},x_{\ell},x_{2},x_{\ell-1},x_{3},x_{\ell-2},\ldots$ . We use the fact that if $f\colon T_{i}\to G$ is a homomorphism of $T_{i}$ in $G$ , then it is also a homomorphism of $H_{i}$ in $G^{2}$ . Therefore, from now on we can focus on $T_{i}$ instead of $H_{i}$ . By adding more edges, without loss of generality we may assume each $T_{i}$ is a tree.

Our aim is to iteratively find homomorphisms $\phi_{i}\colon T_{i}\to G$ such that, for each $\mathbf{v}\in[m]^{i}$ , the set

S_{\mathbf{v}}^{i}=\left\{w\in V(H)\colon\phi_{1}(w)=v_{1},\ldots,\phi_{i}(w)=v_{i}\right\}

is of size

|S_{\mathbf{v}}^{i}|\leq n(K/m)^{i},

(8)

where $K\geq K_{0}$ is sufficiently large and $K_{0}$ is the constant given by Lemma 1.2. Suppose that we have found such homomorphisms $\phi_{1},\ldots,\phi_{i-1}$ , for some $i\in\{1,\ldots,a\}$ . For simplicity, we define $S_{\mathbf{v}}^{0}=V(H)$ . Let $\phi_{i}$ be a random $T_{i}$ -walk in $G$ , with an arbitrary vertex in $T_{i}$ being the root. Applying Lemma 1.2 with some $x\in V(G)$ and $S=S_{\mathbf{v}}^{i-1}\cup S^{\prime}$ , for some $\mathbf{v}\in[m]^{i-1}$ and $S^{\prime}$ chosen arbitrarily such that $|S|=n(K/m)^{i-1}$ (this is a rather technical detail), we get

\Pr[X(x,\mathbf{v})>K|S|/m]\leq e^{-(K-K_{0})|S|/m}=o(1/n^{2}),

where $X(x,\mathbf{v})$ denotes the number of vertices $v\in S$ such that $\phi_{i}(v)=x$ . There are $m$ choices for $x$ and $m^{a}=o(n)$ choices for $\mathbf{v}$ , thus with positive probability $\phi_{i}$ is such that $X(x,\mathbf{v})\leq n(K/m)^{i}$ for every $x\in V(G)$ and $\mathbf{v}\in[m]^{i-1}$ . Therefore, there exists $\phi_{i}$ for which (8) holds.

Let now $f\colon H\to[m]^{a}$ be defined as $f(w)=(\phi_{1}(w),\ldots,\phi_{a}(w))$ . As $\phi_{i}$ is a homomorphism of $T_{i}$ into $G$ and $H_{i}\subseteq T_{i}^{2}$ , $\phi_{i}$ is also a homomorphism of $H_{i}$ into $G^{2}$ . Consider some edge $h=\{w_{1},\ldots,w_{r}\}\in H$ . Then the restriction of $\phi_{i}$ to $F_{i}^{(h)}$ is a homomorphism of $F_{i}^{(h)}$ in $G^{2}$ . Since $\sum_{i=1}^{a}e(F_{i})\geq b$ by Lemma 2.1, the set of vertices $\mathbf{v}^{(1)},\ldots,\mathbf{v}^{(r)}$ given by $\mathbf{v}^{(i)}=(\phi_{1}(w_{i}),\ldots,\phi_{a}(w_{i}))$ for $i\in[r]$ , form a hyperedge in $\Gamma^{\prime}$ . Note that these vertices might not all be distinct, thus the hyperedge is not necessarily of size $r$ . Therefore, each $h\in H$ is preserved by $f$ , that is, $f(h)$ is a hyperedge in $\Gamma^{\prime}$ . By (8), no vertex is an image of more than $O(\log n)$ vertices from $H$ , thus we can turn $f$ into an injective homomorphism $f^{\prime}\colon H\to\Gamma$ , which finally defines a copy of $H$ in $\Gamma$ . ∎

A reader familiar with some of the previous work [5, 6, 9], most notably the proof of [9, Theorem 1.4], will notice similarity with the overall strategy used in the proof of Theorem 4.1. We note that both the construction of the hypergraph $\Gamma$ and tools used to show it is universal are more involved in our case.

5 Concluding remarks

Towards optimal universal hypergraphs.

The following conjecture, if true, would allow one to replace the use of Lemma 1.2 in the proof of Theorem 1.1 and obtain optimal the optimal bound $O(n^{r-r/d})$ .

Conjecture 5.1.

For every $D\in\mathbb{N}$ there exists $d\in\mathbb{N}$ and $\alpha>0$ such that the following holds. Suppose $G$ is an $(n,d,\lambda)$ -graph for $\lambda=\Theta(\sqrt{d})$ . Then for any tree $T$ with maximum degree at most $D$ and any partition of $V(T)=T_{1}\cup\ldots\cup T_{\ell}$ with $|T_{i}|\leq\alpha n$ for each $I\in[\ell]$ , there exists a homomorphism $\phi\colon T\to G$ such that the restriction of $\phi$ to each $T_{i}$ is an injection.

In case $\ell=1$ , this corresponds to the celebrated result by Friedman and Pippenger [23]. It is important to notice that there is no upper bound on $\ell$ in terms of $n$ or any other parameter.

Branching random walks.

As discussed in Section 1.1, it would be interesting to extend Lemma 1.2 to other forms of random variables. As a first step, one could consider a random variable which counts the number of times a branching random walk has landed in a set $X\subseteq V(G)$ rather than on a particular vertex $x\in V(G)$ . This would generalise the result of Gillman [25].

The main obstacle in adapting the proof of Lemma 1.2 to this case seems to be in the estimate (3). For appropriately defined random variable, analogous to the one considered in (3), one would aim to upper bound its expectation as $\mu\prod_{i=1}^{k-1}(\mu+(\lambda/d)^{d_{i}})$ , where $\mu=|X|/n$ . When $|X|=1$ then this is precisely what is achieved in (3). However, the way this upper bound is derived is based on the ‘worst-case’ conditioning of how a part of $T$ is mapped, which is too pessimistic and does not yield a desired upper bound for larger set $X$ . A similar estimate is encountered [35, Lemma 3.3], however the proof there leverages the linear structure of random walks and the ability to algebraically express the desired expectation, and it is not clear whether a similar argument can be applied here.

Another interesting direction would be to consider branching random walks on graphs which are not regular.

Acknowledgment.

The author thanks Noga Alon for stimulating discussions about the problem, and Anders Martinsson for discussions about Lemma 1.2.

References

[1] M. Ajtai, J. Komlós, and E. Szemerédi. Deterministic simulation in LOGSPACE. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC ’87, page 132–140, New York, NY, USA, 1987. Association for Computing Machinery.
[2] P. Allen, J. Böttcher, and A. Liebenau. Universality for graphs of bounded degeneracy. arXiv preprint arXiv:2309.05468, 2023.
[3] N. Alon. Explicit expanders of every degree and size. Combinatorica, 41(4):447–463, 2021.
[4] N. Alon and V. Asodi. Sparse universal graphs. J. Comput. Appl. Math., 142(1):1–11, 2002.
[5] N. Alon and M. Capalbo. Sparse universal graphs for bounded-degree graphs. Random Struct. Algorithms, 31(2):123–133, 2007.
[6] N. Alon and M. Capalbo. Optimal universal graphs with deterministic embedding. In Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2008, San Francisco, CA, January 20–22, 2008, pages 373–378. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM), 2008.
[7] N. Alon, M. Capalbo, Y. Kohayakawa, V. Rodl, A. Rucinski, and E. Szemerédi. Universality and tolerance. In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 14–21. IEEE, 2000.
[8] N. Alon, M. Capalbo, Y. Kohayakawa, V. Rödl, A. Ruciński, and E. Szemerédi. Near-optimum universal graphs for graphs with bounded degrees. In International Workshop on Randomization and Approximation Techniques in Computer Science, pages 170–180. Springer, 2001.
[9] N. Alon, N. Dodson, C. Jackson, R. McCarty, R. Nenadov, and L. Southern. Universality for graphs with bounded density. arXiv:2311.05500.
[10] L. Babai, F. R. K. Chung, P. Erdős, R. L. Graham, and J. H. Spencer. On graphs which contain all sparse graphs. Ann. Discrete Math. 12, 21-26 (1982)., 1982.
[11] S. Bhatt, F. Chung, T. Leighton, and A. Rosenberg. Optimal simulations of tree machines. In 27th Annual Symposium on Foundations of Computer Science, pages 274–282. IEEE, 1986.
[12] S. Bhatt and T. Leighton. A framework for solving VLSI graph layout problems. J. Comput. Syst. Sci., 28:300–343, 1984.
[13] M. Capalbo. Small universal graphs for bounded-degree planar graphs. Combinatorica, 22(3):345–359, 2002.
[14] M. R. Capalbo and S. R. Kosaraju. Small universal graphs. In Proceedings of the 31st annual ACM symposium on theory of computing, STOC 1999. Atlanta, GA, USA, May 1–4, 1999, pages 741–749. New York, NY: ACM, Association for Computing Machinery, 1999.
[15] F. R. K. Chung. Separator theorems and their applications. Paths, flows, and VLSI-layout, Proc. Meet., Bonn/Ger. 1988, Algorithms Comb. 9, 17-34., 1990.
[16] F. R. K. Chung and R. L. Graham. On graphs which contain all small trees. J. Comb. Theory, Ser. B, 24:14–23, 1978.
[17] F. R. K. Chung and R. L. Graham. On universal graphs for spanning trees. J. Lond. Math. Soc., II. Ser., 27:203–211, 1983.
[18] F. R. K. Chung, R. L. Graham, and N. Pippenger. On graphs which contain all small trees. II. Combinatorics, Keszthely 1976, Colloq. Math. Soc. Janos Bolyai 18, 213-223 (1978)., 1978.
[19] F. R. K. Chung, A. L. Rosenberg, and L. Snyder. Perfect storage representations for families of data structures. SIAM J. Algebraic Discrete Methods, 4:548–565, 1983.
[20] I. H. Dinwoodie. A probability inequality for the occupation measure of a reversible Markov chain. Ann. Appl. Probab., 5(1):37–43, 1995.
[21] J. Edmonds. Minimum partition of a matroid into independent subsets. J. Res. Natl. Bur. Stand., Sect. B, 69:67–72, 1965.
[22] L. Esperet, G. Joret, and P. Morin. Sparse universal graphs for planarity. J. Lond. Math. Soc., II. Ser., 108(4):1333–1357, 2023.
[23] J. Friedman and N. Pippenger. Expanding graphs contain all small trees. Combinatorica, 7:71–76, 1987.
[24] A. Garg, Y. T. Lee, Z. Song, and N. Srivastava. A matrix expander Chernoff bound. In Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC ’18, Los Angeles, CA, USA, June 25–29, 2018, pages 1102–1114. New York, NY: Association for Computing Machinery (ACM), 2018.
[25] D. Gillman. A Chernoff bound for random walks on expander graphs. SIAM J. Comput., 27(4):1203–1220, 1998.
[26] A. D. Healy. Randomness-efficient sampling within NC¹. Comput. Complexity, 17(1):3–37, 2008.
[27] S. Hetterich, O. Parczyk, and Y. Person. On universal hypergraphs. Electron. J. Comb., 23(4):research paper p4.28, 16, 2016.
[28] S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications. Bull. Am. Math. Soc., New Ser., 43(4):439–561, 2006.
[29] N. Kahale. Large deviation bounds for Markov chains. Comb. Probab. Comput., 6(4):465–474, 1997.
[30] C. A. León and F. Perron. Optimal Hoeffding bounds for discrete reversible Markov chains. Ann. Appl. Probab., 14(2):958–970, 2004.
[31] P. Lezaud. Chernoff-type bound for finite markov chains. The Annals of Applied Probability, 8(3):849–867.
[32] A. Naor, S. Rao, and O. Regev. Concentration of Markov chains with bounded moments. Ann. Inst. Henri Poincaré, Probab. Stat., 56(3):2270–2280, 2020.
[33] R. Nenadov. Ramsey and universality properties of random graphs. PhD thesis, ETH Zurich, 2016.
[34] O. Parczyk and Y. Person. Spanning structures and universality in sparse hypergraphs. Random Struct. Algorithms, 49(4):819–844, 2016.
[35] S. Rao and O. Regev. A sharp tail bound for the expander random sampler. arXiv:1703.10205.
[36] R. P. Stanley. Enumerative Combinatorics. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2 edition, 2011.
[37] R. Wagner. Tail estimates for sums of variables sampled by a random walk. Comb. Probab. Comput., 17(2):307–316, 2008.

	$\displaystyle\mathbb{E}\left[\sum_{W\in\binom{U}{k}}I_{x}(W)\right]$	$\displaystyle\stackrel{{\scriptstyle\eqref{eq:estimate_IxW}}}{{\leq}}\sum_{W\in\binom{U}{k}}\sum_{f\in\{0,1\}^{k-1}}\left(\frac{1}{n}\right)^{k-\|f\|}\prod_{i\colon f_{i}=1}(\lambda/d)^{d_{i}(W)}$
		$\displaystyle=\sum_{f\in\{0,1\}^{k-1}}\left(\frac{1}{n}\right)^{k-\|f\|}\sum_{F\in\binom{U}{k-\|f\|}}\sum_{\begin{subarray}{c}W\in\binom{U}{k}\\ W_{\bar{f}}=F\end{subarray}}\prod_{i\colon f_{i}=1}(\lambda/d)^{d_{i}(W)}$
		$\displaystyle\stackrel{{\scriptstyle\eqref{eq:estimate_f}}}{{\leq}}\sum_{f\in\{0,1\}^{k-1}}\left(\frac{2^{8}}{n}\right)^{k-\|f\|}\binom{\|U\|}{k-\|f\|}\left(2^{9}D\;\frac{\lambda}{d}\right)^{\|f\|}$
		$\displaystyle\leq\sum_{i=0}^{k-1}\binom{k-1}{i}\frac{(2^{8}\|U\|/n)^{k-i}}{(k-i)!}\left(2^{9}D\;\frac{\lambda}{d}\right)^{i}.$