A tournament T on a set V of n players is an orientation of the edges of the complete graph Kn on V; T will be called a random tournament if the directions of these edges are determined by a sequence {Yj[ratio ]j = 1, …, (n2)} of independent coin flips. If (y, x) is an edge in a (random) tournament, we say that y beats x. A set A ⊂ V, |A| = k, is said to be beaten if there exists a player y ∉ A such that y beats x for each x ∈ A. If such a y does not exist, we say that A is unbeaten. A (random) tournament on V is said to have property Sk if each k-element subset of V is beaten. In this paper, we use the Stein–Chen method to show that the probability distribution of the number W0 of unbeaten k-subsets of V can be well-approximated by that of a Poisson random variable with the same mean; an improved condition for the existence of tournaments with property Sk is derived as a corollary. A multivariate version of this result is proved next: with Wj representing the number of k-subsets that are beaten by precisely j external vertices, j = 0, 1, …, b, it is shown that the joint distribution of (W0, W1, …, Wb) can be approximated by a multidimensional Poisson vector with independent components, provided that b is not too large.

We prove a generalization of a theorem of Ganter concerning the embedding of partial Steiner systems into Steiner systems. As an application we discuss a further version of the problem of Rosenfeld on embedding graphs into strongly regular graphs.

We consider the problem of minimizing the number of edges that are contained in triangles, among n-vertex graphs with a given number of edges. For sufficiently large n, we prove an exact formula for this minimum, which partially resolves a conjecture of Füredi and Maleki.

Which patterns must a two-colouring of $K_n$ contain if each vertex has at least $\varepsilon n$ red and $\varepsilon n$ blue neighbours? We show that when $\varepsilon \gt 1/4$, $K_n$ must contain a complete subgraph on $\Omega (\log n)$ vertices where one of the colours forms a balanced complete bipartite graph.

When $\varepsilon \leq 1/4$, this statement is no longer true, as evidenced by the following colouring $\chi$ of $K_n$. Divide the vertex set into $4$ parts nearly equal in size as $V_1,V_2,V_3, V_4$, and let the blue colour class consist of the edges between $(V_1,V_2)$, $(V_2,V_3)$, $(V_3,V_4)$, and the edges contained inside $V_2$ and inside $V_3$. Surprisingly, we find that this obstruction is unique in the following sense. Any two-colouring of $K_n$ in which each vertex has at least $\varepsilon n$ red and $\varepsilon n$ blue neighbours (with $\varepsilon \gt 0$) contains a vertex set $S$ of order $\Omega _{\varepsilon }(\log n)$ on which one colour class forms a balanced complete bipartite graph, or which has the same colouring as $\chi$.

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.

We study relaxations of proper two-colourings, such that the order of the induced monochromatic components in one (or both) of the colour classes is bounded by a constant. A colouring of a graph G is called (C1, C2)-relaxed if every monochromatic component induced by vertices of the first (second) colour is of order at most C1 (C2, resp.). We prove that the decision problem ‘Is there a (1, C)-relaxed colouring of a given graph G of maximum degree 3?’ exhibits a hardness jump in the component order C. In other words, there exists an integer f(3) such that the decision problem is NP-hard for every 2 ≤ C < f(3), while every graph of maximum degree 3 is (1, f(3))-relaxed colourable. We also show f(3) ≤ 22 by way of a quasilinear time algorithm, which finds a (1, 22)-relaxed colouring of any graph of maximum degree 3. Both the bound on f(3) and the running time greatly improve earlier results. We also study the symmetric version, that is, when C1 = C2, of the relaxed colouring problem and make the first steps towards establishing a similar hardness jump.

It has been known for several years that the lattice of subspaces of a finite vector space has a decomposition into symmetric chains, i.e. a decomposition into disjoint chains that are symmetric with respect to the rank function of the lattice. This paper gives a positive answer to the long-standing open problem of providing an explicit construction of such a symmetric chain decomposition for a given lattice of subspaces of a finite (dimensional) vector space. The construction is done inductively using Schubert normal forms and results in a bracketing algorithm similar to the well-known algorithm for Boolean lattices.

We analyse the first-order asymptotic growth of

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

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

We consider the distribution of the value of the optimal k-assignment in an m × n matrix, where the entries are independent exponential random variables with arbitrary rates. We give closed formulas for both the Laplace transform of this random variable and for its expected value under the condition that there is a zero-cost (k − 1)-assignment.

We compute the large N limit of the partition function of the Euclidean Yang–Mills measure on orientable compact surfaces with genus $g\geqslant 1$ and non-orientable compact surfaces with genus $g\geqslant 2$ , with structure group the unitary group ${\mathrm U}(N)$ or special unitary group ${\mathrm{SU}}(N)$ . Our proofs are based on asymptotic representation theory: more specifically, we control the dimension and Casimir number of irreducible representations of ${\mathrm U}(N)$ and ${\mathrm{SU}}(N)$ when N tends to infinity. Our main technical tool, involving ‘almost flat’ Young diagram, makes rigorous the arguments used by Gross and Taylor (1993, Nuclear Phys. B400(1–3) 181–208) in the setting of QCD, and in some cases, we recover formulae given by Douglas (1995, Quantum Field Theory and String Theory (Cargèse, 1993), Vol. 328 of NATO Advanced Science Institutes Series B: Physics, Plenum, New York, pp. 119–135) and Rusakov (1993, Phys. Lett. B303(1) 95–98).

For an orientation H with n vertices, let T(H) denote the maximum possible number of labelled copies of H in an n-vertex tournament. It is easily seen that T(H) ≥ n!/2e(H), as the latter is the expected number of such copies in a random tournament. For n odd, let R(H) denote the maximum possible number of labelled copies of H in an n-vertex regular tournament. In fact, Adler, Alon and Ross proved that for H=Cn, the directed Hamilton cycle, T(Cn) ≥ (e−o(1))n!/2n, and it was observed by Alon that already R(Cn) ≥ (e−o(1))n!/2n. Similar results hold for the directed Hamilton path Pn. In other words, for the Hamilton path and cycle, the lower bound derived from the expectation argument can be improved by a constant factor. In this paper we significantly extend these results, and prove that they hold for a larger family of orientations H which includes all bounded-degree Eulerian orientations and all bounded-degree balanced orientations, as well as many others. One corollary of our method is that for any fixed k, every k-regular orientation H with n vertices satisfies T(H) ≥ (ek−o(1))n!/2e(H), and in fact, for n odd, R(H) ≥ (ek−o(1))n!/2e(H).

If φ is a scattered order type, and μ is a cardinal, then there exists a scattered order type ψ such that holds.

Given an undirected graph G, let us randomly orient G by tossing independent (possibly biased) coins, one for each edge of G. Writing a → b for the event that there exists a directed path from a vertex a to a vertex b in such a random orientation, we prove that for any three vertices s, a and b of G, we have ℙ(s → a ∩ s → b) ⩾ ℙ(s → a) ℙ(s → b).

The Tutte polynomial $T(G;x,y)$ of a graph evaluates to many interesting combinatorial quantities at various points in the $(x,y)$ plane, including the number of spanning trees, number of forests, number of acyclic orientations, the reliability polynomial, the partition function of the Q-state Potts model of a graph, and the Jones polynomial of an alternating link. The exact computation of $T(G;x,y)$ has been shown by Vertigan and Welsh [8] to be #P-hard at all but a few special points and on two hyperbolae, even in the restricted class of planar bipartite graphs. Attention has therefore been focused on approximation schemes. To date, positive results have been restricted to the upper half plane $y>1$, and most results have relied on a condition of sufficient denseness in the graph. In this paper we present an approach that yields a fully polynomial randomized approximation scheme for $T(G;x,y)$ for $x>1,\ y=1$, and for $T(G;2,0)$, in a class of sparse graphs. This is the first positive result that includes the important point $(2,0)$.

We prove two estimates for the expectation of the exponential of a complex function of a random permutation or subset. Using this theory, we find asymptotic expressions for the expected number of copies and induced copies of a given graph in a uniformly random graph with degree sequence(d1, …, dn) as n→ ∞. We also determine the expected number of spanning trees in this model. The range of degrees covered includes dj= λn + O(n1/2+ε) for some λ bounded away from 0 and 1.

For any c ≥ 2, a c-strong colouring of the hypergraph G is an assignment of colours to the vertices of G such that, for every edge e of G, the vertices of e are coloured by at least min{c,|e|} distinct colours. The hypergraph G is t-intersecting if every two edges of G have at least t vertices in common.

A natural variant of a question of Erdős and Lovász is: For fixed c ≥ 2 and t ≥ 1, what is the minimum number of colours that is sufficient to c-strong colour any t-intersecting hypergraphs? The purpose of this note is to describe some open problems related to this question.

Let ${\mathcal H}$ denote a collection of subsets of {1,2,. . .,n}, and assign independent random variables uniformly distributed over [0,1] to the n elements. Declare an element p-present if its corresponding value is at most p. In this paper, we quantify how much the observation of the r-present (r>p) set of elements affects the probability that the set of p-present elements is contained in ${\mathcal H}$. In the context of percolation, we find that this question is closely linked to the near-critical regime. As a consequence, we show that for every r>1/2, bond percolation on the subgraph of the square lattice given by the set of r-present edges is almost surely noise sensitive at criticality, thus generalizing a result due to Benjamini, Kalai and Schramm.

We observe returns of a simple random walk on a finite graph to a fixed node, and would like to infer properties of the graph, in particular properties of the spectrum of the transition matrix. This is not possible in general, but at least the set of eigenvalues can be recovered under fairly general conditions, e.g., when the graph has a node-transitive automorphism group. The main result is that by observing polynomially many returns, it is possible to estimate the spectral gap of such a graph up to a constant factor.

It is proven that a conjecture of Tao (2010) holds true for log-concave random variables on the integers: For every $n \geq 1$, if $X_1,\ldots,X_n$ are i.i.d. integer-valued, log-concave random variables, then

\begin{equation*} H(X_1+\cdots +X_{n+1}) \geq H(X_1+\cdots +X_{n}) + \frac {1}{2}\log {\Bigl (\frac {n+1}{n}\Bigr )} - o(1) \end{equation*}

$H(X_1) \to \infty$

$H(X_1)$

$U_1,\ldots,U_n$

$(0,1)$

\begin{equation*} h(X_1+\cdots +X_n + U_1+\cdots +U_n) = H(X_1+\cdots +X_n) + o(1), \end{equation*}

$H(X_1) \to \infty$

$h$

$o(1)$