A family of sets is said to be intersecting if any two sets in the family have non-empty intersection. In 1973, Erdős raised the problem of determining the maximum possible size of a union of r different intersecting families of k-element subsets of an n-element set, for each triple of integers (n, k, r). We make progress on this problem, proving that for any fixed integer r ⩾ 2 and for any $$k \le ({1 \over 2} - o(1))n$$, if X is an n-element set, and $${\cal F} = {\cal F}_1 \cup {\cal F}_2 \cup \cdots \cup {\cal F}_r $$, where each $$ {\cal F}_i $$ is an intersecting family of k-element subsets of X, then $$|{\cal F}| \le \left( {\matrix{n \cr k \cr } } \right) - \left( {\matrix{{n - r} \cr k \cr } } \right)$$, with equality only if $${\cal F} = \{ S \subset X:|S| = k,\;S \cap R \ne \emptyset \} $$ for some R ⊂ X with |R| = r. This is best possible up to the size of the o(1) term, and improves a 1987 result of Frankl and Füredi, who obtained the same conclusion under the stronger hypothesis $$k < (3 - \sqrt 5 )n/2$$, in the case r = 2. Our proof utilizes an isoperimetric, influence-based method recently developed by Keller and the authors.

We define the notion of smooth supercritical compositional structures. Two well-known examples are compositions and graphs of given genus. The ‘parts’ of a graph are the subgraphs that are maximal trees. We show that large part sizes have asymptotically geometric distributions. This leads to asymptotically independent Poisson variables for numbers of various large parts. In many cases this leads to asymptotic formulas for the probability of being gap-free and for the expected values of the largest part sizes, number of distinct parts and number of parts of multiplicity k.

It has been conjectured that, for any fixed \[{\text{r}} \geqslant 2\] and sufficiently large n, there is a monochromatic Hamiltonian Berge-cycle in every \[({\text{r}} - 1)\]-colouring of the edges of \[{\text{K}}_{\text{n}}^{\text{r}}\], the complete r-uniform hypergraph on n vertices. In this paper we prove this conjecture.

The name of Frank Ramsey is universally known amongst combinatorial mathematicians, but our casual mental picture of him can easily be an unimpressive one – the man who almost stumbled across the theorem that now bears his name, thereby anticipating Erdős and Szekeres, who of course gave the proper proof. Such an idea of Ramsey is entirely false: he was an absolutely brilliant man, who would certainly have become even more famous had he not died so young, and who would surely, it could easily be argued, have made yet further remarkable contributions to philosophy, economics and logic – and to combinatorics.

We study factor of i.i.d. processes on the d-regular tree for d ≥ 3. We show that if such a process is restricted to two distant connected subgraphs of the tree, then the two parts are basically uncorrelated. More precisely, any functions of the two parts have correlation at most $k(d-1) / (\sqrt{d-1})^k$, where k denotes the distance between the subgraphs. This result can be considered as a quantitative version of the fact that factor of i.i.d. processes have trivial 1-ended tails.

We show that the sampling formula induced from a Λ-coalescent process with multiple collisions is regenerative if and only if the measure Λ is either concentrated in 0 (Kingman case) or concentrated in 1 (star-shaped case). The Ewens sampling formula is the only sampling formula in this class which also belongs to Pitman's two-parameter family of sampling distributions.

We show that for every $\varepsilon\,{>}\,0$ there exists an $r_0\,{=}\,r_0(\varepsilon)$ such that, for all integers $r\,{\ge}\, r_0$, every graph of average degree at least $r+\varepsilon$ and girth at least 1000 contains a subdivision of $K_{r+2}$. Combined with a result of Mader this implies that, for every $\varepsilon\,{>}\,0$, there exists an $f(\varepsilon)$ such that, for all $r\,{\ge}\, 2$, every graph of average degree at least $r+\varepsilon$ and girth at least $f(\varepsilon)$ contains a subdivision of $K_{r+2}$. We also prove a more general result concerning subdivisions of arbitrary graphs.

Let A be a subset of an abelian group G. The subset sum of A is the set [sum ](A) = {[sum ]x∈T[mid ]T⊂A}. We prove the following result. Let S be a generating subset of an abelian group G such that 0∉S and 14[les ][mid ]S[mid ]. Then one of the following conditions holds.

(i) [mid ][sum ](S)[mid ][ges ]min([mid ]G[mid ] −3, 3[mid ]S[mid ]−3).

(ii) There is an x∈S such that S[setmn ]{x} generates a proper subgroup of order less than (3[mid ]S[mid ]−3)/2.

As a consequence, we obtain the following open case of an old conjecture of Diderrich. Let q be a composite odd number and let G be an abelian group of order 3q. Let S be a subset of G with cardinality q+1. Then every element of G is the sum of some subset of S.

Keller and Kindler recently established a quantitative version of the famous Benjamini–Kalai–Schramm theorem on the noise sensitivity of Boolean functions. Their result was extended to the continuous Gaussian setting by Keller, Mossel and Sen by means of a Central Limit Theorem argument. In this work we present a unified approach to these results, in both discrete and continuous settings. The proof relies on semigroup decompositions together with a suitable cut-off argument, allowing for the efficient use of the classical hypercontractivity tool behind these results. It extends to further models of interest such as families of log-concave measures and Cayley and Schreier graphs. In particular we obtain a quantitative version of the Benjamini–Kalai–Schramm theorem for the slices of the Boolean cube.

In r-neighbour bootstrap percolation on the vertex set of a graph G, a set A of initially infected vertices spreads by infecting, at each time step, all uninfected vertices with at least r previously infected neighbours. When the elements of A are chosen independently with some probability p, it is natural to study the critical probability pc(G, r) at which it becomes likely that all of V(G) will eventually become infected. Improving a result of Balogh, Bollobás and Morris, we give a bound on the second term in the expansion of the critical probability when G = [n]d and d ⩾ r ⩾ 2. We show that for all d ⩾ r ⩾ 2 there exists a constant cd,r > 0 such that if n is sufficiently large, then

$$p_c (\left[ n \right]^d ,{\rm{ }}r){\rm{\le }}\left( {\frac{{\lambda (d,r)}}{{\log _{(r - 1)} (n)}} - \frac{{c_{d,r} }}{{(\log _{(r - 1)} (n))^{3/2} }}} \right)^{d - r + 1} ,$$

where λ(d, r) is an exact constant and log(k) (n) denotes the k-times iterated natural logarithm of n.

A classical result of Sárközy states that, for any and any positive density subset E of , there exist elements x and y of E and such that . A version of this result for finite fields is derived from a recent theorem of P. Larick, a short proof of which is also given.

We give a fully polynomial-time randomized approximation scheme (FPRAS) for the number of bases in bicircular matroids. This is a natural class of matroids for which counting bases exactly is #P-hard and yet approximate counting can be done efficiently.

We derive an explicit formula for the difference χ(G;λ) − χ(G|X;λ)χ(Tx(G); λ)/(λ − 1), where χ(G;λ) is the characteristic polynomial of a simple matroid G, G|X is the restriction of G to a flat X in G, and Tx(G) is the complete principal truncation of G at the flat X. Two counting proofs of this formula are given. The first uses the critical problem and the second uses the broken-circuit complex. We also derive several inequalities involving Whitney numbers of the first kind and other numerical invariants.

Let ℝ+(ℋn),ℤ(ℋn),ℤ+(ℋn) be, respectively, the cone over ℝ, the lattice and the cone over ℤ, generated by all cuts of the complete graph on n nodes. For i ≥ 0, let has exactly i realizations in ℤ+(ℋn)}. We show that is infinite, except for the undecided case and empty and for i = 0, n ≤ 5 and for i ≥ 2, n ≤ 3. The set contains 0,1,∞ nonsimplicial points for n ≤ 4, n = 5, n ≥ 6, respectively. On the other hand, there exists a finite number t(n) such that t(n)d ∈ ℤ+(ℋn) for any ; we also estimate such scales for classes of points. We construct families of points of and ℤ+(ℋn), especially on a 0-lifting of a simplicial facet, and points d ∈ ℝ+(ℋn) with di, n = t for 1 ≤ i ≤ n − 1.

We show that the total chromatic number of a simple k-chromatic graph exceeds the chromatic index by at most 18k ⅓ log ½ 3k.

A family ℱ of k-element sets of an n-set is called t-intersecting if any two of its members overlap in at least t-elements. The Erdős-Ko-Rado Theorem gives a best possible upper bound for such a family if n ≥ n0(k, t). One of the most exciting open cases is when t = 2, n = 2k. The present paper gives an essential improvement on the upper bound for this case. The proofs use linear algebra and yield more general results.

An element e of a matroid M is called non-binary when M\e and M/e are both non-binary matroids. Oxley in [5] gave a characterization of the 3-connected non-binary matroids without non-binary elements. In this paper, we will construct all the 3-connected matroids having 1, 2 or 3 non-binary elements.

A linear forest is the union of a set of vertex disjoint paths. Akiyama, Exoo and Harary, and independently Hilton, have conjectured that the edges of every graph of maximum degree Δ can be covered by linear forests. We show that almost every graph can be covered with this number of linear forests.

We consider instances of the maximum independent set problem that are constructed according to the following semirandom model. Let $G_{n,p}$ be a random graph, and let $S$ be a set of $k$ vertices, chosen uniformly at random. Then, let $G_0$ be the graph obtained by deleting all edges connecting two vertices in $S$. Finally, an adversary may add edges to $G_0$ that do not connect two vertices in $S$, thereby producing the instance $G=G_{n,p,k}^*$. We present an algorithm that on input $G=G_{n,p,k}^*$ finds an independent set of size $\geq k$ within polynomial expected time, provided that $k\geq C(n/p)^{1/2}$ for a certain constant $C>0$. Moreover, we prove that in the case $k\leq (1-\varepsilon)\ln(n)/p$ this problem is hard.