Using representation theory, we obtain a necessary and sufficient condition for a discrete-time Markov chain on a finite state space $E$ to be representable as $$\Psi_n \Psi_{n-1} \cdots \Psi_1 z,\quad n \geq 0,$$ for any $z \in E$, where the $\Psi_i$ are independent, identically distributed random permutations taking values in some given transitive group of permutations on $E$. The condition is particularly simple when the group is 2-transitive on $E$. We also work out the explicit form of our condition for the dihedral group of symmetries of a regular polygon.

Vapnik and Chervonenkis proposed in [7] a combinatorial notion of dimension that reflects the ‘combinatorial complexity’ of families of sets. In the three decades that have passed since that paper, this notion – the Vapnik–Chervonenkis dimension (VC-dimension) – has been discovered to be of primal importance in quite a wide variety of topics in both pure mathematics and theoretical computer science.

In this paper we turn our attention to classes with infinite VC-dimension, a realm thrown into one big bag by the usual VC-dimension analysis. We identify three levels of combinatorial complexity of classes with infinite VC-dimension. We show that these levels fall under the set-theoretic definition of σ-ideals (in particular, each of them is closed under countable unions), and that they are all distinct. The first of these levels (i.e., the family of ‘small’ infinite-dimensional classes) coincides with the family of classes which are non-uniformly PAC-learnable.

Maybe the most surprising contribution of this work is the discovery of an intimate relation between the VC-dimension of a class of subsets of the natural numbers and the Lebesgue measure of the set of reals defined when these subsets are viewed as binary representations of real numbers.

As a by-product, our investigation of the VC-dimension-induced ideals over the reals yields a new proper extension of the Lebesgue measure. Another offshoot of this work is a simple result in probability theory, showing that, given any sequence of pairwise independent events, any random event is eventually independent of the members of the sequence.

We prove a generalmulti-dimensional central limit theorem for the expected number of vertices of a given degree in the family of planar maps whose vertex degrees are restricted to an arbitrary (finite or infinite) set of positive integers D. Our results rely on a classical bijection with mobiles (objects exhibiting a tree structure), combined with refined analytic tools to deal with the systems of equations on infinite variables that arise. We also discuss possible extensions to maps of higher genus and to weighted maps.

We find an asymptotic enumeration formula for the number of simple $r$ -uniform hypergraphs with a given degree sequence, when the number of edges is sufficiently large. The formula is given in terms of the solution of a system of equations. We give sufficient conditions on the degree sequence which guarantee existence of a solution to this system. Furthermore, we solve the system and give an explicit asymptotic formula when the degree sequence is close to regular. This allows us to establish several properties of the degree sequence of a random $r$ -uniform hypergraph with a given number of edges. More specifically, we compare the degree sequence of a random $r$ -uniform hypergraph with a given number edges to certain models involving sequences of binomial or hypergeometric random variables conditioned on their sum.

We prove that, for any $t \ge 3$, there exists a constant c = c(t) > 0 such that any d-regular n-vertex graph with the second largest eigenvalue in absolute value λ satisfying $\lambda \le c{d^{t - 1}}/{n^{t - 2}}$ contains vertex-disjoint copies of kt covering all but at most ${n^{1 - 1/(8{t^4})}}$ vertices. This provides further support for the conjecture of Krivelevich, Sudakov and Szábo (Combinatorica24 (2004), pp. 403–426) that (n, d, λ)-graphs with n ∈ 3ℕ and $\lambda \le c{d^2}/n$ for a suitably small absolute constant c > 0 contain triangle-factors. Our arguments combine tools from linear programming with probabilistic techniques, and apply them in a certain weighted setting. We expect this method will be applicable to other problems in the field.

A cylinder graph is the graph Cartesian product of a path and a cycle. In this paper we investigate the length of a minimal spanning tree of a cylinder graph whose edges are assigned random lengths according to independent and uniformly distributed random variables. Our work was inspired by a formula of J. Michael Steele which shows that the expected length of a minimal spanning tree of a connected graph can be calculated through the Tutte polynomial of the graph. First, using transfer matrices, we show how to calculate the Tutte polynomials of cylinder graphs. Second, using Steele's formula, we tabulate the expected lengths of the minimal spanning trees for some cylinder graphs. Third, for a fixed cycle length, we show that the ratio of the expected length of a minimal spanning tree of a cylinder graph to the length of the cylinder graph converges to a constant; this constant is described in terms of the Perron–Frobenius eigenvalue of the accompanying transfer matrix. Finally, we show that the length of a minimal spanning tree of a cylinder graph satisfies a strong law of large numbers.

We show that, for a certain class of probabilistic models, the number of internal nodes $S_n$ of a trie built from $n$ independent and identically distributed keys is concentrated around its mean, in the sense that $\Var S_n=\Oh(\EE S_n)$. Keys are sequences of symbols which may be taken from varying alphabets, and the choice of the alphabet from which the $k$th symbol is taken, as well as its distribution, may depend on all the preceding symbols. In the construction of the trie we also allow for bucket sizes greater than 1. The property that characterizes our models is the following: there is a constant $C$ such that for any word $v$ that may occur as a prefix of a key the size $S^v_n$ of a trie built from the suffixes of $n$ independent keys conditioned to have the common prefix $v$ has the property $\EE S^v_n\leq Cn$. This class of models contains memoryless and Markovian source models as well as the probabilistic dynamical source models that were recently introduced and thoroughly developed by Vallée [Algorithmica29 (2001) 262–306], in particular the continued fraction source. Furthermore we study the external path length $L_n$, which obeys $\EE L_n=\Oh(n\ln n)$ and $\Var L_n=\Oh(n\ln^2 n)$.

We prove that triangular configurations are plentiful in large subsets of Cartesian squares of finite quasirandom groups from classes having the quasirandom ultraproduct property, for example the class of finite simple groups. This is deduced from a strong double recurrence theorem for two commuting measure-preserving actions of a minimally almost periodic (not necessarily amenable or locally compact) group on a (not necessarily separable) probability space.

A stable set $I$ of a graph $G$ is called $k$-extendable, $k \,{\ge}\, 1$, if there exists a stable set $X \,{\subseteq}\,V(G) {\setminus} I$ such that $|X| \,{\le}\, k$ and $|N(X) \,{\cap}\, I| \,{<}\, |X|$. A graph $G$ is called $k$-extendable if every stable set in $G$, which is not maximum, is $k$-extendable. Let us denote by ${\rm E}(k)$ the class of all $k$-extendable graphs.

We present a finite forbidden induced subgraph characterization of the maximal hereditary subclass ${\rm PE}(k)$ in ${\rm E}(k)$ for every $k \,{\ge}\,1$.

Thus, we define a hierarchy ${\rm PE}(1) \,{\subset}\, {\rm PE}(2) \,{\subset}\,{\cdots}\,{ \subset}\, {\rm PE}(k) \,{\subset}\,{ \cdots}\,$ of hereditary classes of graphs, in each of which a maximum stable set can be found in polynomial time. The hierarchy covers all graphs, and all its classes can be recognized in polynomial time.

In this paper, we study percolation on finite Cayley graphs. A conjecture of Benjamini says that the critical percolation $p_c$ of any vertex-transitive graph satisfying a certain diameter condition can be bounded away from one. We prove Benjamini's conjecture for some special classes of Cayley graphs. We also establish a reduction theorem, which allows us to build Cayley graphs for large groups without increasing $p_c$.

In this paper we will give all Ramsey numbers r(K3, G) for connected graphs G of order 7 and 8. For smaller orders and non-connected graphs of order up to 8, the number of graphs with given Ramsey number is listed for all possible values.

A $(p,q)$ -colouring of a graph $G$ is an edge-colouring of $G$ which assigns at least $q$ colours to each $p$ -clique. The problem of determining the minimum number of colours, $f(n,p,q)$ , needed to give a $(p,q)$ -colouring of the complete graph $K_n$ is a natural generalization of the well-known problem of identifying the diagonal Ramsey numbers $r_k(p)$ . The best-known general upper bound on $f(n,p,q)$ was given by Erdős and Gyárfás in 1997 using a probabilistic argument. Since then, improved bounds in the cases where $p=q$ have been obtained only for $p\in \{4,5\}$ , each of which was proved by giving a deterministic construction which combined a $(p,p-1)$ -colouring using few colours with an algebraic colouring.

In this paper, we provide a framework for proving new upper bounds on $f(n,p,p)$ in the style of these earlier constructions. We characterize all colourings of $p$ -cliques with $p-1$ colours which can appear in our modified version of the $(p,p-1)$ -colouring of Conlon, Fox, Lee, and Sudakov. This allows us to greatly reduce the amount of case-checking required in identifying $(p,p)$ -colourings, which would otherwise make this problem intractable for large values of $p$ . In addition, we generalize our algebraic colouring from the $p=5$ setting and use this to give improved upper bounds on $f(n,6,6)$ and $f(n,8,8)$ .

We give some sufficient conditions for an (S, U)-outline T-factorization of Kn to be an (S, U)-amalgamated T-factorization of Kn. We then apply these to give various necessary and sufficient conditions for edge coloured graphs G to have recoverable embeddings in T-factorized Kn's.

Two natural classes of polymatroids can be associated with hypergraphs: the so-called Boolean and hypergraphic polymatroids. Boolean polymatroids carry virtually all the structure of hypergraphs; hypergraphic polymatroids generalize graphic matroids. This paper considers algorithmic problems associated with recognizing members of these classes. Let k be a fixed positive integer and assume that the k-polymatroid ρ is presented via a rank oracle. We present an algorithm that determines in polynomial time whether ρ is Boolean, and if it is, finds the hypergraph. We also give an algorithm that decides in polynomial time whether ρ is the hypergraphic polymatroid associated with a given hypergraph. Other structure-theoretic results are also given.

Dowling lattices are a class of geometric lattices, based on groups, which have been shown to share many properties with projective geometries. In this paper we show that the automorphisms of Dowling lattices are analogs of the automorphisms of projective geometries. We also treat similar results for several related geometric lattices.

Two graphs G1 and G2 on n vertices are said to pack if there exist injective mappings of their vertex sets into [n] such that the images of their edge sets are disjoint. A longstanding conjecture due to Bollobás and Eldridge and, independently, Catlin, asserts that if (Δ(G1) + 1)(Δ(G2) + 1) ⩽ n + 1, then G1 and G2 pack. We consider the validity of this assertion under the additional assumption that G1 or G2 has bounded codegree. In particular, we prove for all t ⩾ 2 that if G1 contains no copy of the complete bipartite graph K2,t and Δ(G1) > 17t · Δ(G2), then (Δ(G1) + 1)(Δ(G2) + 1) ⩽ n + 1 implies that G1 and G2 pack. We also provide a mild improvement if moreover G2 contains no copy of the complete tripartite graph K1,1,s, s ⩾ 1.

Many problems in combinatorial linear algebra require upper bounds on the number of solutions to an underdetermined system of linear equations $Ax = b$, where the coordinates of the vector x are restricted to take values in some small subset (e.g. $\{\pm 1\}$) of the underlying field. The classical ways of bounding this quantity are to use either a rank bound observation due to Odlyzko or a vector anti-concentration inequality due to Halász. The former gives a stronger conclusion except when the number of equations is significantly smaller than the number of variables; even in such situations, the hypotheses of Halász’s inequality are quite hard to verify in practice. In this paper, using a novel approach to the anti-concentration problem for vector sums, we obtain new Halász-type inequalities that beat the Odlyzko bound even in settings where the number of equations is comparable to the number of variables. In addition to being stronger, our inequalities have hypotheses that are considerably easier to verify. We present two applications of our inequalities to combinatorial (random) matrix theory: (i) we obtain the first non-trivial upper bound on the number of $n\times n$ Hadamard matrices and (ii) we improve a recent bound of Deneanu and Vu on the probability of normality of a random $\{\pm 1\}$ matrix.

We prove that the rescaled costs of partial match queries in a random two-dimensional quadtree converge almost surely towards a random limit which is identified as the terminal value of a martingale. Our approach shares many similarities with the theory of self-similar fragmentations.

We explore the ‘Hausdorff dimension at infinity’ for self-affine carpets defined on the square lattice. This notion of dimension (due to Barlow and Taylor), which is the correct notion from a probabilistic perspective, differs for these sets from more ‘naive’ indices of fractal dimension.

In 2003, Bohman, Frieze, and Martin initiated the study of randomly perturbed graphs and digraphs. For digraphs, they showed that for every $\alpha \gt 0$, there exists a constant $C$ such that for every $n$-vertex digraph of minimum semi-degree at least $\alpha n$, if one adds $Cn$ random edges then asymptotically almost surely the resulting digraph contains a consistently oriented Hamilton cycle. We generalize their result, showing that the hypothesis of this theorem actually asymptotically almost surely ensures the existence of every orientation of a cycle of every possible length, simultaneously. Moreover, we prove that we can relax the minimum semi-degree condition to a minimum total degree condition when considering orientations of a cycle that do not contain a large number of vertices of indegree $1$. Our proofs make use of a variant of an absorbing method of Montgomery.