The asymptotics of 2-colour Ramsey numbers of loose and tight cycles in 3-uniform hypergraphs were recently determined [16, 17]. We address the same problem for Berge cycles and for 3 colours. Our main result is that the 3-colour Ramsey number of a 3-uniform Berge cycle of length n is asymptotic to . The result is proved with the Regularity Lemma via the existence of a monochromatic connected matching covering asymptotically 4n/5 vertices in the multicoloured 2-shadow graph induced by the colouring of Kn(3).

A (not necessarily proper) vertex colouring of a graph has clustering c if every monochromatic component has at most c vertices. We prove that planar graphs with maximum degree $\Delta$ are 3-colourable with clustering $O(\Delta^2)$. The previous best bound was $O(\Delta^{37})$. This result for planar graphs generalises to graphs that can be drawn on a surface of bounded Euler genus with a bounded number of crossings per edge. We then prove that graphs with maximum degree $\Delta$ that exclude a fixed minor are 3-colourable with clustering $O(\Delta^5)$. The best previous bound for this result was exponential in $\Delta$.

We show that, if M is a connected binary matroid of cogirth at least five which does not have both an F7-minor and an F*7-minor, then M has a circuit C such that M − C is connected and r(M − C) = r(M).

It is known that random $k$-Sat instances with at least $(2^k \cdot \ln 2)\cdot n$ random clauses are unsatisfiable with high probability. This result is simply obtained by showing that the expected number of satisfying assignments tends to $0$ when the number of variables $n$ tends to infinity. This proof does not directly provide us with an efficient algorithm certifying the unsatisfiability of a given random formula. Concerning efficient algorithms, it is essentially known that random formulas with $n^\varepsilon \cdot n^{k/2}$ clauses with $k$ literals can be efficiently certified as unsatisfiable. The present paper is the result of trying to lower this bound. We obtain better bounds for some specialized satisfiability problems. These results are based on discrepancy investigations for hypergraphs.

Further, we show that random formulas with a linear number of clauses can be efficiently certified as unsatisfiable in the Not-All-Equal-$3$-Sat sense. A similar result holds for the non-$3$-colourability of random graphs with a linear number of edges. We obtain these results by direct application of approximation algorithms.

For random trees T generated by the binary search tree algorithm from uniformly distributed input we consider the subtree size profile, which maps k ∈ ℕ to the number of nodes in T that root a subtree of size k. Complementing earlier work by Devroye, by Feng, Mahmoud and Panholzer, and by Fuchs, we obtain results for the range of small k-values and the range of k-values proportional to the size n of T. In both cases emphasis is on the process view, i.e., the joint distributions for several k-values. We also show that the dynamics of the tree sequence lead to a qualitative difference between the asymptotic behaviour of the lower and the upper end of the profile.

In this paper we prove that, if a collection of sets [Ascr ] is union-closed, then the average set size of $\cal A is at least $\frac{1}{2}\log_2 (\vert{\cal A}\vert)$.

A graph Γ with diameter d is strongly distance-regular if Γ is distance-regular and its distance-d graph Γd is strongly regular. Some known examples of such graphs are the connected strongly regular graphs, with distance-d graph Γd = Γ (the complement of Γ), and the antipodal distance-regular graphs. Here we study some spectral conditions for a (regular or distance-regular) graph to be strongly distance-regular. In particular, for the case d = 3 the following characterization is proved. A regular (connected) graph Γ, with distinct eigenvalues λ0 > λ1 > λ2 > λ3, is strongly distance-regular if and only if λ2 = −1, and Γ3 is k-regular with degree k satisfying an expression which depends only on the order and the different eigenvalues of Γ.

Consider two graphs G1 and G2 on the same vertex set V and suppose that Gi has mi edges. Then there is a bipartition of V into two classes A and B so that, for both i = 1, 2, we have . This gives an approximate answer to a question of Bollobás and Scott. We also prove results about partitions into more than two vertex classes. Our proofs yield polynomial algorithms.

A celebrated theorem of Turán asserts that every graph on n vertices with more than $\frac{r\,{-}\,1}{2r}n^2$ edges contains a copy of a complete graph $K_r+1$. In this paper we consider the following more general question. Let G be a $K_r+1-free graph of order n and let α be a constant, 0<α≤1. How dense can every induced subgraph of G on αn vertices be? We prove the following local density extension of Turán's theorem.

For every integer $r\geq 2$ there exists a constant $c_r < 1$ such that, if $c_r < \alpha < 1$ and every αn vertices of G span more than

\[ \frac{r\,{-}\,1}{2r}(2\alpha -1)n^2\vspace*{7pt} \]

edges, then G contains a copy of $K_r+1$. This result is clearly best possible and answers a question of Erdős, Faudree, Rousseau and Schelp [5].

In addition, we prove that the only $K_r+1-free graph of order n, in which every αn vertices span at least $\frac{r\,{-}\,1}{2r}(2\alpha -1)n^2$ edges, is a Turán graph. We also obtain the local density version of the Erdős–Stone theorem.

We consider the problem of fault diagnosis in multiprocessor systems. Processors perform tests on one another: fault-free testers correctly identify the fault status of tested processors, while faulty testers can give arbitrary test results. Processors fail independently with constant probability p<1/2 and the goal is to identify correctly the status of all processors, based on the set of test results. For 0<q<1, q-diagnosis is a fault diagnosis algorithm whose probability of error does not exceed q. We show that the minimum number of tests to perform q-diagnosis for n processors is Θ(n log 1/q) in the nonadaptive case and n+Θ( log 1/q) in the adaptive case. We also investigate q-diagnosis algorithms that minimize the maximum number of tests performed by, and performed on, processors in the system, constructing testing schemes in which each processor is involved in very few tests. Our results demonstrate that the flexibility yielded by adaptive testing permits a significant saving in the number of tests for the same reliability of diagnosis.

The study of the structural properties of large random planar graphs has become in recent years a field of intense research in computer science and discrete mathematics. Nowadays, a random planar graph is an important and challenging model for evaluating methods that are developed to study properties of random graphs from classes with structural side constraints.

In this paper we focus on the structure of random 2-connected planar graphs regarding the sizes of their 3-connected building blocks, which we call cores. In fact, we prove a general theorem regarding random biconnected graphs from various classes. If Bn is a graph drawn uniformly at random from a suitable class of labelled biconnected graphs, then we show that with probability 1 − o(1) as n → ∞, Bn belongs to exactly one of the following categories:

1. (i) either there is a unique giant core in Bn, that is, there is a 0 < c = c() < 1 such that the largest core contains ~ cn vertices, and every other core contains at most nα vertices, where 0 < α = α() < 1;

2. (ii) or all cores of Bn contain O(logn) vertices.

In this paper we investigate a partitioning problem, setting the existence problem for all group-divisible designs with first and second associates in which the blocks are 4-cycles.

A colouring of a graph G is called distinguishing if its stabilizer in Aut G is trivial. It has been conjectured that, if every automorphism of a locally finite graph moves infinitely many vertices, then there is a distinguishing 2-colouring. We study properties of random 2-colourings of locally finite graphs and show that the stabilizer of such a colouring is almost surely nowhere dense in Aut G and a null set with respect to the Haar measure on the automorphism group. We also investigate random 2-colourings in several classes of locally finite graphs where the existence of a distinguishing 2-colouring has already been established. It turns out that in all of these cases a random 2-colouring is almost surely distinguishing.

Let {Av}v∈V be a finite collection of events and G = (V, E) be a chordal graph. Our main result – the chordal graph sieve – is a Bonferroni-type inequality where the selection of intersections in the estimates is determined by a chordal graph G. It interpolates between Boole's inequality (G empty) and the sieve formula (G complete). By varying G, several inequalities both well-known and new are obtained in a concise and unified way.

Complete disorder is impossible – this theme of Ramsey Theory, as stated by Theodore S. Motzkin, was a guiding theme throughout Walter Deuber's scientific life.

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

We show that, for any finite set P of points in the plane and for any integer k ≥ 2, there is a finite set R = R(P, k) with the following property: for any k-colouring of R there is a monochromatic set , ⊆ R, such that is combinatorially equivalent to the set P, and the convex hull of P contains no point of R \ . We also consider related questions for colourings of p-element subsets of R (p > 1), and show that these analogues have negative solutions.

We define and efficiently compute the canonical flow on a graph, which is a certain feasible solution for the concurrent flow problem and exhibits invariance under the action of the automorphism group of the graph. Using estimates for the congestion of our canonical flow, we derive lower bounds on the crossing number, bisection width, and the edge and vertex expansion of a graph in terms of sizes of the edge and vertex orbits and the average distance in the graph. We further exhibit classes of graphs for which our lower bounds are tight within a multiplicative constant. Also, in cartesian product graphs a concurrent flow is constructed in terms of the concurrent flows in the factors, and in this way lower bounds for the edge and vertex expansion of the power graphs are derived in terms of that of the original graph.

In this paper we study planar first-passage percolation (FPP) models on random Delaunay triangulations. In [14], Vahidi-Asl and Wierman showed, using sub-additivity theory, that the rescaled first-passage time converges to a finite and non-negative constant μ. We show a sufficient condition to ensure that μ>0 and derive some upper bounds for fluctuations. Our proofs are based on percolation ideas and on the method of martingales with bounded increments.

An n-vertex graph G is c-Ramsey if it contains neither a complete nor an empty induced subgraph of size greater than c log n. Erdős, Faudree and Sós conjectured that every c-Ramsey graph with n vertices contains Ω(n5/2) induced subgraphs, any two of which differ either in the number of vertices or in the number of edges, i.e., the number of distinct pairs (|V(H)|, |E(H)|), as H ranges over all induced subgraphs of G, is Ω(n5/2). We prove an Ω(n2.3693) lower bound.