RandNet Workshop on 
Random Discrete Structures

Many bijections between maps and decorated trees have been developed in the last 20 years. In 2010, Jérémie Bouttier and Emmanuel Guitter introduced a new bijective paradigm for maps, called the « slice decomposition », which consists in cutting maps along some geodesic paths to produce some sort of canonical building blocks. This decomposition enables to obtain recursive decompositions, similar to the ones already available for decorated trees, but it also leads to new constructions and decompositions.
In my talk, I will present the extension of the slice decomposition to hypermaps (i.e maps in which faces can be properly coloured in two colours). A key feature of hypermaps is that the geodesics along which we cut are directed, following the canonical orientation of edges imposed by the coloring. This orientation requires us to introduce an adapted notion of slices. Using these slices as fundamental building blocks, we obtain new bijective decompositions of several families of hypermaps, thus giving proofs for enumerative formulas obtained in the physics literature.
This is a joint work with Jérémie Bouttier.

We study the asymptotic rank of adjacency matrices of a large class of edge-weighted configuration models. Here, the weight of a (multi-)edge can be any fixed non-zero element from an arbitrary field, as long as it is independent of the (multi-)graph. Our main result demonstrates that the asymptotic behavior of the normalized rank of the adjacency matrix neither depends on the fixed edge-weights, nor on which field they are chosen from. The underlying approach rests on a novel adaptation of the component exploration method developed by Janson and Luczak, which enables the application of combinatorial techniques that were developed in the study of random constraint satisfaction problems. The talk is based on joint work with Remco van der Hofstad and Haodong Zhu.

Motivated by Ryser’s conjecture, which bounds the minimum size of a vertex cover in terms of the matching number in $r$-partite hypergraphs, Lovász proposed in 1975 the stronger statement that one can always find $r-1$ vertices whose deletion reduces the matching number. Recently, Clow, Haxell, and Mohar disproved this by exhibiting a counterexample for $r=3$. In this work we present a significantly smaller counterexample and construct an infinite family of such counterexamples for $r=3$. Furthermore, we provide the first counterexamples for $r=4$. This talk is based on joint work with Aida Abiad, Frederik Garbe, and Christoph Spiegel.

We investigate the Threshold Group Testing problem in a probabilistic, noiseless, and non-adaptive setting, where the aim is to identify a known number of defective items using as few tests as possible. In this framework, each test returns a positive result if the number of defectives in the tested group meets or exceeds a specified threshold, and a negative result otherwise. This generalises Classical Group Testing, which corresponds to the special case where the threshold is one.
Our main contribution is the derivation of tight information-theoretic upper and lower bounds on the minimum number of tests required, expressed in terms of population size, number of defectives, and the threshold value. These bounds coincide in most regimes, offering a near-complete characterisation of the testing complexity. However, part of the lower bound is derived under the assumption of a fixed test design.
Notably, the results reveal regimes where Threshold Group Testing can surprisingly require fewer tests than Classical Group Testing, highlighting the nuanced effect of the threshold on testing complexity. In contrast, when the number of defectives is a constant fraction of the population, threshold testing does not reduce the testing burden, requiring at least as many tests as items.

The quantitative version of Ramsey's theorem, due to Erdős and Szekeres, tells us that every graph on $n$ vertices without a clique of size $t$ contains an independent set of size at least $n^{1-c_t}$. But what subgraphs do we need to exclude to ensure that a graph on $n$ vertices has an independent set of size $n^{1-o(1)}$? Clearly, we must exclude a clique, and considering random graphs shows that we must also exclude a forest. We show that this is enough. We also discuss a fractional version of the Gyárfás-Sumner Conjecture, and extensions to the multicolour setting. Joint work with Tung Nguyen and Paul Seymour.

We will consider a random geometric graph process where random points are embedded consecutively in the $d$-dimensional unit torus and every two points at distance at most $r$ form an edge. First, we will explore analogues of well-known hitting time results for connectivity and Hamiltonicity in the Erdős-Rényi graph process when $r$ approaches $0$.
The main focus of the talk will fall on a discussion of a geometric version of the power of choice where, at each step, an agent is shown two independent random points and is allowed to choose one of them. Related sharp threshold and hitting time results will be considered in an online and an offline version of the choice process. Joint work with Dawid Ignasiak.

In Bernoulli percolation on the square lattice, the proportion of vertices in the largest cluster in a restricted box converges to the probability that the origin lies in an infinite cluster as the box size tends to infinity. The probability that this proportion is smaller, decays stretched exponentially with exponent strictly smaller than one. The probability that the largest cluster is much larger than expected decays exponentially. Thus, the upper tail decays much faster than the lower tail.
This talk will explain why the discrepancy between the tails is reversed in spatial random graph models in which the degrees have heavy tails.
Based on joint work with Julia Komjathy and Dieter Mitsche

In this talk, we will discuss the non-hamiltonicity of various families of regular (labelled) planar graphs, when considering graphs uniformly at random, and will in particular derive bounds on the length of their largest cycle. On the way, we will put these questions into a historical perspective, dating back to the early days of graph theory and the four-colour problem, answer an old question attributed to Plummer, and discuss an open problem of Wormlad asking whether or not uniform random planar graphs admit long cycles, i.e. cycles whose length is linear in the number of vertices.
This is on-going work with Michael Drmota and Marc Noy.

Authors. François Durand, Élie de Panafieu, Guillem Perarnau (work in progress)
"Strategic voting" or manipulability by coalition, occurs when a group of voters can obtain an election outcome they prefer by not voting sincerely. Among the various existing voting systems, Instant-Runoff Voting (IRV) is reputed to be more resistant to strategic voting than others. IRV is used for several presidential and parliamentary elections around the world (Australia, India, Ireland, Papua New Guinea, Sri Lanka). We study the probability that strategic voting is ineffective under IRV when voters randomly draw their preferences among the candidates. This work combines social choice theory, probability, and analytic combinatorics.

We count unlabelled chordal graphs with tree-width at most $t$, which are the graphs that can be obtained from an initial vertex by iteratively adding a new vertex connected to all vertices of an existing clique of size at most $t$. In order to do so, we extend Pólya theory and the method of cycle pointing to take into account the cycles of cliques in the automorphisms of graphs.

TBA.

Address: Waaggasse 5, 1040 Wien.

We consider a uniform spanning tree in a planar domain $D$, and for any fixed $n\ge 2$, we condition the tree on the "$n$-arm event" (the tree has $n$ disjoint branches from the origin to the boundary). What can be said about the geometry of these branches? We show surprising connections to random matrix theory: on the unit disc, for every fixed $n\ge 2$, the $n$ hitting positions of the branches on the unit circle coincide exactly (in the scaling limit of fine mesh size) with the eigenvalues of a random matrix of size n drawn from the Circular Orthogonal Ensemble (COE, or CβE with $\beta = 1$). Furthermore, the $n$ branches converge to Loewner evolution driven by the circular Dyson Brownian motion with parameter $\beta = 4$; this verifies a nonrigorous prediction of Cardy in this setting.
We use this and an exact combinatorial identity (based on Fomin's determinantal formula) to discuss the winding of the branches around the origin, correcting a statement of Kenyon in the process.
This is joint work with Marcin Lis, Minchang Liu and Eveliina Peltola.

We analyse Jordan, rumour, closeness, betweenness and degree centrality in random recursive trees. We consider the rank of the root, after ordering the vertices according to these measures, and the label of the most central vertex, the centroid. We focus on persistence, that is whether there is a random but finite time after which the rank of the root or the index of the centroid does not change, almost surely. Moreover, we also study tightness and the expected value of these random variables, for each centrality measure. Additionally, we consider the size of a confidence set that contains the root.

Tree walks are a class of closed walks on a complete graph constrained to span trees. They appear naturally in the computation of the moments of the eigenvalue distribution of random graphs $G(n,c/n)$ and their asymptotic enumeration is still an open problem. We discuss recent progress and current challenges.
Joint work with Élie de Panafieu.

In this talk, we will discuss two related probabilistic models of permutations and trees biased by their number of descents. Here, a descent in a permutation is a pair of consecutive elements where the first is greater than the second. Likewise, a descent in a rooted tree with labelled vertices is a pair of a parent vertex and a child such that the label of the parent is greater than the label of the child. For some nonnegative real number $q$, we consider the probability measures on permutations and on rooted labelled trees of a given size where each permutation or tree is chosen with a probability proportional to $q^{\text{number of descents}}$. In particular, we determine the asymptotic distribution of the first elements of permutations under this model. Different phases can be observed based on how $q$ depends on the number of elements $n$ in our permutations. Using the results on permutations, one can also characterize the local limit of descent-biased rooted labelled trees. This talk is based on joint work with Paul Thévenin.

Motivated by the study of networks involving encapsulation and decapsulation of protocols, we introduce nondeterministic walks, a new variant of one-dimensional discrete walks. The main difference to classical walks is that its nondeterministic steps consist of sets of steps from a predefined set such that all possible extensions are explored in parallel. In the first part of the talk, we discuss in detail the nondeterministic Dyck step set $\{\{-1\}, \{1\}, \{-1,1\}\}$ and Motzkin step set $\{\{-1\}, \{0\}, \{1\}, \{-1,0\}, \{-1,1\}, \{0,1\}, \{-1,0,1\}\}$, and show that several nondeterministic classes of lattice paths, such as nondeterministic bridges, excursions, and meanders are algebraic. The key concept is the generalization of the ending point of a walk to its reachable points, i.e., a set of ending points. In the scond part, we extend our results to general step sets: We show that nondeterministic bridges and several subclasses of nondeterministic meanders are always algebraic.
Our results are obtained using generating functions, analytic combinatorics, and additive combinatorics. This is joint work with Élie de Panafieu and Mohamed Lamine Lamali.

TBA.