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.

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.

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.

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

Starting from a sequence regarded as a walk through some set of values, we consider the associated loop-erased walk as a sequence of directed edges, with an edge from i to j if the loop-erased walk makes a step from i to j. We introduce a colouring of these edges by painting edges with a fixed colour as long as the walk does not loop back on itself, then switching to a new colour whenever a loop is erased, with each new colour distinct from all previous colours. The pattern of colours along the edges of the loop-erased walk then displays stretches of consecutive steps of the walk left untouched by the loop-erasure process. Assuming that the underlying sequence generating the loop-erased walk is a sequence of independent random variables, each uniform on [N] := {1, 2, . . ., N}, we condition the walk to start at N and stop the walk when it first reaches the subset [k], for some 1 ≤ k ≤ N − 1. We relate the distribution of the random length of this loop-erased walk to the distribution of the length of the first loop of the walk, via Cayley's enumerations of trees, and via Wilson's algorithm. For fixed N and k, and i = 1, 2, . . ., let Bi denote the events that the loop-erased walk from N to [k] has i + 1 or more edges, and the ith and (i + 1)th of these edges are coloured differently. We show that, given that the loop-erased random walk has j edges for some 1 ≤ j ≤ N − k, the events Bi for 1 ≤ i ≤ j − 1 are independent, with the probability of Bi equal to 1/(k + i + 1). This determines the distribution of the sequence of random lengths of differently coloured segments of the loop-erased walk, and yields asymptotic descriptions of these random lengths as N → ∞.

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 mean weight of a cycle in an edge-weighted graph is the sum of the cycle's edge weights divided by the cycle's length. We study the minimum mean-weight cycle on the complete graph on n vertices, with random i.i.d. edge weights drawn from an exponential distribution with mean 1. We show that the probability of the min mean weight being at most c/n tends to a limiting function of c which is analytic for c ≤ 1/e, discontinuous at c = 1/e, and equal to 1 for c > 1/e. We further show that if the min mean weight is ≤ 1/(en), then the length of the relevant cycle is Θp(1) (i.e., it has a limiting probability distribution which does not scale with n), but that if the min mean weight is > 1/(en), then the relevant cycle almost always has mean weight (1 + o(1))/(en) and length at least (2/π2 − o (1)) log2n log log n.

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.

We prove and generalise a conjecture in [MPP4] about the asymptotics of $\frac{1}{\sqrt{n!}} f^{\lambda/\mu}$ , where $f^{\lambda/\mu}$ is the number of standard Young tableaux of skew shape $\lambda/\mu$ which have stable limit shape under the $1/\sqrt{n}$ scaling. The proof is based on the variational principle on the partition function of certain weighted lozenge tilings.

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

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

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.

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.

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

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.

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