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

A proper vertex coloring of a graph is called equitable if the sizes of colour classes differ by at most 1. In this paper, we find the minimum number l=l(d, Δ) such that every d-degenerate graph with maximum degree at most Δ admits an equitable t-colouring for every t[ges ]l when Δ[ges ]27d.

We determine the asymptotic behaviour of the number of Eulerian circuits in a complete graph of odd order. One corollary of our result is the following. If a maximum random walk, constrained to use each edge at most once, is taken on Kn, then the probability that all the edges are eventually used is asymptotic to e3/4n−½. Some similar results are obtained about Eulerian circuits and spanning trees in random regular tournaments. We also give exact values for up to 21 nodes.

Suppose that X1, X2, . . . are independent identically distributed Bernoulli random variables with mean p. A Bernoulli factory for a function f takes as input X1, X2, . . . and outputs a random variable that is Bernoulli with mean f(p). A fast algorithm is a function that only depends on the values of X1, . . ., XT, where T is a stopping time with small mean. When f(p) is a real analytic function the problem reduces to being able to draw from linear functions Cp for a constant C > 1. Also it is necessary that Cp ⩽ 1 − ε for known ε > 0. Previous methods for this problem required extensive modification of the algorithm for every value of C and ε. These methods did not have explicit bounds on $\mathbb{E}[T]$ as a function of C and ε. This paper presents the first Bernoulli factory for f(p) = Cp with bounds on $\mathbb{E}[T]$ as a function of the input parameters. In fact, supp∈[0,(1−ε)/C]$\mathbb{E}[T]$ ≤ 9.5ε−1C. In addition, this method is very simple to implement. Furthermore, a lower bound on the average running time of any Cp Bernoulli factory is shown. For ε ⩽ 1/2, supp∈[0,(1−ε)/C]$\mathbb{E}[T]$≥0.004Cε−1, so the new method is optimal up to a constant in the running time.

Consider the integer lattice L = ℤ2. For some m [ges ] 4, let us colour each column of this lattice independently and uniformly with one of m colours. We do the same for the rows, independently of the columns. A point of L will be called blocked if its row and column have the same colour. We say that this random configuration percolates if there is a path in L starting at the origin, consisting of rightward and upward unit steps, avoiding the blocked points. As a problem arising in distributed computing, it has been conjectured that for m [ges ] 4 the configuration percolates with positive probability. This question remains open, but we prove that the probability that there is percolation to distance n but not to infinity is not exponentially small in n. This narrows the range of methods available for proving the conjecture.

This paper is partly an overview of the subject (Sections 1–4), and partly a research paper containing proofs for new results (Sections 5–7).

We introduce a new model of competition on growing networks. This extends the preferential attachment model, with the key property that node choices evolve simultaneously with the network. When a new node joins the network, it chooses neighbours by preferential attachment, and selects its type based on the number of initial neighbours of each type. The model is analysed in detail, and in particular, we determine the possible proportions of the various types in the limit of large networks. An important qualitative feature we find is that, in contrast to many current theoretical models, often several competitors will coexist. This matches empirical observations in many real-world networks.

We identify the asymptotic probability of a configuration model CMn(d) producing a connected graph within its critical window for connectivity that is identified by the number of vertices of degree 1 and 2, as well as the expected degree. In this window, the probability that the graph is connected converges to a non-trivial value, and the size of the complement of the giant component weakly converges to a finite random variable. Under a finite second moment condition we also derive the asymptotics of the connectivity probability conditioned on simplicity, from which follows the asymptotic number of simple connected graphs with a prescribed degree sequence.

This paper deals with a combinatorial problem concerning colourings of uniform hypergraphs with large girth. We prove that if H is an n-uniform non-r-colourable simple hypergraph then its maximum edge degree Δ(H) satisfies the inequality

$$ \Delta(H)\geqslant c\cdot r^{n-1}\ffrac{n(\ln\ln n)^2}{\ln n} $$

As an application of our probabilistic technique we establish a lower bound for the classical van der Waerden number W(n, r), the minimum natural N such that in an arbitrary colouring of the set of integers {1,. . .,N} with r colours there exists a monochromatic arithmetic progression of length n. We prove that

$$ W(n,r)\geqslant c\cdot r^{n-1}\ffrac{(\ln\ln n)^2}{\ln n}. $$

We show that, if G is a graph of order n with maximal degree Δ(G) and minimal degree δ(G) whose complement contains no K2,s, s [ges ] 2, then G contains every tree T of order n−s+1 whose maximal degree is at most Δ(G) and whose vertex of second-largest degree is at most δ(G). We then show that this result implies that special cases of two conjectures are true. We verify that the Erdös–Sós conjecture, which states that a graph whose average degree is larger than k−1 contains every tree of order k+1, is true for graphs whose complement does not contain a K2,4, and the Komlós–Sós conjecture, which states that every graph of median degree at least k contains every tree of order k+1, is true for graphs whose complement does not contain a K2,3.

We say that $n$-vertex graphs $G_1,G_2,\ldots,G_k$pack if there exist injective mappings of their vertex sets onto $[n] = \{1, \ldots,n \}$ such that the images of the edge sets do not intersect. The notion of packing allows one to make some problems on graphs more natural or more general. Clearly, two $n$-vertex graphs $G_1$ and $G_2$ pack if and only if $G_1$ is a subgraph of the complement $\overline{G}_2$ of $G_2$.

A family of subsets of an n-set is k-locally thin if, for every k of its member sets, the ground set has at least one element contained in exactly 1 of them. We derive new asymptotic upper bounds for the maximum cardinality of locally thin set families for every even k. This improves on previous results of two of the authors with Monti.

The Brownian separable permuton is a random probability measure on the unit square, which was introduced by Bassino, Bouvel, Féray, Gerin and Pierrot (2016) as the scaling limit of the diagram of the uniform separable permutation as size grows to infinity. We show that, almost surely, the permuton is the pushforward of the Lebesgue measure on the graph of a random measure-preserving function associated to a Brownian excursion whose strict local minima are decorated with independent and identically distributed signs. As a consequence, its support is almost surely totally disconnected, has Hausdorff dimension one, and enjoys self-similarity properties inherited from those of the Brownian excursion. The density function of the averaged permuton is computed and a connection with the shuffling of the Brownian continuum random tree is explored.

Our aim in this note is to make some conjectures about extremal densities of daisy-free families, where a ‘daisy’ is a certain hypergraph. These questions turn out to be related to some Turán problems in the hypercube, but they are also natural in their own right. We start by giving the daisy conjectures, and some related problems, and shall then go on to describe the connection with vertex-Turán problems in the hypercube.

Zeilberger's enumeration schemes can be used to completely automate the enumeration of many permutation classes. We extend his enumeration schemes so that they apply to many more permutation classes and describe the Maple package WilfPlus, which implements this process. We also compare enumeration schemes to three other systematic enumeration techniques: generating trees, substitution decompositions, and the insertion encoding.

For each poset H whose Hasse diagram is a tree of height k, we show that the largest size of a family of subsets of [n]={1,. . ., n} not containing H as an induced subposet is asymptotic to . This extends a result of Bukh [1], which in turn generalizes several known results including Sperner's theorem.

Consider the following one-player game. Starting with the empty graph on n vertices, in every step a new edge is drawn uniformly at random and inserted into the current graph. This edge has to be coloured immediately with one of r available colours. The player's goal is to avoid creating a monochromatic copy of some fixed graph F for as long as possible. We prove an upper bound on the typical duration of this game if F is from a large class of graphs including cliques and cycles of arbitrary size. Together with lower bounds published elsewhere, explicit threshold functions follow.

We consider linear preferential attachment trees, and show that they can be regarded as random split trees in the sense of Devroye (1999), although with infinite potential branching. In particular, this applies to the random recursive tree and the standard preferential attachment tree. An application is given to the sum over all pairs of nodes of the common number of ancestors.

Let Hd(n,p) signify a random d-uniform hypergraph with n vertices in which each of the $\binom{n}{d}$ possible edges is present with probability p=p(n) independently, and let Hd(n,m) denote a uniformly distributed d-uniform hypergraph with n vertices and m edges. We derive local limit theorems for the joint distribution of the number of vertices and the number of edges in the largest component of Hd(n,p) and Hd(n,m) in the regime $(d-1)\binom{n-1}{d-1}p>1+\varepsilon$, resp. d(d−1)m/n>1+ϵ, where ϵ>0 is arbitrarily small but fixed as n → ∞. The proofs are based on a purely probabilistic approach.

Szemerédi's regularity lemma and its variants are some of the most powerful tools in combinatorics. In this paper, we establish several results around the regularity lemma. First, we prove that whether or not we include the condition that the desired vertex partition in the regularity lemma is equitable has a minimal effect on the number of parts of the partition. Second, we use an algorithmic version of the (weak) Frieze–Kannan regularity lemma to give a substantially faster deterministic approximation algorithm for counting subgraphs in a graph. Previously, only an exponential dependence for the running time on the error parameter was known, and we improve it to a polynomial dependence. Third, we revisit the problem of finding an algorithmic regularity lemma, giving approximation algorithms for several co-NP-complete problems. We show how to use the weak Frieze–Kannan regularity lemma to approximate the regularity of a pair of vertex subsets. We also show how to quickly find, for each ε′>ε, an ε′-regular partition with k parts if there exists an ε-regular partition with k parts. Finally, we give a simple proof of the permutation regularity lemma which improves the tower-type bound on the number of parts in the previous proofs to a single exponential bound.