Search

The analysis of large simple graphs with extreme values of the densities of edges and triangles has been extended to the statistical structure of typical graphs of fixed intermediate densities, by the use of large deviations of Erdoes-Renyi graphs. We prove that the typical graph exhibits sharp singularities as the constraining densities vary between different curves of extreme values, and we determine the precise nature of the singularities. The extension to graphs with fixed densities of edges and k-cycles for odd k>3 is straightforward and we note the simple changes in the proof.

We analyze ensembles of random networks with fixed numbers of edges, triangles, and nodes. In the limit as the number of nodes goes to infinity, this model is known to exhibit sharp phase transitions as the density of edges and triangles is varied. In this paper we study finite size effects in ensembles where the number of nodes is between 30 and 66. Despite the small number of nodes, the phases and phase transitions are clearly visible. Concentrating on 54 nodes and one particular phase transition, we use spectral data to examine the structure of a typical graph in each phase, and see that is it very similar to the graphon that describes the system as n diverges. We further investigate how graphs change their structure from that of one phase to the other under a natural edge flip dynamics in which the number of triangles is either forced downwards or allowed to drift upwards. In each direction, spectral data shows that the change occurs in three stages: a very fast stage of about 100 edge flips, in which the triangle count reaches the targeted value, a slower second stage of several thousand edge flips in which the graph adopts the qualitative features of the new phase, and a very slow third stage, requiring hundreds of thousands of edge flips, in which the fine details of the structure equilibrate.

We prove moderate deviations bounds for the lower tail of the number of odd cycles in a $\calG(n, m)$ random graph. We show that the probability of decreasing triangle density by $t^3$, is $\exp(-\Theta(n^2 t^2))$ whenever $n^{-3/4} \ll t^3 \ll 1$, while for $k \ge 5$ we give the same estimate for the probability of decreasing the $k$-cycle density by $t^k$, but for the larger range $n^{-1} \ll t^k \ll 1$. When $m \ge \frac 12 \binom n2$, we also find the leading coefficient in the exponent. This complements results of Goldschmidt et al., who showed that for $n^{-3/2} \ll t^k \ll n^{-1}$, the probability is $\exp(-\Theta(n^3 t^{2k}))$. That is, deviations of order smaller than $n^{-1}$ behave like small deviations, and deviations of order larger than $n^{-3/4}$ (for triangles) or $n^{-1}$ (for $k$-cycles with $k \ge 5$) behave like large deviations. For triangles, we conjecture that a sharp change between the two regimes occurs for deviations of size $n^{-3/4}$, which we associate with a single large negative eigenvalue of the adjacency matrix becoming responsible for almost all of the cycle deficit. Our results can be interpreted as finite size effects in phase transitions in constrained random graphs.

We prove Ehrhard’s inequality using interpolation along the Ornstein–Uhlenbeck semi-group. We also provide an improved Jensen inequality for Gaussian variables that might be of independent interest.

The Standard Simplex Conjecture and the Plurality is Stablest Conjecture are two conjectures stating that certain partitions are optimal with respect to Gaussian and discrete noise stability respectively. These two conjectures are natural generalizations of the Gaussian noise stability result by Borell (1985) and the Majority is Stablest Theorem (2004). Here we show that the standard simplex is not the most stable partition in Gaussian space and that Plurality is not the most stable low influence partition in discrete space for every number of parts k ≥ 3, for every value ρ ≠ 0 of the noise and for every prescribed measure for the different parts as long as they are not all equal to 1/k. Our results do not contradict the original statements of the Plurality is Stablest and Standard Simplex Conjectures in their original statements concerning partitions to sets of equal measure. However, they indicate that if these conjectures are true, their veracity and their proofs will crucially rely on assuming that the sets are of equal measures, in stark contrast to Borell’s result, the Majority is Stablest Theorem and many other results in isoperimetric theory. Given our results it is natural to ask for (conjectured) partitions achieving the optimum noise stability.

Consider algorithms with unbounded computation time that probe the entries of the adjacency matrix of an $n$ vertex graph, and need to output a clique. We show that if the input graph is drawn at random from $G_{n,\frac{1}{2}}$ (and hence is likely to have a clique of size roughly $2\log n$), then for every $\delta < 2$ and constant $\ell$, there is an $\alpha < 2$ (that may depend on $\delta$ and $\ell$) such that no algorithm that makes $n^{\delta}$ probes in $\ell$ rounds is likely (over the choice of the random graph) to output a clique of size larger than $\alpha \log n$., Comment: 15 pages

The planted partition model (also known as the stochastic blockmodel) is a classical cluster-exhibiting random graph model that has been extensively studied in statistics, physics, and computer science. In its simplest form, the planted partition model is a model for random graphs on $$n$$ nodes with two equal-sized clusters, with an between-class edge probability of $$q$$ and a within-class edge probability of $$p$$ . Although most of the literature on this model has focused on the case of increasing degrees (ie. $$pn, qn \rightarrow \infty $$ as $$n \rightarrow \infty $$ ), the sparse case $$p, q = O(1/n)$$ is interesting both from a mathematical and an applied point of view. A striking conjecture of Decelle, Krzkala, Moore and Zdeborova based on deep, non-rigorous ideas from statistical physics gave a precise prediction for the algorithmic threshold of clustering in the sparse planted partition model. In particular, if $$p = a/n$$ and $$q = b/n$$ , then Decelle et al. conjectured that it is possible to cluster in a way correlated with the true partition if $$(a - b)^2 > 2(a + b)$$ , and impossible if $$(a - b)^2 < 2(a + b)$$ . By comparison, the best-known rigorous result is that of Coja-Oghlan, who showed that clustering is possible if $$(a - b)^2 > C (a + b)$$ for some sufficiently large $$C$$ . We prove half of their prediction, showing that it is indeed impossible to cluster if $$(a - b)^2 < 2(a + b)$$ . Furthermore we show that it is impossible even to estimate the model parameters from the graph when $$(a - b)^2 < 2(a + b)$$ ; on the other hand, we provide a simple and efficient algorithm for estimating $$a$$ and $$b$$ when $$(a - b)^2 > 2(a + b)$$ . Following Decelle et al, our work establishes a rigorous connection between the clustering problem, spin-glass models on the Bethe lattice and the so called reconstruction problem. This connection points to fascinating applications and open problems.

Suppose Alice and Bob receive strings $X=(X_1,...,X_n)$ and $Y=(Y_1,...,Y_n)$ each uniformly random in $[s]^n$ but so that $X$ and $Y$ are correlated . For each symbol $i$, we have that $Y_i = X_i$ with probability $1-\eps$ and otherwise $Y_i$ is chosen independently and uniformly from $[s]$. Alice and Bob wish to use their respective strings to extract a uniformly chosen common sequence from $[s]^k$ but without communicating. How well can they do? The trivial strategy of outputting the first $k$ symbols yields an agreement probability of $(1 - \eps + \eps/s)^k$. In a recent work by Bogdanov and Mossel it was shown that in the binary case where $s=2$ and $k = k(\eps)$ is large enough then it is possible to extract $k$ bits with a better agreement probability rate. In particular, it is possible to achieve agreement probability $(k\eps)^{-1/2} \cdot 2^{-k\eps/(2(1 - \eps/2))}$ using a random construction based on Hamming balls, and this is optimal up to lower order terms. In the current paper we consider the same problem over larger alphabet sizes $s$ and we show that the agreement probability rate changes dramatically as the alphabet grows. In particular we show no strategy can achieve agreement probability better than $(1-\eps)^k (1+\delta(s))^k$ where $\delta(s) \to 0$ as $s \to \infty$. We also show that Hamming ball based constructions have {\em much lower} agreement probability rate than the trivial algorithm as $s \to \infty$. Our proofs and results are intimately related to subtle properties of hypercontractive inequalities., Comment: 15 pages, 1 figure

Benjamini, Kalai and Schramm showed that a monotone function $f : \{-1,1\}^n \to \{-1,1\}$ is noise stable if and only if it is correlated with a half-space (a set of the form $\{x: \langle x, a\rangle \le b\}$). We study noise stability in terms of correlation with half-spaces for general (not necessarily monotone) functions. We show that a function $f: \{-1, 1\}^n \to \{-1, 1\}$ is noise stable if and only if it becomes correlated with a half-space when we modify $f$ by randomly restricting a constant fraction of its coordinates. Looking at random restrictions is necessary: we construct noise stable functions whose correlation with any half-space is $o(1)$. The examples further satisfy that different restrictions are correlated with different half-spaces: for any fixed half-space, the probability that a random restriction is correlated with it goes to zero. We also provide quantitative versions of the above statements, and versions that apply for the Gaussian measure on $\mathbb{R}^n$ instead of the discrete cube. Our work is motivated by questions in learning theory and a recent question of Khot and Moshkovitz., 23 pages

We study the predictive performance of l 1-regularized linear regression in a model-free setting, including the case where the number of covariates is substantially larger than the sample size. We introduce a new analysis method that avoids the boundedness problems that typically arise in model-free empirical minimization. Our technique provides an answer to a conjecture of Greenshtein and Ritov (Bernoulli 10(6):971–988, 2004) regarding the “persistence” rate for linear regression and allows us to prove an oracle inequality for the error of the regularized minimizer. It also demonstrates that empirical risk minimization gives optimal rates (up to log factors) of convex aggregation of a set of estimators of a regression function.