Search

Benjamini, Yadin, and Yehudayoff (2007) showed that if the maximum degree of a graph $G$ is 'sub-logarithmic,' then the typical range of random $\mathbb Z$-homomorphisms is super-constant. Furthermore, they showed that there is a sharp transition on the range of random $\mathbb Z$-homomorphisms on the graph $C_{n,k}$, the tensor product of the $n$-cycle and the complete graph on $k$ vertices with self-loops, around $k=2\log n$. We extend (to some extent) their results to random $M$-Lipschitz functions and random real-valued Lipschitz functions., Comment: 16 pages, 1 figure

Dedekind's problem, dating back to 1897, asks for the total number $\psi(n)$ of antichains contained in the Boolean lattice $B_n$ on $n$ elements. We study Dedekind's problem using a recently developed method based on the cluster expansion from statistical physics and as a result, obtain several new results on the number and typical structure of antichains in $B_n$. We obtain detailed estimates for both $\psi(n)$ and the number of antichains of size $\beta \binom{n}{\lfloor n/2 \rfloor}$ for any fixed $\beta>0$. We also establish a sparse version of Sperner's theorem: we determine the sharp threshold and scaling window for the property that almost every antichain of size $m$ is contained in a middle layer of $B_n$.

We establish a refined version of a graph container lemma due to Galvin and discuss several applications related to the hard-core model on bipartite expander graphs. Given a graph $G$ and $\lambda>0$, the hard-core model on $G$ at activity $\lambda$ is the probability distribution $\mu_{G,\lambda}$ on independent sets in $G$ given by $\mu_{G,\lambda}(I)\propto \lambda^{|I|}$. As one of our main applications, we show that the hard-core model at activity $\lambda$ on the hypercube $Q_d$ exhibits a `structured phase' for $\lambda= \Omega( \log^2 d/d^{1/2})$ in the following sense: in a typical sample from $\mu_{Q_d,\lambda}$, most vertices are contained in one side of the bipartition of $Q_d$. This improves upon a result of Galvin which establishes the same for $\lambda=\Omega(\log d/ d^{1/3})$. As another application, we establish a fully polynomial-time approximation scheme (FPTAS) for the hard-core model on a $d$-regular bipartite $\alpha$-expander, with $\alpha>0$ fixed, when $\lambda= \Omega( \log^2 d/d^{1/2})$. This improves upon the bound $\lambda=\Omega(\log d/ d^{1/4})$ due to the first author, Perkins and Potukuchi. We discuss similar improvements to results of Galvin-Tetali, Balogh-Garcia-Li and Kronenberg-Spinka.

Given a connected finite graph $G$, an integer-valued function $f$ on $V(G)$ is called $M$-Lipschitz if the value of $f$ changes by at most $M$ along the edges of $G$. In 2013, Peled, Samotij, and Yehudayoff showed that random $M$-Lipschitz functions on graphs with sufficiently good expansion typically exhibit small fluctuations, giving sharp bounds on the typical range of such functions, assuming $M$ is not too large. We prove that the same conclusion holds under a relaxed expansion condition and for larger $M$, (partially) answering questions of Peled et al. Our techniques involve a combination of Sapozhenko's graph container methods and entropy methods from information theory., Comment: 24 pages

In this expository article, we give a gentle introduction to the Erd\H{o}s-R\'enyi random graphs and threshold phenomena that they exhibit. We also mildly introduce the Kahn-Kalai Conjecture with several intuitive examples, mainly targeting the general audience., Comment: Section 5 is expanded in v2. 10 pages, many figures, to appear in Notices of the AMS

We give a short and self-contained argument that shows that, for any positive integers $t$ and $n$ with $t =O\Bigl(\frac{n}{\log n}\Bigr)$, the number $\alpha([t]^n)$ of antichains of the poset $[t]^n$ is at most \[\exp_2\Bigl(1+O\Bigl(\Bigl(\frac{t\log^3 n}{n}\Bigr)^{1/2}\Bigr)\Bigr)N(t,n)\,,\] where $N(t,n)$ is the size of a largest level of $[t]^n$. This, in particular, says that if $t \ll n/\log^3 n$ as $n \rightarrow \infty$, then $\log\alpha([t]^n)=(1+o(1))N(t,n)$, giving a (partially) positive answer to a question of Moshkovitz and Shapira for $t, n$ in this range. Particularly for $t=3$, we prove a better upper bound: \[\log\alpha([3]^n)\le(1+4\log 3/n)N(3,n),\] which is the best known upper bound on the number of antichains of $[3]^n$., Comment: 13 pages, 1 figure

For an odd integer $n = 2d-1$, let $\mathcal B_d$ be the subgraph of the hypercube $Q_n$ induced by the two largest layers. In this paper, we describe the typical structure of proper $q$-colorings of $V(\mathcal B_d)$ and give asymptotics on the number of them. The proofs use various tools including information theory (entropy), Sapozhenko's graph container method and a recently developed method of M. Jenssen and W. Perkins that combines Sapozhenko's graph container lemma with the cluster expansion for polymer models from statistical physics., Comment: 31 pages

For appropriate Gaussian processes, as a corollary of the majorizing measure theorem, Michel Talagrand (1987) proved that the event that the supremum is significantly larger than its expectation can be covered by a set of half-spaces whose sum of measures is small. We prove a conjecture of Talagrand that is the analog of this result in the Bernoulli-$p$ setting, and answer a question of Talagrand on the analogous result for general positive empirical processes., Comment: Final version, 22 pages

Proving the ``expectation-threshold'' conjecture of Kahn and Kalai, we show that for any increasing property $\mathcal{F}$ on a finite set $X$, $$p_c(\mathcal{F})=O(q(\mathcal{F})\log \ell(\mathcal{F})),$$ where $p_c(\mathcal{F})$ and $q(\mathcal{F})$ are the threshold and ``expectation threshold'' of $\mathcal{F}$, and $\ell(\mathcal{F})$ is the maximum of $2$ and the maximum size of a minimal member of $\mathcal{F}$.

We address a special case of a conjecture of M. Talagrand relating two notions of "threshold" for an increasing family $\mathcal F$ of subsets of a finite set $V$. The full conjecture implies equivalence of the "Fractional Expectation-Threshold Conjecture," due to Talagrand and recently proved by the authors and B. Narayanan, and the (stronger) "Expectation-Threshold Conjecture" of the second author and G. Kalai. The conjecture under discussion here says there is a fixed $L$ such that if, for a given $\mathcal F$, $p\in [0,1]$ admits $\lambda:2^V \rightarrow \mathbb R^+$ with \[ \mbox{$\sum_{S\subseteq F}\lambda_S\ge 1 ~~\forall F\in \mathcal F$} \] and \[ \mbox{$\sum_S\lambda_Sp^{|S|} \le 1/2$} \] (a.k.a. $\mathcal F$ is weakly $p$-small), then $p/L$ admits such a $\lambda$ taking values in $\{0,1\}$ ($\mathcal F$ is $(p/L)$-small). Talagrand showed this when $\lambda$ is supported on singletons and suggested, as a more challenging test case, proving it when $\lambda$ is supported on pairs. The present work provides such a proof., Comment: 11 pages

Let $Q_d$ be the $d$-dimensional Hamming cube and $N=|V(Q_d)|=2^d$. An independent set $I$ in $Q_d$ is called balanced if $I$ contains the same number of even and odd vertices. We show that the logarithm of the number of balanced independent sets in $Q_d$ is \[(1-\Theta(1/\sqrt d))N/2.\] The key ingredient of the proof is an improved version of "Sapozhenko's graph container lemma.", Comment: 6 pages. Comments are welcome!

Resolving a conjecture of K\"uhn and Osthus from 2012, we show that $p= 1/\sqrt{n}$ is the threshold for the random graph $G_{n,p}$ to contain the square of a Hamilton cycle., Comment: 6 pages

A celebrated conjecture of Zs. Tuza says that in any (finite) graph, the minimum size of a cover of triangles by edges is at most twice the maximum size of a set of edge-disjoint triangles. Resolving a recent question of Bennett, Dudek, and Zerbib, we show that this is true for random graphs; more precisely: \[ \mbox{for any $p=p(n)$, $\mathbb P(\mbox{$G_{n,p}$ satisfies Tuza's Conjecture})\rightarrow 1 $ (as $n\rightarrow\infty$).} \], Comment: References updated

Proving a conjecture of Talagrand, a fractional version of the 'expectation-threshold' conjecture of Kalai and the second author, we show for any increasing family $F$ on a finite set $X$ that $p_c (F) =O( q_f (F) \log \ell(F))$, where $p_c(F)$ and $q_f(F)$ are the threshold and 'fractional expectation-threshold' of $F$, and $\ell(F)$ is the largest size of a minimal member of $F$. This easily implies several heretofore difficult results and conjectures in probabilistic combinatorics, including thresholds for perfect hypergraph matchings (Johansson--Kahn--Vu), bounded-degree spanning trees (Montgomery), and bounded-degree spanning graphs (new). We also resolve (and vastly extend) the 'axial' version of the random multi-dimensional assignment problem (earlier considered by Martin--M\'{e}zard--Rivoire and Frieze--Sorkin). Our approach builds on a recent breakthrough of Alweiss, Lovett, Wu and Zhang on the Erd\H{o}s--Rado 'Sunflower Conjecture'., Comment: 16 pages, submitted, now includes some discussion of applications

Our basic result, an isoperimetric inequality for Hamming cube $Q_n$, can be written: \[ \int h_A^\beta d\mu \ge 2 \mu(A)(1-\mu(A)). \] Here $\mu$ is uniform measure on $V=\{0,1\}^n$ ($=V(Q_n)$); $\beta=\log_2(3/2)$; and, for $S\subseteq V$ and $x\in V$, \[ h_S(x) = \begin{cases} d_{V \setminus S}(x) &\mbox{ if } x \in S, 0 &\mbox{ if } x \notin S \end{cases} \] (where $d_T(x)$ is the number of neighbors of $x$ in $T$). This implies inequalities involving mixtures of edge and vertex boundaries, with related stability results, and suggests some more general possibilities. One application, a stability result for the set of edges connecting two disjoint subsets of $V$ of size roughly $|V|/2$, is a key step in showing that the number of maximal independent sets in $Q_n$ is $(1+o(1))2n\exp_2[2^{n-2}]$. This asymptotic statement, whose proof will appear separately, was the original motivation for the present work., Comment: 12 pages, 1 figure (v2: reference updated)

Let $Q_n$ be the $n$-dimensional Hamming cube and $N=2^n$. We prove that the number of maximal independent sets in $Q_n$ is asymptotically \[2n2^{N/4},\] as was conjectured by Ilinca and the first author in connection with a question of Duffus, Frankl and R\"odl. The value is a natural lower bound derived from a connection between maximal independent sets and induced matchings. The proof that it is also an upper bound draws on various tools, among them "stability" results for maximal independent set counts and old and new results on isoperimetric behavior in $Q_n$., Comment: 20 pages (v2: reference updated)

Answering questions of Y. Rabinovich, we prove "stability" versions of upper bounds on maximal independent set counts in graphs under various restrictions. Roughly these say that being close to the maximum implies existence of a large induced matching or triangle matching (depending on assumptions)., Comment: 11 pages

Let $Q_d$ be the $d$-dimensional hypercube and $N=2^d$. We prove that the number of (proper) 4-colorings of $Q_d$ is asymptotically \[6e2^N,\] as was conjectured by Engbers and Galvin in 2012. The proof uses a combination of information theory (entropy) and isoperimetric ideas originating in work of Sapozhenko in the 1980's., Comment: 15 pages, 2 figures

This paper presents a collection of experimental results regarding permutation pattern avoidance, focusing on cases where there are "many" patterns to be avoided., Comment: 9 pages. Accompanied by several Maple programs, and input and output files that may be obtained from http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/pamp.html