We study several parameters of a random Bienaymé–Galton–Watson tree $T_n$ of size $n$ defined in terms of an offspring distribution $\xi$ with mean $1$ and nonzero finite variance $\sigma ^2$ . Let $f(s)=\mathbb{E}\{s^\xi \}$ be the generating function of the random variable $\xi$ . We show that the independence number is in probability asymptotic to $qn$ , where $q$ is the unique solution to $q = f(1-q)$ . One of the many algorithms for finding the largest independent set of nodes uses a notion of repeated peeling away of all leaves and their parents. The number of rounds of peeling is shown to be in probability asymptotic to $\log n/\log (1/f'(1-q))$ . Finally, we study a related parameter which we call the leaf-height. Also sometimes called the protection number, this is the maximal shortest path length between any node and a leaf in its subtree. If $p_1 = \mathbb{P}\{\xi =1\}\gt 0$ , then we show that the maximum leaf-height over all nodes in $T_n$ is in probability asymptotic to $\log n/\log (1/p_1)$ . If $p_1 = 0$ and $\kappa$ is the first integer $i\gt 1$ with $\mathbb{P}\{\xi =i\}\gt 0$ , then the leaf-height is in probability asymptotic to $\log _\kappa \log n$ .

A tight upper bound on the number of elements in a connected matroid with fixed rank and largest cocircuit size is given. This upper bound is used to show that a connected matroid with at least thirteen elements contains either a circuit or a cocircuit with at least six elements. In the language of matroid Ramsey numbers, n(6, 6) = 13: this is the largest currently known matroid Ramsey number.

In this paper we consider a bipartite version of Schütte's well-known tournament problem. A bipartite tournament $T=(A,B,E)$ with teams $A$ and $B$, and set of arcs $E$, has the property $S_{k,l}$ if for any subsets $K\subseteq A$ and $L\subseteq B$, with $|K| =k$ and $| L | =l$, there exist conquerors of $K$ and $L$ in opposite teams. The task is to estimate, for fixed $k$ and $l$, the minimum number $f(k,l)=| A | + | B | $ of players in a tournament satisfying property $S_{k,l}$. We achieve this goal by reformulating the problem in terms of intersecting set families and applying probabilistic as well as constructive methods. Intriguing connections with some famous problems of this area have emerged in this way, leading to new open questions.

We study computational aspects of repulsive Gibbs point processes, which are probabilistic models of interacting particles in a finite-volume region of space. We introduce an approach for reducing a Gibbs point process to the hard-core model, a well-studied discrete spin system. Given an instance of such a point process, our reduction generates a random graph drawn from a natural geometric model. We show that the partition function of a hard-core model on graphs generated by the geometric model concentrates around the partition function of the Gibbs point process. Our reduction allows us to use a broad range of algorithms developed for the hard-core model to sample from the Gibbs point process and approximate its partition function. This is, to the extent of our knowledge, the first approach that deals with pair potentials of unbounded range.

Given a graphon $W$ and a finite simple graph $H$ , with vertex set $V(H)$ , denote by $X_n(H, W)$ the number of copies of $H$ in a $W$ -random graph on $n$ vertices. The asymptotic distribution of $X_n(H, W)$ was recently obtained by Hladký, Pelekis, and Šileikis [17] in the case where $H$ is a clique. In this paper, we extend this result to any fixed graph $H$ . Towards this we introduce a notion of $H$ -regularity of graphons and show that if the graphon $W$ is not $H$ -regular, then $X_n(H, W)$ has Gaussian fluctuations with scaling $n^{|V(H)|-\frac{1}{2}}$ . On the other hand, if $W$ is $H$ -regular, then the fluctuations are of order $n^{|V(H)|-1}$ and the limiting distribution of $X_n(H, W)$ can have both Gaussian and non-Gaussian components, where the non-Gaussian component is a (possibly) infinite weighted sum of centred chi-squared random variables with the weights determined by the spectral properties of a graphon derived from $W$ . Our proofs use the asymptotic theory of generalised $U$ -statistics developed by Janson and Nowicki [22]. We also investigate the structure of $H$ -regular graphons for which either the Gaussian or the non-Gaussian component of the limiting distribution (but not both) is degenerate. Interestingly, there are also $H$ -regular graphons $W$ for which both the Gaussian or the non-Gaussian components are degenerate, that is, $X_n(H, W)$ has a degenerate limit even under the scaling $n^{|V(H)|-1}$ . We give an example of this degeneracy with $H=K_{1, 3}$ (the 3-star) and also establish non-degeneracy in a few examples. This naturally leads to interesting open questions on higher order degeneracies.