Limiting shape of the depth first search tree in an Erdős‐Rényi graph

We show that the profile of the tree constructed by the depth first search algorithm in the giant component of an Erd?s‐Rényi graph with N vertices and connection probability c/N with c > 1 converges to an explicit deterministic shape. This makes it possible to exhibit a long nonintersecting path of length , where ρ_c is the density of the giant component and Li₂ denotes the dilogarithm function.     

On Hamilton cycles in Erdős‐Rényi subgraphs of large graphs

Given a graph Γ_n=(V,E) on n vertices and m edges, we define the Erd?s‐Rényi graph process with host Γ_n as follows. A permutation e₁,…,e_m of E is chosen uniformly at random, and for t ≤ m we let Γ_n,t=(V,{e₁,…,e_t}). Suppose the minimum degree of Γ_n is δ(Γ_n) ≥ (1/2+ε)n for some constant ε>0. Then with high probability (An event holds with high probability (whp) if as n→∞.), Γ_n,t becomes Hamiltonian at the same moment that its minimum degree reaches 2. Given 0 ≤ p ≤ 1 let Γ_n,p be the Erd?s‐Rényi subgraph of Γ_n, obtained by retaining each edge independently with probability p. When δ(Γ_n) ≥ (1/2+ε)n, we provide a threshold for Hamiltonicity in Γ_n,p.     

A probabilistic approach to the leader problem in random graphs

We study the fixation time of the identity of the leader, that is, the most massive component, in the general setting of Aldous's multiplicative coalescent, which in an asymptotic sense describes the evolution of the component sizes of a wide array of near‐critical coalescent processes, including the classical Erd?s‐Rényi process. We show tightness of the fixation time in the “Brownian” regime, explicitly determining the median value of the fixation time to within an optimal O(1) window. This generalizes ?uczak's result for the Erd?s‐Rényi random graph using completely different techniques. In the heavy‐tailed case, in which the limit of the component sizes can be encoded using a thinned pure‐jump Lévy process, we prove that only one‐sided tightness holds. This shows a genuine difference in the possible behavior in the two regimes.     

Rapid mixing of Gibbs sampling on graphs that are sparse on average

Gibbs sampling also known as Glauber dynamics is a popular technique for sampling high dimensional distributions defined on graphs. Of special interest is the behavior of Gibbs sampling on the Erd?s‐Rényi random graph G(n,d/n), where each edge is chosen independently with probability d/n and d is fixed. While the average degree in G(n,d/n) is d(1 ‐ o(1)), it contains many nodes of degree of order log n/log log n. The existence of nodes of almost logarithmic degrees implies that for many natural distributions defined on G(n,p) such as uniform coloring (with a constant number of colors) or the Ising model at any fixed inverse temperature β, the mixing time of Gibbs sampling is at least n^{1+Ω(1/log log n)}. Recall that the Ising model with inverse temperature β defined on a graph G = (V,E) is the distribution over {±}^Vgiven by . High degree nodes pose a technical challenge in proving polynomial time mixing of the dynamics for many models including the Ising model and coloring. Almost all known sufficient conditions in terms of β or number of colors needed for rapid mixing of Gibbs samplers are stated in terms of the maximum degree of the underlying graph. In this work, we show that for every d < ∞ and the Ising model defined on G (n, d/n), there exists a β_d > 0, such that for all β < β_d with probability going to 1 as n →∞, the mixing time of the dynamics on G (n, d/n) is polynomial in n. Our results are the first polynomial time mixing results proven for a natural model on G (n, d/n) for d > 1 where the parameters of the model do not depend on n. They also provide a rare example where one can prove a polynomial time mixing of Gibbs sampler in a situation where the actual mixing time is slower than npolylog(n). Our proof exploits in novel ways the local tree like structure of Erd?s‐Rényi random graphs, comparison and block dynamics arguments and a recent result of Weitz. Our results extend to much more general families of graphs which are sparse in some average sense and to much more general interactions. In particular, they apply to any graph for which every vertex v of the graph has a neighborhood N(v) of radius O(log n) in which the induced sub‐graph is a tree union at most O(log n) edges and where for each simple path in N(v) the sum of the vertex degrees along the path is O(log n). Moreover, our result apply also in the case of arbitrary external fields and provide the first FPRAS for sampling the Ising distribution in this case. We finally present a non Markov Chain algorithm for sampling the distribution which is effective for a wider range of parameters. In particular, for G(n, d/n) it applies for all external fields and β < β_d, where d tanh(β_d) = 1 is the critical point for decay of correlation for the Ising model on G(n, d/n). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Spectra of large diluted but bushy random graphs

We compute an asymptotic expansion in of the limit in of the empirical spectral measure of the adjacency matrix of an Erd?s‐Rényi random graph with vertices and parameter . We present two different methods, one of which is valid for the more general setting of locally tree‐like graphs. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 49, 160–184, 2016     

The missing log in large deviations for triangle counts

This paper solves the problem of sharp large deviation estimates for the upper tail of the number of triangles in an Erd?s‐Rényi random graph, by establishing a logarithmic factor in the exponent that was missing till now. It is possible that the method of proof may extend to general subgraph counts. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 437–451, 2012     

For most graphs H,most H‐free graphs have a linear homogeneous set

Erd?s and Hajnal conjectured that for every graph H there is a constant such that every graph G that does not have H as an induced subgraph contains a clique or a stable set of order . The conjecture would be false if we set ; however, in an asymptotic setting, we obtain this strengthened form of Erd?s and Hajnal's conjecture for almost every graph H, and in particular for a large class of graphs H defined by variants of the colouring number. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 45, 343–361, 2014     

Categorical Abstract Algebraic Logic: Algebraic Semantics for (\documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\bf{\pi }$\end{document})‐Institutions

Various aspects of the work of Blok and Rebagliato on the algebraic semantics for deductive systems are studied in the context of logics formalized as π‐institutions. Three kinds of semantics are surveyed: institution, matrix (system) and algebraic (system) semantics, corresponding, respectively, to the generalized matrix, matrix and algebraic semantics of the theory of sentential logics. After some connections between matrix and algebraic semantics are revealed, it is shown that every (finitary) N‐rule based extension of an N‐rule based π‐institution possessing an algebraic semantics also possesses an algebraic semantics. This result abstracts one of the main theorems of Blok and Rebagliato. An attempt at a Blok‐Rebagliato‐style characterization of those π‐institutions with a mono‐unary category of natural transformations on their sentence functors having an algebraic semantics is also made. Finally, a necessary condition for a π‐institution to possess an algebraic semantics is provided.     

Stability results for random discrete structures

Two years ago, Conlon and Gowers, and Schacht proved general theorems that allow one to transfer a large class of extremal combinatorial results from the deterministic to the probabilistic setting. Even though the two papers solve the same set of long‐standing open problems in probabilistic combinatorics, the methods used in them vary significantly and therefore yield results that are not comparable in certain aspects. In particular, the theorem of Schacht yields stronger probability estimates, whereas the one of Conlon and Gowers also implies random versions of some structural statements such as the famous stability theorem of Erd?s and Simonovits. In this paper, we bridge the gap between these two transference theorems. Building on the approach of Schacht, we prove a general theorem that allows one to transfer deterministic stability results to the probabilistic setting. We then use this theorem to derive several new results, among them a random version of the Erd?s‐Simonovits stability theorem for arbitrary graphs, extending the result of Conlon and Gowers, who proved such a statement for so‐called strictly 2‐balanced graphs. The main new idea, a refined approach to multiple exposure when considering subsets of binomial random sets, may be of independent interest.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 269‐289, 2014     

Global solution with \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$ \mathcal {C}^{k}$\end{document}‐estimates for \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\bar{\partial }$\end{document}‐equation on q‐convex intersections

We construct a global solution with $\mathcal {C}^{k}$‐estimates for the $\bar{\partial }$‐equation on q‐convex intersections.     

The Marčenko‐Pastur law for sparse random bipartite biregular graphs

We prove that the empirical spectral distribution of a (d_L, d_R)‐biregular, bipartite random graph, under certain conditions, converges to a symmetrization of the Mar?enko‐Pastur distribution of random matrix theory. This convergence is not only global (on fixed‐length intervals) but also local (on intervals of increasingly smaller length). Our method parallels the one used previously by Dumitriu and Pal (2012). © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 48, 313–340, 2016