An intersecting system of type (∃, ∀, k, n) is a collection [ ]={[Fscr ]1, ..., [Fscr ]m} of pairwise disjoint families of k-subsets of an n-element set satisfying the following condition. For every ordered pair [Fscr ]i and [Fscr ]j of distinct members of [ ] there exists an A∈[Fscr ]i that intersects every B∈[Fscr ]j. Let In (∃, ∀, k) denote the maximum possible cardinality of an intersecting system of type (∃, ∀, k, n). Ahlswede, Cai and Zhang conjectured that for every k≥1, there exists an n0(k) so that In (∃, ∀, k)=(n−1/k−1) for all n>n0(k). Here we show that this is true for k≤3, but false for all k≥8. We also prove some related results.

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.

It follows from known results that every regular tripartite hypergraph of positive degree, with n vertices in each class, has matching number at least n/2. This bound is best possible, and the extremal configuration is unique. Here we prove a stability version of this statement, establishing that every regular tripartite hypergraph with matching number at most (1 + ϵ)n/2 is close in structure to the extremal configuration, where ‘closeness’ is measured by an explicit function of ϵ.

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)$.

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.

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$.

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)$ .

Let r ⩾ 2 be a fixed constant and let $ {\cal H} $ be an r-uniform, D-regular hypergraph on N vertices. Assume further that D → ∞ as N → ∞ and that degrees of pairs of vertices in $ {\cal H} $ are at most L where L = D/( log N)ω(1). We consider the random greedy algorithm for forming a matching in $ {\cal H} $. We choose a matching at random by iteratively choosing edges uniformly at random to be in the matching and deleting all edges that share at least one vertex with a chosen edge before moving on to the next choice. This process terminates when there are no edges remaining in the graph. We show that with high probability the proportion of vertices of $ {\cal H} $ that are not saturated by the final matching is at most (L/D)(1/(2(r−1)))+o(1). This point is a natural barrier in the analysis of the random greedy hypergraph matching process.

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 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.

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.

For an integer $b \geq 1$, the $b$-choice number of a graph $G$ is the minimum integer $k$ such that, for every assignment of a set $S(v)$ of at least $k$ colours to each vertex $v$ of $G$, there is a $b$-set colouring of $G$ that assigns to each vertex $v$ a $b$-set $B(v) \subseteq S(v) \; (|B(v)|=b)$ so that adjacent vertices receive disjoint $b$-sets. This is a generalization of the notions of choice number and chromatic number of a graph. Using probabilistic arguments, we show that, for some positive constant $c > 0$ (independent of $b$), the $b$-choice number of any graph $G$ on $n$ vertices is at most $c (b\chi) (\ln (n/\chi)+1)$ where $\chi = \chi(G)$ denotes the chromatic number of $G$. For any fixed $b$, this bound is tight up to a constant factor for each $n,\chi$. This generalizes and extends a result of Noga Alon [1]wherein a similar bound was obtained for 1-choice numbers of complete $\chi$-partite graphs with each part having size $n/\chi$. We also show that the proof arguments are constructive, leading to polynomial time algorithms for the list colouring problem on certain classes of graphs, provided each vertex is given a list of sufficiently large size.

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.

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.

In this note we study the emergence of Hamiltonian Berge cycles in random r-uniform hypergraphs. For $r\geq 3$ we prove an optimal stopping time result that if edges are sequentially added to an initially empty r-graph, then as soon as the minimum degree is at least 2, the hypergraph with high probability has such a cycle. In particular, this determines the threshold probability for Berge Hamiltonicity of the Erdős–Rényi random r-graph, and we also show that the 2-out random r-graph with high probability has such a cycle. We obtain similar results for weak Berge cycles as well, thus resolving a conjecture of Poole.

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.

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.

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.

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.