Answering a question of Bang-Jensen and Thomassen [4], we prove that the minimum feedback arc set problem is NP-hard for tournaments.

A simple explicit construction is provided of a partition-valued fragmentation process whose distribution on partitions of [n] = 1,. . .,n at time θ ≥ 0 is governed by the Ewens sampling formula with parameter θ. These partition-valued processes are exchangeable and consistent, as n varies. They can be derived by uniform sampling from a corresponding mass fragmentation process defined by cutting a unit interval at the points of a Poisson process with intensity θx−1dx on/mathbbR+, arranged to beintensifying as θ increases.

We show that in the game of angel and devil, played on the planar integer lattice, the angel of power 4 can evade the devil. This answers a question of Berlekamp, Conway and Guy. Independent proofs that work for the angel of power 2 have been given by Kloster and by Máthé.

Improving upon work in [2], the precise value of the set reconstruction number is given for all cyclic groups of odd order.

Let G be a simple graph on n vertices. A conjecture of Bollobás and Eldridge [5] asserts that if then G contains any n vertex graph H with Δ(H) = k. We prove a strengthened version of this conjecture for bipartite, bounded degree H, for sufficiently large n. This is the first result on this conjecture for expander graphs of arbitrary (but bounded) degree. An important tool for the proof is a new version of the Blow-Up Lemma.

Consider the following communication problem, which leads to a new notion of edge colouring. The communication network is represented by a bipartite multigraph, where the nodes on one side are the transmitters and the nodes on the other side are the receivers. The edges correspond to messages, and every edge e is associated with an integer c(e), corresponding to the time it takes the message to reach its destination. A proper k-edge-colouring with delays is a function f from the edges to {0, 1, . . ., k − 1}, such that, for every two edges e1 and e2 with the same transmitter, f(e1) ≠ f(e2), and for every two edges e1 and e2 with the same receiver, f(e1) + c(e1) ≢ f(e2) + c(e2) (mod k). Ross, Bambos, Kumaran, Saniee and Widjaja [18] conjectured that there always exists a proper edge colouring with delays using k = Δ + o(Δ) colours, where Δ is the maximum degree of the graph. Haxell, Wilfong and Winkler [11] conjectured that a stronger result holds: k = Δ + 1 colours always suffice. We prove the weaker conjecture for simple bipartite graphs, using a probabilistic approach, and further show that the stronger conjectureholds for some multigraphs, applying algebraic tools.

We give a combinatorial proof of the result of Kahn, Kalai and Linial [16], which states that every balanced boolean function on the n-dimensional boolean cube has a variable with influence of at least . The methods of the proof are then used to recover additional isoperimetric results for the cube, with improved constants.

We also state some conjectures about optimal constants.

We solve Conway's Angel Problem by showing that the Angel of power 2 has a winning strategy.

An old observation of Conway is that we may suppose without loss of generality that the Angel never jumps to a square where he could have already landed at a previous time. We turn this observation around and prove that we may suppose without loss of generality that the Devil never eats a square where the Angel could have already jumped. Then we give a simple winning strategy for the Angel.

A simple first moment argument shows that in a randomly chosen $k$-SAT formula with $m$ clauses over $n$ boolean variables, the fraction of satisfiable clauses is $1-2^{-k}+o(1)$ as $m/n\rightarrow\infty$ almost surely. In this paper, we deal with the corresponding algorithmic strong refutation problem: given a random $k$-SAT formula, can we find a certificate that the fraction of satisfiable clauses is $1-2^{-k}+o(1)$ in polynomial time? We present heuristics based on spectral techniques that in the case $k=3$ and $m\geq\ln(n)^6n^{3/2}$, and in the case $k=4$ and $m\geq Cn^2$, find such certificates almost surely. In addition, we present heuristics for bounding the independence number (resp. the chromatic number) of random $k$-uniform hypergraphs from above (resp. from below) for $k=3,4$.

We study semirandom k-colourable graphs made up as follows. Partition the vertex set V = {1, . . ., n} randomly into k classes V1, . . ., Vk of equal size and include each Vi–Vj-edge with probability p independently (1 ≤ i < j ≤ k) to obtain a graph G0. Then, an adversary may add further Vi–Vj-edges (i≠j) to G0, thereby completing the semirandom graph G = G*n,p,k. We show that if np ≥ max{(1 + ϵ)klnn, C0k2} for a certain constant C0>0 and an arbitrarily small but constant ϵ>0, an optimal colouring of G*n,p,k can be found in polynomial time with high probability. Furthermore, if np ≥ C0max{klnn, k2}, a k-colouring of G*n,p,k can be computed in polynomial expected time. Moreover, an optimal colouring of G*n,p,k can be computed in expected polynomial time if k ≤ ln1/3n and np ≥ C0klnn. By contrast, it is NP-hard to k-colour G*n,p,k With high probability if .

We introduce the minor-closed, dual-closed class of multi-path matroids. We give a polynomial-time algorithm for computing the Tutte polynomial of a multi-path matroid, we describe their basis activities, and we prove some basic structural properties. Key elements of this work are two complementary perspectives we develop for these matroids: on the one hand, multi-path matroids are transversal matroids that have special types of presentations; on the other hand, the bases of multi-path matroids can be viewed as sets of lattice paths in certain planar diagrams.

In 1972, Rosenfeld asked if every triangle-free graph could be embedded in the unit sphere Sd in such a way that two vertices joined by an edge have distance more than (ie, distance more than 2π/3 on the sphere). In 1978, Larman [LAR] disproved this conjecture, constructing a triangle-free graph for which the minimum length of an edge could not exceed . In addition, he conjectured that the right answer would be , which is not better than the class of all graphs. Larman'sconjecture was independently proved by Rosenfeld [MR] and Rödl [VR[. In this last paper it was shown that no bound better than can be found for graphs with arbitrarily large odd girth. We prove in this paper that this is stilltrue for arbitrarily large girth. We discuss then the case of triangle-free graphs with linear minimum degree.

Let D(G) be the smallest quantifier depth of a first-order formula which is true for a graph G but false for any other non-isomorphic graph. This can be viewed as a measure for the descriptive complexity of G in first-order logic.

We show that almost surely , where G is a random tree of order n or the giant component of a random graph with constant c<1. These results rely on computing the maximum of D(T) for a tree T of order n and maximum degree l, so we study this problem as well.

In combinatorial optimization, a popular approach to NP-hard problems is the design of approximation algorithms. These algorithms typically run in polynomial time and are guaranteed to produce a solution which is within a known multiplicative factor of optimal. Unfortunately, the known factor is often known to be large in pathological instances. Conventional wisdom holds that, in practice, approximation algorithms will produce solutions closer to optimal than their proven guarantees. In this paper, we use the rigorous-analysis-of-heuristics framework to investigate this conventional wisdom.

We analyse the performance of three related approximation algorithms for the uncapacitated facility location problem (from Jain, Mahdian, Markakis, Saberi and Vazirani (2003) and Mahdian, Ye and Zhang (2002)) when each is applied to an instances created by placing n points uniformly at random in the unit square. We find that, with high probability, these 3 algorithms do not find asymptotically optimal solutions, and, also with high probability, a simple plane partitioning heuristic does find an asymptotically optimal solution.

Szemerédi's regularity lemma for graphs has proved to be a powerful tool with many subsequent applications. The objective of this paper is to extend the techniques developed by Nagle, Skokan, and the authors and obtain a stronger and more ‘user-friendly’ regularity lemma for hypergraphs.

Let A be a set of N matrices. Let g(A) ≔ |A + A| + |A · A|, where A + A = {a1 + a2 ∣ ai ∈ A} and A · A = {a1a2 ∣ ai ∈ A} are the sum set and product set. We prove that if the determinant of the difference of any two distinct matrices in A is nonzero, then g(A) cannot be bounded below by cN for any constant c. We also prove that if A is a set of d × d symmetric matrices, then there exists ϵ = ϵ(d)>0 such that g(A)>N1+ϵ. For the first result, we use the bound on the number of factorizations in a generalized progression. For the symmetric case, we use a technical proposition which provides an affine space V containing a large subset E of A, with the property that if an algebraic property holds for a large subset of E, then it holds for V. Then we show that the system a2 : a ∈ V is commutative, allowing us to decompose as eigenspaces simultaneously, so we can finish the proof with induction and a variant of the Erdős–Szemerédi argument.

We study negative dependence properties of a sampling process due to Srinivasan to produce distributions on level sets with given marginals. We give a simple proof that the distribution satisfies negative association. We also show that under a linear match schedule it satisfies the stronger condition of conditional negative association via a non-trivial application of the Feder–Mihail theorem. This method involves the notion of a variable of positive influence. We give some results and related counter-examples which might shed some light on its role in a theory of negative dependence.

In this note we give a very short proof for the description of all maximum size two-part Sperner systems.

The chromatic polynomial PΓ(x) of a graph Γ is a polynomial whose value at the positive integer k is the number of proper k-colourings of Γ. If G is a group of automorphisms of Γ, then there is a polynomial OPΓ,G(x), whose value at the positive integer k is the number of orbits of G on proper k-colourings of Γ.

It is known that real chromatic roots cannot be negative, but they are dense in ∞). Here we discuss the location of real orbital chromatic roots. We show, for example, that they are dense in , but under certain hypotheses, there are zero-free regions.

We also look at orbital flow roots. Here things are more complicated because the orbit count is given by a multivariate polynomial; but it has a natural univariate specialization, and we show that the roots of these polynomials are dense in the negative real axis.

We show that every regular tournament on n vertices has at least n!/(2 + o(1))n Hamiltonian cycles, thus answering a question of Thomassen [17] and providing a partial answer to a question of Friedgut and Kahn [7]. This compares to an upper bound of about O(n0.25n!/2n) for arbitrary tournaments due to Friedgut and Kahn (somewhat improving Alon's bound of O(n0.5n!/2n)). A key ingredient of the proof is a martingale analysis of self-avoiding walks on a regular tournament.