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 study the asymptotic behaviour of random integer partitions under a new probability law that we introduce, the Plancherel-Hurwitz measure. This distribution, which has a natural definition in terms of Young tableaux, is a deformation of the classical Plancherel measure. It appears naturally in the enumeration of Hurwitz maps, or equivalently transposition factorisations in symmetric groups. We study a regime in which the number of factors in the underlying factorisations grows linearly with the order of the group, and the corresponding maps are of high genus. We prove that the limiting behaviour exhibits a new, twofold, phenomenon: the first part becomes very large, while the rest of the partition has the standard Vershik-Kerov-Logan-Shepp limit shape. As a consequence, we obtain asymptotic estimates for unconnected Hurwitz numbers with linear Euler characteristic, which we use to study random Hurwitz maps in this regime. This result can also be interpreted as the return probability of the transposition random walk on the symmetric group after linearly many steps.

Given a large graph G and k agents on this graph, we consider the Voronoi tessellation induced by the graph distance. Each agent gets control of the portion of the graph that is closer to itself than to any other agent. We study the limit law of the vector Vor: = (V1/n, V2/n, …, Vk/n), whose i'th coordinate records the fraction of vertices of G controlled by the i'th agent, as n tends to infinity. We show that if G is a uniform random tree, and the agents are placed uniformly at random, the limit law of Vor is uniform on the (k – 1)-dimensional simplex. In particular, when k = 2, the two agents each get a uniform random fraction of the territory. In fact, we prove the result directly on the Brownian continuum random tree (CRT), and we also prove the same result for a “higher genus” analogue of the CRT that we call the continuum random unicellular map, indexed by a genus parameter g ≥ 0. As a key step of independent interest, we study the case when G is a random planar embedded graph with a finite number of faces. The main idea of the proof is to show that Vor has the same distribution as another partition of mass Int: = (I1/n, I2/n, …, Ik/n) where Ij is the contour length separating the i-th agent from the next one in clockwise order around the 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 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.

Tuza conjectured that for every graph $G$ the maximum size $\nu$ of a set of edge-disjoint triangles and minimum size $\tau$ of a set of edges meeting all triangles satisfy $\tau \leq 2\nu$. We consider an edge-weighted version of this conjecture, which amounts to packing and covering triangles in multigraphs. Several known results about the original problem are shown to be true in this context, and some are improved. In particular, we answer a question of Krivelevich, who proved that $\tau \leq 2\nu^*$ (where $\nu^*$ is the fractional version of $\nu$) and asked whether this is tight. We prove that $\tau \leq 2\nu^*-\frac{1}{\sqrt{6}}\sqrt{\nu^*}$ and show that this bound is essentially best possible.

The enumeration of maps and the study of uniform random maps have been classical topics of combinatorics and statistical physics ever since the seminal work of Tutte in the 1960s. Following the bijective approach initiated by Cori and Vauquelin in the '80s, we describe a bijection between rooted maps, or rooted bipartite quadrangulations, on a surface of genus g and some simpler objects that generalize plane trees. Thanks to a rerooting argument, our bijection allows us to compute the generating series of rooted maps on a surface of genus g with respect to the number of edges, and to recover the asymptotic numbers of such maps. Our construction allows us to keep track in a bipartite quadrangulation of the distances of all vertices to a random basepoint. This is an analogue for higher genus surfaces of the basic result on which were built the recent advances in the comprehension of the intrinsic geometry of large random planar maps, hopefully opening the way to the study of a model of continuum random surfaces of genus g.