We consider k-uniform set systems over a universe of size n such that the size of each pairwise intersection of sets lies in one of s residue classes mod q, but k does not lie in any of these s classes. A celebrated theorem of Frankl and Wilson [8] states that any such set system has size at most (ns) when q is prime. In a remarkable recent paper, Grolmusz [9] constructed set systems of superpolynomial size Ω(exp(c log2n/log log n)) when q = 6. We give a new, simpler construction achieving a slightly improved bound. Our construction combines a technique of Frankl [6] of ‘applying polynomials to set systems’ with Grolmusz's idea of employing polynomials introduced by Barrington, Beigel and Rudich [5]. We also extend Frankl's original argument to arbitrary prime-power moduli: for any ε > 0, we construct systems of size ns+g(s), where g(s) = Ω(s1−ε). Our work overlaps with a very recent technical report by Grolmusz [10].

Let TBin(N, n, q) be the game on the complete graph KN in which two players, the Breaker and the Maker, alternately claim one and q edges, respectively. The Maker's aim is to build a binary tree on n<N vertices in n−1 turns while the Breaker tries to prevent him from doing so. It is shown that, for every constant ε>0, there exists n0 such that, for every n[ges ]n0, the Breaker has a winning strategy in TBin(N, n, q) if q>(1+ε)N/logn, while, for q<(1−ε)N/logn, the game TBin(N, n, q) can be won by the Maker provided that n=o(N).

Let $\{D_M\}_{M\geq 0}$ be the n-vertex random directed graph process, where $D_0$ is the empty directed graph on n vertices, and subsequent directed graphs in the sequence are obtained by the addition of a new directed edge uniformly at random. For each $$\varepsilon > 0$$ , we show that, almost surely, any directed graph $D_M$ with minimum in- and out-degree at least 1 is not only Hamiltonian (as shown by Frieze), but remains Hamiltonian when edges are removed, as long as at most $1/2-\varepsilon$ of both the in- and out-edges incident to each vertex are removed. We say such a directed graph is $(1/2-\varepsilon)$ -resiliently Hamiltonian. Furthermore, for each $\varepsilon > 0$ , we show that, almost surely, each directed graph $D_M$ in the sequence is not $(1/2+\varepsilon)$ -resiliently Hamiltonian.

This improves a result of Ferber, Nenadov, Noever, Peter and Škorić who showed, for each $\varepsilon > 0$ , that the binomial random directed graph $D(n,p)$ is almost surely $(1/2-\varepsilon)$ -resiliently Hamiltonian if $p=\omega(\log^8n/n)$ .

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.

Let $P(G,t)$ and $F(G,t)$ denote the chromatic and flow polynomials of a graph $G$. G. D. Birkhoff and D C. Lewis showed that, if $G$ is a plane near-triangulation, then the only zeros of $P(G,t)$ in $(-\infty,2]$ are 0, 1 and 2. We will extend their theorem by showing that a stronger result to the dual statement holds for both planar and non-planar graphs: if $G$ is a bridge graph with at most one vertex of degree other than three, then the only zeros of $F(G,t)$ in $(-\infty,\alpha]$ are 1 and 2, where $\alpha\approx 2.225\cdots$ is the real zero in $(2,3)$ of the polynomial $t^4-8t^3+22t^2-28t+17$. In addition we construct a sequence of ‘near-cubic’ graphs whose flow polynomials have zeros converging to $\alpha$ from above.

We compute the limit shape for several classes of restricted integer partitions, where the restrictions are placed on the part sizes rather than the multiplicities. Our approach utilizes certain classes of bijections which map limit shapes continuously in the plane. We start with bijections outlined in [43], and extend them to include limit shapes with different scaling functions.

We compute the first three terms of the 1/d expansions for the growth constants and one-point functions of nearest-neighbour lattice trees and lattice (bond) animals on the integer lattice $\mathbb{Z}^d$, with rigorous error estimates. The proof uses the lace expansion, together with a new expansion for the one-point functions based on inclusion–exclusion.

We study the problem of finding pairwise vertex-disjoint triangles in the randomly perturbed graph model, which is the union of any $n$ -vertex graph $G$ satisfying a given minimum degree condition and the binomial random graph $G(n,p)$ . We prove that asymptotically almost surely $G \cup G(n,p)$ contains at least $\min \{\delta (G), \lfloor n/3 \rfloor \}$ pairwise vertex-disjoint triangles, provided $p \ge C \log n/n$ , where $C$ is a large enough constant. This is a perturbed version of an old result of Dirac.

Our result is asymptotically optimal and answers a question of Han, Morris, and Treglown [RSA, 2021, no. 3, 480–516] in a strong form. We also prove a stability version of our result, which in the case of pairwise vertex-disjoint triangles extends a result of Han, Morris, and Treglown [RSA, 2021, no. 3, 480–516]. Together with a result of Balogh, Treglown, and Wagner [CPC, 2019, no. 2, 159–176], this fully resolves the existence of triangle factors in randomly perturbed graphs.

We believe that the methods introduced in this paper are useful for a variety of related problems: we discuss possible generalisations to clique factors, cycle factors, and $2$ -universality.

We study I(T), the number of inversions in a tree T with its vertices labelled uniformly at random, which is a generalization of inversions in permutations. We first show that the cumulants of I(T) have explicit formulas involving the k-total common ancestors of T (an extension of the total path length). Then we consider Xn, the normalized version of I(Tn), for a sequence of trees Tn. For fixed Tn's, we prove a sufficient condition for Xn to converge in distribution. As an application, we identify the limit of Xn for complete b-ary trees. For Tn being split trees [16], we show that Xn converges to the unique solution of a distributional equation. Finally, when Tn's are conditional Galton–Watson trees, we show that Xn converges to a random variable defined in terms of Brownian excursions. By exploiting the connection between inversions and the total path length, we are able to give results that significantly strengthen and broaden previous work by Panholzer and Seitz [46].

We define uniformly spread sets as point sets in d-dimensional Euclidean space that are wobbling equivalent to the standard lattice ℤd. A linear image ϕ(ℤd) of ℤd is shown to be uniformly spread if and only if det(ϕ) = 1. Explicit geometrical and number-theoretical constructions are given. In 2-dimensional Euclidean space we obtain bounds for the wobbling distance for rotations, shearings and stretchings that are close to optimal. Our methods also allow us to analyse the discrepancy of certain billiards. Finally, we take a look at paradoxical situations and exhibit recursive point sets that are wobbling equivalent, but not recursively so.

Considering a natural generalization of the Ruzsa–Szemerédi problem, we prove that for any fixed positive integers r, s with r < s, there are graphs on n vertices containing $n^{r}e^{-O\left(\sqrt{\log{n}}\right)}=n^{r-o(1)}$ copies of Ks such that any Kr is contained in at most one Ks. We also give bounds for the generalized rainbow Turán problem ex (n, H, rainbow - F) when F is complete. In particular, we answer a question of Gerbner, Mészáros, Methuku and Palmer, showing that there are properly edge-coloured graphs on n vertices with $n^{r-1-o(1)}$ copies of Kr such that no Kr is rainbow.

Let f be a de Morgan read-once function of n variables. Let fε be the random restriction obtained by independently assigning to each variable of f, the value 0 with probability (1 -ε)/2, the value 1 with the same probability, and leaving it unassigned with probability ε. We show that fε depends, on the average, on only O(εαn + εn1/α) variables, where . This result is asymptotically the tightest possible. It improves a similar result obtained recently by Håstad, Razborov and Yao.

We consider the Widom–Rowlinson model of two types of interacting particles on d-regular graphs. We prove a tight upper bound on the occupancy fraction, the expected fraction of vertices occupied by a particle under a random configuration from the model. The upper bound is achieved uniquely by unions of complete graphs on d + 1 vertices, Kd+1. As a corollary we find that Kd+1 also maximizes the normalized partition function of the Widom–Rowlinson model over the class of d-regular graphs. A special case of this shows that the normalized number of homomorphisms from any d-regular graph G to the graph HWR, a path on three vertices with a loop on each vertex, is maximized by Kd+1. This proves a conjecture of Galvin.

Let σ, π be two permutations selected at random from the uniform distribution on the symmetric group Sn. By a result of Dixon [5], the subgroup G generated by σ, π is almost always (i.e. with probability approaching 1 as n → ∞) either Sn or the alternating group An. We prove that the diameter of the Cayley graph of G defined by {σ, π} is almost always not greater than exp ((½ + o(l)). (In n)2).

We consider numbers and sizes of independent sets in graphs with minimum degree at least d. In particular, we investigate which of these graphs yield the maximum numbers of independent sets of different sizes, and which yield the largest random independent sets. We establish a strengthened form of a conjecture of Galvin concerning the first of these topics.

We show that the expected number of maximal empty axis-parallel boxes amidst n random points in the unit hypercube [0,1]d in $\mathbb{R}^d$ is (1 ± o(1)) $\frac{(2d-2)!}{(d-1)!}$n lnd−1n, if d is fixed. This estimate is relevant to analysis of the performance of exact algorithms for computing the largest empty axis-parallel box amidst n given points in an axis-parallel box R, especially the algorithms that proceed by examining all maximal empty boxes. Our method for bounding the expected number of maximal empty boxes also shows that the expected number of maximal empty orthants determined by n random points in $\mathbb{R}^d$ is (1 ± o(1)) lnd−1n, if d is fixed. This estimate is related to the expected number of maximal (or minimal) points amidst random points, and has application to algorithms for coloured orthogonal range counting.

For a given graph G of minimum degree at least k, let Gp denote the random spanning subgraph of G obtained by retaining each edge independently with probability p = p(k). We prove that if p ⩾ (logk + loglogk + ωk(1))/k, where ωk(1) is any function tending to infinity with k, then Gp asymptotically almost surely contains a cycle of length at least k + 1. When we take G to be the complete graph on k + 1 vertices, our theorem coincides with the classic result on the threshold probability for the existence of a Hamilton cycle in the binomial random graph.

A digraph is m-labelled if every arc is labelled by an integer in {1, . . ., m}. Motivated by wavelength assignment for multicasts in optical networks, we introduce and study n-fibre colourings of labelled digraphs. These are colourings of the arcs of D such that at each vertex v, and for each colour α, in(v, α) + out(v, α) ≤ n with in(v, α) the number of arcs coloured α entering v and out(v, α) the number of labels l such that there is at least one arc of label l leaving v and coloured with α. The problem is to find the minimum number of colours λn(D) such that the m-labelled digraph D has an n-fibre colouring. In the particular case when D is 1-labelled, λ1(D) is called the directed star arboricity of D, and is denoted by dst(D). We first show that dst(D) ≤ 2Δ−(D)+1, and conjecture that if Δ−(D) ≥ 2, then dst(D) ≤ 2Δ−(D). We also prove that for a subcubic digraph D, then dst(D) ≤ 3, and that if Δ+(D), Δ−(D) ≤ 2, then dst(D) ≤ 4. Finally, we study λn(m, k) = max{λn(D) | D is m-labelled and Δ−(D) ≤ k}. We show that if m ≥ n, then for some constant C. We conjecture that the lower bound should be the correct value of λn(m, k).

Kuratowski's Theorem, perhaps the most famous result in graph theory, states that K5 and K3,3 are the only non-planar graphs for which both G\e, the deletion of the edge e, and G/e, the contraction of the edge e, are planar for all edges e of G. We characterize the almost-planar graphs, those non-planar graphs for which G\e or G/e is planar for all edges e of G. This paper gives two characterizations of the almost-planar graphs: an explicit description of the structure of almost-planar graphs; and an excluded minor criterion. We also give a best possible bound on the number of edges of an almost-planar graph.

A graph G is called n-minimizable if it can be reduced, by deleting a set of its edges, to a minimally n-connected graph. It is shown that, if n-connected graphs G and H differ only by finitely many vertices and edges, then G is n-minimizable if and only if H is n-minimizable (Theorem 4.12). In the main result, conditions are given that a tree decomposition of an n-connected graph G must satisfy in order to guarantee that the n-minimizability of each of the members of this decomposition implies the n-minimizability of the graph G (Theorem 6.5).