We prove that a uniformly random automaton with \( n \) states on a 2-letter alphabet has a synchronizing word of length \(O(n^{1/2}\log n)\) with high probability (w.h.p.). That is to say, w.h.p. there exists a word \(\omega\) of such length, and a state \(v_{0}\) , such that \(\omega\) sends all states to \(v_{0}\) . Prior to this work, the best upper bound was the quasilinear bound \(O(n\log^{3}n)\) due to Nicaud [ 26 ]. The correct scaling exponent had been subject to various estimates by other authors between 0.5 and 0.56 based on numerical simulations, and our result confirms that the smallest one indeed gives a valid upper bound (with a log factor). Our proof introduces the concept of \( w \) -trees, for a word \( w \) , that is, automata in which the \( w \) -transitions induce a (loop-rooted) tree. We prove a strong structure result that says that, w.h.p., a random automaton on \( n \) states is a \( w \) -tree for some word \( w \) of length at most \((1+\epsilon)\log_{2}(n)\) , for any \(\epsilon > 0\) . The existence of the (random) word \( w \) is proved by the probabilistic method. This structure result is key to proving that a short synchronizing word exists.

We prove that a uniformly random automaton with n states on a 2-letter alphabet has a synchronizing word of length with high probability (w.h.p.). That is to say, w.h.p. there exists a word ω of such length, and a state v0, such that ω sends all states to v0. This confirms a conjecture of Kisielewicz, Kowalski, Szykuła [KKS13] based on numerical simulations, up to a log factor - the previous best partial result towards the conjecture was the quasilinear bound O(n log3 n) due to Nicaud [Nic19]. Moreover, the synchronizing word ω we obtain has small entropy, in the sense that it can be encoded with only O(log(n)) bits w.h.p.. Our proof introduces the concept of ω-trees, for a word ω, that is, automata in which the ω-transitions induce a (loop-rooted) tree. We prove a strong structure result that says that, w.h.p., a random automaton on n states is a ω-tree for some word ω of length at most (1 + ε) log2(n), for any ε > 0. The existence of the (random) word ω is proved by the probabilistic method. This structure result is key to proving that a short synchronizing word exists.

We consider bond percolation on random graphs with given degrees and bounded average degree. In particular, we consider the order of the largest component after the random deletion of the edges of such a random graph. We give a rough characterization of those degree distributions for which bond percolation with high probability leaves a component of linear order, known usually as a giant component. We show that essentially the critical condition has to do with the tail of the degree distribution. Our proof makes use of recent technique which is based on the switching method and avoids the use of the classic configuration model on degree sequences that have a limiting distribution. Thus our results hold for sparse degree sequences without the usual restrictions that accompany the configuration model.

A famous theorem of Dirac states that any graph on $n$ vertices with minimum degree at least $n/2$ has a Hamilton cycle. Such graphs are called Dirac graphs. Strengthening this result, we show the existence of rainbow Hamilton cycles in $\mu n$-bounded colorings of Dirac graphs for sufficiently small $\mu >0$.

A well-known conjecture in computer science and statistical physics is that Glauber dynamics on the set of k-colorings of a graph G on n vertices with maximum degree Δ is rapidly mixing for k ≥ Δ + 2. In FOCS 1999, Vigoda [43] showed that the flip dynamics (and therefore also Glauber dynamics) is rapidly mixing for any . It turns out that there is a natural barrier at , below which there is no one-step coupling that is contractive with respect to the Hamming metric, even for the flip dynamics. We use linear programming and duality arguments to fully characterize the obstructions to going beyond . These extremal configurations turn out to be quite brittle, and in this paper we use this to give two proofs that the Glauber dynamics is rapidly mixing for any for some absolute constant ε0 > 0. This is the first improvement to Vigoda's result that holds for general graphs. Our first approach analyzes a variable-length coupling in which these configurations break apart with high probability before the coupling terminates, and our other approach analyzes a one-step path coupling with a new metric that counts the extremal configurations. Additionally, our results extend to list coloring, a widely studied generalization of coloring, where the previously best known results required k > 2Δ.

We give asymptotically exact values for the treewidth ${tw}(G)$ of a random geometric graph $G\in{\mathcal G(n,r)}$ in $[0,\sqrt{n}]^2$. More precisely, let $r_c$ denote the threshold radius for the appearance of the giant component in ${\mathcal G(n,r)}$. We then show that for any constant $0 < r < r_c$, ${tw}(G)=\Theta(\frac{\log n}{\log \log n})$, and for $c$ being sufficiently large, and $r=r(n) \geq c$, ${tw}(G)=\Theta(r \sqrt{n})$. Our proofs show that for the corresponding values of $r$ the same asymptotic bounds also hold for the pathwidth and the treedepth of a random geometric graph.

A class of graphs is bridge-addable if given a graph $G$ in the class, any graph obtained by adding an edge between two connected components of $G$ is also in the class. The authors recently proved a conjecture of McDiarmid, Steger, and Welsh stating that if $\mathcal{G}$ is bridge-addable and $G_n$ is a uniform $n$-vertex graph from $\mathcal{G}$, then $G_n$ is connected with probability at least $(1+o_n(1))e^{-1/2}$. The constant $e^{-1/2}$ is best possible since it is reached for the class of all forests. In this paper we prove a form of uniqueness in this statement: if $\mathcal{G}$ is a bridge-addable class and the random graph $G_n$ is connected with probability close to $e^{-1/2}$, then $G_n$ is asymptotically close to a uniform $n$-vertex random forest in some local sense. For example, if the probability converges to $e^{-1/2}$, then $G_n$ converges in the sense of Benjamini-Schramm to the uniform infinite random forest $F_\infty$. This result is reminiscent of so-called "stability results" in extremal graph theory, with the difference that here the stable extremum is not a graph but a graph class.

The traditional Erdos-Renyi model of a random network is of little use in modelling the type of complex networks which modern researchers study. In this graph, every pair of vertices is equally likely to be connected by an edge. However, 21st century networks are of diverse nature and usually exhibit inhomogeneity among their nodes. This motivates the study, for a fixed degree sequence D=(d1, ..., dn), of a uniformly chosen simple graph G(D) on {1, ..., n} where the vertex i has degree di. In this paper, we study the existence of a giant component in G(D). A heuristic argument suggests that a giant component in G(D) will exist provided that the sum of the squares of the degrees is larger than twice the sum of the degrees. In 1995, Molloy and Reed essentially proved this to be the case when the degree sequence D under consideration satisfies certain technical conditions [Random Structures & Algorithms, 6:161-180]. This work has attracted considerable attention, has been extended to degree sequences under weaker conditions and has been applied to random models of a wide range of complex networks such as the World Wide Web or biological systems operating at a sub-molecular level. Nevertheless, the technical conditions on D restrict the applicability of the result to sequences where the vertices of high degree play no important role. This is a major problem since it is observed in many real-world networks, such as scale-free networks, that vertices of high degree (the so-called hubs) are present and play a crucial role. In this paper we characterize when a uniformly random graph with a fixed degree sequence has a giant component. Our main result holds for every degree sequence of length n provided that a minor technical condition is satisfied. The typical structure of G(D) when D does not satisfy this condition is relatively simple and easy to understand. Our result gives a unified criterion that implies all the known results on the existence of a giant component in G(D), including both the generalizations of the Molloy-Reed result and results on more restrictive models. Moreover, it turns out that the heuristic argument used in all the previous works on the topic, does not extend to general degree sequences.

The study of typical properties of random graphs is of particular importance for the theoretical analysis of complex networks. In this field, many models of randomness (such as Erdős-Rényi or random planar graphs, preferential attachment models) have been successfully analysed thanks to the fact that their underlying structure enables one to perform explicit computations of some observables. Another approach, pioneered by McDiarmid, Steger and Welsh (2005) is to consider graphs taken uniformly from an abstract graph class, assuming only some global property of the class but without fully specifying it. Despite the fact that exact computations are no longer possible, results obtained in this setup are arguably very robust, since they apply universally for many different models of random graphs. The foundational and most studied problem in this topic is a conjecture of these authors on bridge-addable classes that we prove in this paper. A class of graphs is bridge-addable if any graph obtained by adding an edge between two connected components of a graph in the class, is also in the class. Examples of bridge-addable classes include forests, planar graphs, graphs with bounded tree-width, or graphs excluding any 2-connected minor. We prove that a random graph from a bridge-addable class is connected with probability at least e–1/2 + o(1), when its number of vertices tends to infinity. This lower bound is tight since it is reached for forests. The best previously known constants where e–1, e–0.7983 and e–2/3 proved respectively by McDiarmid, Steger and Welsh, by Balister, Bollobás and Gerke, and by Norin.

We study two extremal problems about subgraphs excluding a family $\mathcal{F}$ of graphs: (i) Among all graphs with $m$ edges, what is the smallest size $f(m,\mathcal{F})$ of a largest $\mathcal{F}$-free subgraph? (ii) Among all graphs with minimum degree $\delta$ and maximum degree $\Delta$, what is the smallest minimum degree $h(\delta,\Delta,\mathcal{F})$ of a spanning $\mathcal{F}$-free subgraph with largest minimum degree? These questions are easy to answer for families not containing any bipartite graph. We study the case where $\mathcal{F}$ is composed of all even cycles of length at most 2r, $r\geq 2$. In this case, we give bounds on $f(m,\mathcal{F})$ and $h(\delta,\Delta,\mathcal{F})$ that are essentially asymptotically tight up to a logarithmic factor. In particular for every graph $G$, we show the existence of subgraphs with arbitrarily high girth and with either many edges or large minimum degree. These subgraphs are created using probabilistic embeddings of a graph into extremal graphs.

Finding decompositions of a graph into a family of clusters is crucial to understanding its underlying structure. While most existing approaches focus on partitioning the nodes, real-world datasets suggest the presence of overlapping communities. We present OCA, a novel algorithm to detect overlapped communities in large data graphs. It outperforms previous proposals in terms of execution time, and efficiently handles large graphs containing more than 108nodes and edges.