More Like this

1. Multitrees in random graphs

   https://doi.org/10.37236/10804  

   Frieze, A.; Pegden, W. (January 2023, The Electronic journal of combinatorics)

   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 {\em 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
2. Multitrees in Random Graphs

   https://doi.org/10.37236/10804  

   Frieze, Alan; Pegden, Wesley (January 2023, The Electronic Journal of Combinatorics)

   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
3. Upper Tail Large Deviations for Arithmetic Progressions in a Random Set

   https://doi.org/10.1093/imrn/rny022  

   Bhattacharya, Bhaswar B; Ganguly, Shirshendu; Shao, Xuancheng; Zhao, Yufei (March 2018, International Mathematics Research Notices)

   null (Ed.)

   Abstract Let Xk denote the number of k-term arithmetic progressions in a random subset of $$\mathbb{Z}/N\mathbb{Z}$$ or $$\{1, \dots , N\}$$ where every element is included independently with probability p. We determine the asymptotics of $$\log \mathbb{P}\big (X_{k} \ge \big (1+\delta \big ) \mathbb{E} X_{k}\big )$$ (also known as the large deviation rate) where p → 0 with $$p \ge N^{-c_{k}}$$ for some constant ck > 0, which answers a question of Chatterjee and Dembo. The proofs rely on the recent nonlinear large deviation principle of Eldan, which improved on earlier results of Chatterjee and Dembo. Our results complement those of Warnke, who used completely different methods to estimate, for the full range of p, the large deviation rate up to a constant factor. 

   more » « less
4. Turán Number for Bushes

   https://doi.org/10.37236/12197  

   Kostochka, Alexandr; Füredi, Zoltán (October 2025, The Electronic Journal of Combinatorics)

   Let $$ a,b \in {\bf Z}^+$$, $r=a + b$, and let $$T$$ be a tree with parts $$U = \{u_1,u_2,\dots,u_s\}$$ and $$V = \{v_1,v_2,\dots,v_t\}$$. Let $$U_1, \dots ,U_s$$ and $$V_1, \dots, V_t$$ be disjoint sets, such that $$|U_i|=a$$ and $$|V_j|=b$$ for all $i,j$. The $(a,b)$-blowup of $$T$$ is the $$r$$-uniform hypergraph with edge set$$ {\{U_i \cup V_j : u_iv_j \in E(T)\}.}$$ We use the $$\Delta$$-systems method to prove the following Turán-type result. Suppose $$a,b,t\in {\bf Z}^+$$, $$r=a+b\geq 3$$, $$a\geq 2$$, and $$T$$ is a fixed tree of diameter $$4$$ in which the degree of the center vertex is $$t$$. Then there exists a $C=C(r,t,T)>0$ such that $$ |\mathcal{H}|\leq (t-1){n\choose r-1} +Cn^{r-2}$$ for every $$n$$-vertex $$r$$-uniform hypergraph $$\mathcal{H}$$ not containing an $(a,b)$-blowup of $$T$$. This is asymptotically exact when $$t\leq |V(T)|/2$$. A stability result is also presented. 

   more » « less
5. On Weissler’s Conjecture on the Hamming Cube I

   https://doi.org/10.1093/imrn/rnaa363  

   Ivanisvili, P; Nazarov, F (December 2020, International Mathematics Research Notices)

   null (Ed.)

   Abstract Let $$1\leq p \leq q <\infty $$ and let $$w \in \mathbb{C}$$. Weissler conjectured that the Hermite operator $$e^{w\Delta }$$ is bounded as an operator from $$L^{p}$$ to $$L^{q}$$ on the Hamming cube $$\{-1,1\}^{n}$$ with the norm bound independent of $$n$$ if and only if $$\begin{align*} |p-2-e^{2w}(q-2)|\leq p-|e^{2w}|q. \end{align*}$$It was proved in [ 1], [ 2], and [ 17] in all cases except $$2<p\leq q <3$$ and $$3/2<p\leq q <2$$, which stood open until now. The goal of this paper is to give a full proof of Weissler’s conjecture in the case $p=q$. Several applications will be presented. 

   more » « less