Multitrees in Random Graphs
Let $N=\binom{n}{2}$ and $s\geq 2$. Let $e_{i,j},\,i=1,2,\ldots,N,\,j=1,2,\ldots,s$ be $s$ independent permutations of the edges $E(K_n)$ of the complete graph $K_n$. A MultiTree is a set $I\subseteq [N]$ such that the edge sets $E_{I,j}$ induce spanning trees for $j=1,2,\ldots,s$. In this paper we study the following question: what is the smallest $m=m(n)$ such that w.h.p. $[m]$ contains a MultiTree. We prove a hitting time result for $s=2$ and an $O(n\log n)$ bound for $s\geq 3$.  more » « less
Award ID(s):
NSF-PAR ID:
10405082
Author(s) / Creator(s):
;
Date Published:
Journal Name:
The Electronic Journal of Combinatorics
Volume:
30
Issue:
1
ISSN:
1077-8926
Format(s):
Medium: X
National Science Foundation
##### More Like this
1. Abstract

Let $k_i\ (i=1,2,\ldots ,t)$ be natural numbers with $k_1>k_2>\cdots >k_t>0$, $k_1\geq 2$ and $t<k_1.$ Given real numbers $\alpha _{ji}\ (1\leq j\leq t,\ 1\leq i\leq s)$, we consider polynomials of the shape \begin{align*} &\varphi_i(x)=\alpha_{1i}x^{k_1}+\alpha_{2i}x^{k_2}+\cdots+\alpha_{ti}x^{k_t},\end{align*}and derive upper bounds for fractional parts of polynomials in the shape \begin{align*} &\varphi_1(x_1)+\varphi_2(x_2)+\cdots+\varphi_s(x_s),\end{align*}by applying novel mean value estimates related to Vinogradov’s mean value theorem. Our results improve on earlier Theorems of Baker (2017).

more » « less
2. Let { s j } j = 1 n \left \{ s_{j}\right \} _{j=1}^{n} be positive integers. We show that for any 1 ≤ L ≤ n , 1\leq L\leq n, ‖ ∏ j = 1 n ( 1 − z s j ) ‖ L ∞ ( | z | = 1 ) ≥ exp ⁡ ( 1 2 e L ( s 1 s 2 … s L ) 1 / L ) . \begin{equation*} \left \Vert \prod _{j=1}^{n}\left ( 1-z^{s_{j}}\right ) \right \Vert _{L_{\infty }\left ( \left \vert z\right \vert =1\right ) }\geq \exp \left ( \frac {1}{2e}\frac {L}{\left ( s_{1}s_{2}\ldots s_{L}\right ) ^{1/L}}\right ) . \end{equation*} In particular, this gives geometric growth if a positive proportion of the { s j } \left \{ s_{j}\right \} are bounded. We also show that when the { s j } \left \{ s_{j}\right \} grow regularly and faster than j ( log ⁡ j ) 2 + ε j\left ( \log j\right ) ^{2+\varepsilon } , some ε > 0 \varepsilon >0 , then the norms grow faster than exp ⁡ ( ( log ⁡ n ) 1 + δ ) \exp \left ( \left ( \log n\right ) ^{1+\delta }\right ) for some δ > 0 \delta >0 .
more » « less
3. Let ${\bf A}$ be an $n\times m$ matrix over $\mathbf{GF}_2$ where each column consists of $k$ ones, and let $M$ be an arbitrary fixed binary matroid. The matroid growth rate theorem implies that there is a constant $C_M$ such that $m\geq C_M n^2$ implies that the binary matroid induced by {\bf A} contains $M$ as a minor. We prove that if the columns of ${\bf A}={\bf A}_{n,m,k}$ are chosen \emph{randomly}, then there are constants $k_M, L_M$ such that $k\geq k_M$ and $m\geq L_M n$ implies that ${\bf A}$ contains $M$ as a minor w.h.p.
more » « less
4. Abstract In this paper we consider the following problem: let X k , be a Banach space with a normalised basis ( e (k, j) ) j , whose biorthogonals are denoted by ${(e_{(k,j)}^*)_j}$ , for $k\in\N$ , let $Z=\ell^\infty(X_k:k\kin\N)$ be their l ∞ -sum, and let $T:Z\to Z$ be a bounded linear operator with a large diagonal, i.e. , \begin{align*}\inf_{k,j} \big|e^*_{(k,j)}(T(e_{(k,j)})\big|>0.\end{align*} Under which condition does the identity on Z factor through T ? The purpose of this paper is to formulate general conditions for which the answer is positive.
more » « less
5. Abstract

Let $\gamma (t)=(P_{1}(t),\ldots ,P_{n}(t))$ where $P_{i}$ is a real polynomial with zero constant term for each $1\leq i\leq n$. We will show the existence of the configuration $\{x,x+\gamma (t)\}$ in sets of positive density $\epsilon$ in $[0,1]^{n}$ with a gap estimate $t\geq \delta (\epsilon )$ when $P_{i}$’s are arbitrary, and in $[0,N]^{n}$ with a gap estimate $t\geq \delta (\epsilon )N^{n}$ when $P_{i}$’s are of distinct degrees where $\delta (\epsilon )=\exp \left (-\exp \left (c\epsilon ^{-4}\right )\right )$ and $c$ only depends on $\gamma$. To prove these two results, decay estimates of certain oscillatory integral operators and Bourgain’s reduction are primarily utilised. For the first result, dimension-reducing arguments are also required to handle the linear dependency. For the second one, we will prove a stronger result instead, since then an anisotropic rescaling is allowed in the proof to eliminate the dependence of the decay estimate on $N$. And as a byproduct, using the strategy token to prove the latter case, we extend the corner-type Roth theorem previously proven by the first author and Guo.

more » « less