We prove a joint local limit law for the distribution of the r largest components of decomposable logarithmic combinatorial structures, including assemblies, multisets and selections. Our method is entirely probabilistic, and requires only weak conditions that may readily be verified in practice.

In this paper we analyse the expected depth of random circuits of fixed fanin f. Such circuits are built a gate at a time, with the f inputs of each new gate being chosen randomly from among the previously added gates. The depth of the new gate is defined to be one more than the maximal depth of its input gates. We show that the expected depth of a random circuit with n gates is bounded from above by ef ln n and from below by 2.04 … f ln 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.

As a consequence of an early result of Pach we show that every maximal triangle-free graph is either homomorphic with a member of a specific infinite sequence of graphs or contains the Petersen graph minus one vertex as a subgraph. From this result and further structural observations we derive that, if a (not necessarily maximal) triangle-free graph of order n has minimum degree δ[ges ]n/3, then the graph is either homomorphic with a member of the indicated family or contains the Petersen graph with one edge contracted. As a corollary we get a recent result due to Chen, Jin and Koh. Finally, we show that every triangle-free graph with δ>n/3 is either homomorphic with C5 or contains the Möbius ladder. A major tool is the observation that every triangle-free graph with δ[ges ]n/3 has a unique maximal triangle-free supergraph.

We study the fluctuations, in the large deviations regime, of the longest increasing sub-sequence of a random i.i.d. sample on the unit square. In particular, our results yield the precise upper and lower exponential tails for the length of the longest increasing subsequence of a random permutation.

A family of k sets is called a Δ-system if any two sets have the same intersection. Denote by f(r, k) the least integer so that any r-uniform family of f(r, k) sets contains a Δ-system consisting of k sets. We prove that, for every fixed r, f(r, k) = kr + o(kr). Using a recent result of Molloy and Reed [5], a bound on the error term is provided for sufficiently large k.

The problem of probabilistic representability of semimatroids over a four-element set is solved. In this problem, one looks for all combinations of conditional independences within four random variables which can occur simultaneously. New properties of the stochastic conditional independences are deduced from conditional information inequalities. Examples of four-tuples of random variables are presented to show the probabilistic representability of three non-Ingleton semimatroids.

A set A is called universal sum-free if, for every finite 0–1 sequence χ = (e1, …, en), either

(i) there exist i, j, where 1[les ]j<i[les ]n, such that ei = ej = 1 and i − j∈A, or

(ii) there exists t∈N such that, for 1[les ]i[les ]n, we have t + i∈A if and only if ei = 1.

It is proved that the density of each universal sum-free set is zero, which settles a problem of Cameron.

Let B = [b1, …, bn] (with column vectors bi) be a basis of ℝn. Then L = [sum ]biℤ is a lattice in ℝn and A = B[top ]B is the Gram matrix of B. The reciprocal lattice L* of L has basis B* = (B−1)[top ] with Gram matrix A−1. For any nonsingular matrix A = (ai,j) with inverse A−1 = (a*i,j), let τ(A) = max1[les ]i[les ]n {[sum ]nj =1[mid ]ai,j ·a*j,j[mid ]}. Then τ(A), τ(A−1)[ges ]1 holds, with equality for an orthogonal basis. We will show that for any lattice L there is a basis with Gram matrix A such that τ(A), τ(A−1) = exp (O((ln n)2)). This generalizes a result in [8] and [20].

For any basis transformation A→Ā with Ā = T[top ]AT, T = (ti,j)∈SLn(ℤ), we will show [mid ]ti,j[mid ][les ]τ(A−1) ·τ(Ā). This implies that every integral matrix representation of a finite group is equivalent to a representation where the coefficients of the matrices representing group elements are bounded by exp (O((ln n)2)). This new bound is considerably smaller than the known (exponential) bounds for automorphisms of Minkowski-reduced lattice bases: see, for example, [6].

The quantities τ(A), τ(A−1) have the following geometric interpretation. Let V(L) [ratio ]= {x∈ℝn[mid ]∀λ∈L [ratio ][mid ]x[mid ][les ][mid ]x−λ[mid ]} be the Voronoi cell (also called the Dirichlet region) of the lattice L. For a basis B of L, we call C(B) = {[sum ]xibi, [mid ]xi[mid ][les ]1/2} the basis cell of B. Both cells define a lattice tiling of ℝn (see [6]); they coincide for an orthogonal basis. For a general basis B of L with Gram matrix A we will show V(L)[les ]τ(A−1)·C(B) and C(B)[les ]n·τ(A)·V(L).

A graph G is m-choosable with impropriety d, or simply (m, d)*-choosable, if for every list assignment L, where [mid ]L(v)[mid ][ges ]m for every v∈V(G), there exists an L-colouring of G such that each vertex of G has at most d neighbours coloured with the same colour as itself. We show that every planar graph is (3, 2)*-choosable and every outerplanar graph is (2, 2)*-choosable. We also propose some interesting problems about this colouring.