We describe the C2k+1-free graphs on n vertices with maximum number of edges. The extremal graphs are unique for n ∉ {3k − 1, 3k, 4k − 2, 4k − 1}. The value of ex(n, C2k+1) can be read out from the works of Bondy [3], Woodall [14], and Bollobás [1], but here we give a new streamlined proof. The complete determination of the extremal graphs is also new.

We obtain that the bound for n0(C2k+1) is 4k in the classical theorem of Simonovits, from which the unique extremal graph is the bipartite Turán graph.

Let h > w > 0 be two fixed integers. Let H be a random hypergraph whose hyperedges are all of cardinality h. To w-orient a hyperedge, we assign exactly w of its vertices positive signs with respect to the hyperedge, and the rest negative signs. A (w,k)-orientation of H consists of a w-orientation of all hyperedges of H, such that each vertex receives at most k positive signs from its incident hyperedges. When k is large enough, we determine the threshold of the existence of a (w,k)-orientation of a random hypergraph. The (w,k)-orientation of hypergraphs is strongly related to a general version of the off-line load balancing problem. The graph case, when h = 2 and w = 1, was solved recently by Cain, Sanders and Wormald and independently by Fernholz and Ramachandran. This settled a conjecture of Karp and Saks.

Let $\mathcal{F}$ = {F1, F2,. . ., Fn} be a family of n sets on a ground set S, such as a family of balls in ℝd. For every finite measure μ on S, such that the sets of $\mathcal{F}$ are measurable, the classical inclusion–exclusion formula asserts that

$\[\mu(F_1\cup F_2\cup\cdots\cup F_n)=\sum_{I:\emptyset\ne I\subseteq[n]} (-1)^{|I|+1}\mu\biggl(\bigcap_{i\in I} F_i\biggr),\]$

$\mathcal{F}$

$\mathcal{F}$

$\mathcal{F}$

Let it(G) be the number of independent sets of size t in a graph G. Engbers and Galvin asked how large it(G) could be in graphs with minimum degree at least δ. They further conjectured that when n ⩾ 2δ and t ⩾ 3, it(G) is maximized by the complete bipartite graph Kδ,n−δ. This conjecture has recently drawn the attention of many researchers. In this short note, we prove this conjecture.

The shadow of a system of sets is all sets which can be obtained by taking a set in the original system, and removing a single element. The Kruskal-Katona theorem tells us the minimum possible size of the shadow of $\mathcal A$, if $\mathcal A$ consists of m r-element sets.

In this paper, we ask questions and make conjectures about the minimum possible size of a partial shadow for $\mathcal A$, which contains most sets in the shadow of $\mathcal A$. For example, if $\mathcal B$ is a family of sets containing all but one set in the shadow of each set of $\mathcal A$, how large must $\mathcal B$ be?

In this paper we provide two results. The first one consists of an infinitary version of the Furstenberg–Weiss theorem. More precisely we show that every subset A of a homogeneous tree T such that

$\frac{|A\cap T(n)|}{|T(n)|}\geqslant\delta,$

The second result is the following. For every sequence (mq)q∈ℕ of positive integers and for every real 0 < δ ⩽ 1, there exists a sequence (nq)q∈ℕ of positive integers such that for every D ⊆ ∪k ∏q=0k-1[nq] satisfying

$\frac{\big|D\cap \prod_{q=0}^{k-1} [n_q]\big|s}{\prod_{q=0}^{k-1}n_q}\geqslant\delta$

A graph on n vertices is ε-far from a property $\mathcal{P}$ if one has to add or delete from it at least εn2 edges to get a graph satisfying $\mathcal{P}$. A graph property $\mathcal{P}$ is strongly testable if for every fixed ε > 0 it is possible to distinguish, with one-sided error, between graphs satisfying $\mathcal{P}$ and ones that are ε-far from $\mathcal{P}$ by inspecting the induced subgraph on a random subset of at most f(ε) vertices. A property is easily testable if it is strongly testable and the function f is polynomial in 1/ε, otherwise it is hard. We consider the problem of characterizing the easily testable graph properties, which is wide open, and obtain several results in its study. One of our main results shows that testing perfectness is hard. The proof shows that testing perfectness is at least as hard as testing triangle-freeness, which is hard. On the other hand, we show that being a cograph, or equivalently, induced P3-freeness where P3 is a path with 3 edges, is easily testable. This settles one of the two exceptional graphs, the other being C4 (and its complement), left open in the characterization by the first author and Shapira of graphs H for which induced H-freeness is easily testable. Our techniques yield a few additional related results, but the problem of characterizing all easily testable graph properties, or even that of formulating a plausible conjectured characterization, remains open.

Given a graph G, let Q(G) denote the collection of all independent (edge-free) sets of vertices in G. We consider the problem of determining the size of a largest antichain in Q(G). When G is the edgeless graph, this problem is resolved by Sperner's theorem. In this paper, we focus on the case where G is the path of length n − 1, proving that the size of a maximal antichain is of the same order as the size of a largest layer of Q(G).

We establish a relation between two uniform models of random k-graphs (for constant k ⩾ 3) on n labelled vertices: ℍ(k)(n,m), the random k-graph with exactly m edges, and ℍ(k)(n,d), the random d-regular k-graph. By extending the switching technique of McKay and Wormald to k-graphs, we show that, for some range of d = d(n) and a constant c > 0, if m ~ cnd, then one can couple ℍ(k)(n,m) and ℍ(k)(n,d) so that the latter contains the former with probability tending to one as n → ∞. In view of known results on the existence of a loose Hamilton cycle in ℍ(k)(n,m), we conclude that ℍ(k)(n,d) contains a loose Hamilton cycle when d ≫ log n (or just d ⩾ C log n, if k = 3) and d = o(n1/2).

We consider the popular and well-studied push model, which is used to spread information in a given network with n vertices. Initially, some vertex owns a rumour and passes it to one of its neighbours, which is chosen randomly. In each of the succeeding rounds, every vertex that knows the rumour informs a random neighbour. It has been shown on various network topologies that this algorithm succeeds in spreading the rumour within O(log n) rounds. However, many studies are quite coarse and involve huge constants that do not allow for a direct comparison between different network topologies. In this paper, we analyse the push model on several important families of graphs, and obtain tight runtime estimates. We first show that, for any almost-regular graph on n vertices with small spectral expansion, rumour spreading completes after log2n + log n+o(log n) rounds with high probability. This is the first result that exhibits a general graph class for which rumour spreading is essentially as fast as on complete graphs. Moreover, for the random graph G(n,p) with p=c log n/n, where c > 1, we determine the runtime of rumour spreading to be log2n + γ (c)log n with high probability, where γ(c) = clog(c/(c−1)). In particular, this shows that the assumption of almost regularity in our first result is necessary. Finally, for a hypercube on n=2d vertices, the runtime is with high probability at least (1+β) ⋅ (log2n + log n), where β > 0. This reveals that the push model on hypercubes is slower than on complete graphs, and thus shows that the assumption of small spectral expansion in our first result is also necessary. In addition, our results combined with the upper bound of O(log n) for the hypercube (see [11]) imply that the push model is faster on hypercubes than on a random graph G(n, clog n/n), where c is sufficiently close to 1.

We show that for every sufficiently large n, the number of monotone subsequences of length four in a permutation on n points is at least

\begin{equation*} \binom{\lfloor{n/3}\rfloor}{4} + \binom{\lfloor{(n+1)/3}\rfloor}{4} + \binom{\lfloor{(n+2)/3}\rfloor}{4}. \end{equation*}

We analyse the first-order asymptotic growth of

\[ a_{n}=\int_{0}^{1}\prod_{j=1}^{n}4\sin^{2}(\pi jx)\, dx. \]

The size-Ramsey number $\^{r} $(F) of a graph F is the smallest integer m such that there exists a graph G on m edges with the property that every colouring of the edges of G with two colours yields a monochromatic copy of F. In 1983, Beck provided a beautiful argument that shows that $\^{r} $(Pn) is linear, solving a problem of Erdős. In this note, we provide another proof of this fact that actually gives a better bound, namely, $\^{r} $(Pn) < 137n for n sufficiently large.

We find new properties of the topological transition polynomial of embedded graphs, Q(G). We use these properties to explain the striking similarities between certain evaluations of Bollobás and Riordan's ribbon graph polynomial, R(G), and the topological Penrose polynomial, P(G). The general framework provided by Q(G) also leads to several other combinatorial interpretations these polynomials. In particular, we express P(G), R(G), and the Tutte polynomial, T(G), as sums of chromatic polynomials of graphs derived from G, show that these polynomials count k-valuations of medial graphs, show that R(G) counts edge 3-colourings, and reformulate the Four Colour Theorem in terms of R(G). We conclude with a reduction formula for the transition polynomial of the tensor product of two embedded graphs, showing that it leads to additional relations among these polynomials and to further combinatorial interpretations of P(G) and R(G).

Compound Poisson population models are particular conditional branching process models. A formula for the transition probabilities of the backward process for general compound Poisson models is verified. Symmetric compound Poisson models are defined in terms of a parameter θ ∈ (0, ∞) and a power series φ with positive radius r of convergence. It is shown that the asymptotic behaviour of symmetric compound Poisson models is mainly determined by the characteristic value θrφ′(r−). If θrφ′(r−)≥1, then the model is in the domain of attraction of the Kingman coalescent. If θrφ′(r−) < 1, then under mild regularity conditions a condensation phenomenon occurs which forces the model to be in the domain of attraction of a discrete-time Dirac coalescent. The proofs are partly based on the analytic saddle point method. They draw heavily from local limit theorems and from results of S. Janson on simply generated trees, conditioned Galton-Watson trees, random allocations and condensation. Several examples of compound Poisson models are provided and analysed.

The first open case of the Brown–Erdős–Sós conjecture is equivalent to the following: for every c > 0, there is a threshold n0 such that if a quasigroup has order n ⩾ n0, then for every subset S of triples of the form (a, b, ab) with |S| ⩾ cn2, there is a seven-element subset of the quasigroup which spans at least four triples of S. In this paper we prove the conjecture for finite groups.

A two-row array of integers

\[ \alpha_{n}= \begin{pmatrix}a_1 & a_2 & \cdots & a_n\\ b_1 & b_2 & \cdots & b_n \end{pmatrix} \]

${\cal D}$

${\cal D} = ({\cal D}_{n})_{n\in\NN}$

In this paper we study in complete generality the family of two-state, deterministic, monotone, local, homogeneous cellular automata in $\mathbb{Z}$d with random initial configurations. Formally, we are given a set $\mathcal{U}$ = {X1,. . . , Xm} of finite subsets of $\mathbb{Z}$d \ {0}, and an initial set A0 ⊂ $\mathbb{Z}$d of ‘infected’ sites, which we take to be random according to the product measure with density p. At time t ∈ $\mathbb{N}$, the set of infected sites At is the union of At-1 and the set of all x ∈ $\mathbb{Z}$d such that x + X ∈ At-1 for some X ∈ $\mathcal{U}$. Our model may alternatively be thought of as bootstrap percolation on $\mathbb{Z}$d with arbitrary update rules, and for this reason we call it $\mathcal{U}$-bootstrap percolation.

In two dimensions, we give a classification of $\mathcal{U}$-bootstrap percolation models into three classes – supercritical, critical and subcritical – and we prove results about the phase transitions of all models belonging to the first two of these classes. More precisely, we show that the critical probability for percolation on ($\mathbb{Z}$/n$\mathbb{Z}$)2 is (log n)−Θ(1) for all models in the critical class, and that it is n−Θ(1) for all models in the supercritical class.

The results in this paper are the first of any kind on bootstrap percolation considered in this level of generality, and in particular they are the first that make no assumptions of symmetry. It is the hope of the authors that this work will initiate a new, unified theory of bootstrap percolation on $\mathbb{Z}$d.

A univariate polynomial f over a field is decomposable if it is the composition f = g ○ h of two polynomials g and h whose degree is at least 2. We determine an approximation to the number of decomposables over a finite field. The tame case, where the field characteristic p does not divide the degree n of f, is reasonably well understood, and we obtain exponentially decreasing relative error bounds. The wild case, where p divides n, is more challenging and our error bounds are weaker.

We call a tree parameter additive if it can be determined recursively as the sum of the parameter values of all branches, plus a certain toll function. In this paper, we prove central limit theorems for very general toll functions, provided that they are bounded and small on average. Simply generated families of trees are considered as well as Pólya trees, recursive trees and binary search trees, and the results are illustrated by several examples of parameters for which we prove normal or log-normal limit laws.