Umeå University's logo

Consider the partially ordered set on [t]n:={0,…,t−1}n equipped with the natural coordinate-wise ordering, and let A(t,n) denote the number of antichains of this poset. Determining A(2,n) is the celebrated problem of Dedekind from 1897, and the general quantity A(t,n) has a number of combinatorial interpretations: it is precisely the number of (n−1)-dimensional partitions with entries from {0,…,t}, and by a result of Moshkovitz and Shapira, A(t,n)+1 is equal to the n -color Ramsey number of monotone paths of length t in 3-uniform hypergraphs. This has led to significant interest in the growth rate of A(t,n). Trivially, log2⁡A(t,n)≥α(t,n), where α(t,n) is the size of a maximal antichain in [t]n. In the present paper, we prove that this simple lower bound is close to optimal, in particular for every t,n≥2, log2⁡A(t,n)≤(1+O((log⁡n)3n))⋅α(t,n). This resolves a conjecture of Moshkovitz and Shapira, and gives the first bound that is close to optimal for growing t . Our proof is based on the graph container method, partly inspired by previous work of Pohoata and Zakharov. One of our main contributions is a novel supersaturation result in [t]n. We prove that for any k∈Z+ and δ>0, any set A⊂[t]n of size at least (k+δ)α(t,n) contains a vertex comparable to at least Ωδ,k((n/log⁡n)k) other elements of A , a bound that is optimal up to logarithmic factors. We achieve this by constructing a normalized matching flow on the cover graph of [t]n in which the distribution of weights is close to uniform, a result that may be of independent interest.

In this short note, we prove that every twin-free graph on n vertices contains a locating-dominating set of size at most ⌈[Formula presented]n⌉. This improves the earlier bound of ⌊[Formula presented]n⌋ due to Foucaud, Henning, Löwenstein and Sasse from 2016, and makes some progress towards the well-studied locating-dominating conjecture of Garijo, González and Márquez.

We consider the random right-angled Coxeter group WΓ whose presentation graph Γ∼Gn,p is an Erdős–Rényi random graph on n vertices with edge probability p=p(n). We establish that p=1/n is a threshold for relative hyperbolicity of the random group WΓ. As a key step in the proof, we determine the minimal number of pairs of generators that must commute in a right-angled Coxeter group which is not relatively hyperbolic, a result which is of independent interest.

We also show that there is an interval of edge probabilities of width Ω(1/n) in which the random right-angled Coxeter group has precisely cubic divergence. This interval is between the thresholds for relative hyperbolicity (whence exponential divergence) and quadratic divergence. Moreover, a simple random walk on any Cayley graph of the random right-angled Coxeter group for p in this interval satisfies a central limit theorem.

Let G:=(G₁,G₂,G₃) be a triple of graphs on a common vertex set V of size n. A rainbow triangle in G is a triple of edges (e₁,e₂,e₃) with e_i ∈ G_i for each i and {e₁,e₂,e₃} forming a triangle in V. In this paper we consider the following question: what triples of minimum degree conditions (∂(G₁),∂(G₂),∂(G₃)) guarantee the existence of a rainbow triangle? This may be seen as a minimum degree version of a problem of Aharoni, DeVos, de la Maza, Montejanos and Šámal on density conditions for rainbow triangles, which was recently resolved by the authors. We establish that the extremal behaviour in the minimum degree setting differs strikingly from that seen in the density setting, with discrete jumps as opposed to continuous transitions. Our work leaves a number of natural questions open, which we discuss.

A multigraph G is an (s,q)-graph if every s-set of vertices in G supports at most q edges of G, counting multiplicities. Mubayi and Terry posed the problem of determining the maximum of the product of the edge-multiplicities in an (s,q)-graph on n vertices. We give an asymptotic solution to this problem for the family (s,q)=(2r,a(^2r₂)+ex(2r,K_r+1)−1) with r,a ∈ Z_≥2. This greatly generalises previous results on the problem due to Mubayi and Terry and to Day, Treglown and the author, who between them had resolved the special case r=2. Our result asymptotically confirms an infinite family of cases in (and overcomes a major obstacle to a resolution of) a conjecture of Day, Treglown and the author.

Let G be an r-partite graph such that the edge density between any two parts is at least α. How large does α need to be to guarantee that G contains a connected transversal, that is, a tree on r vertices meeting each part in one vertex? And what if instead we want to guarantee the existence of a Hamiltonian transversal? In this paper we initiate the study of such extremal multipartite graph problems, obtaining a number of results and providing many new constructions, conjectures and further questions.

Let G:=(G₁,G₂,G₃) be a triple of graphs on the same vertex set V of size n. A rainbow triangle in G is a triple of edges (e₁,e₂,e₃) with e_i ∈ G_i for each i and {e₁,e₂,e₃} forming a triangle in V. The triples G not containing rainbow triangles, also known as Gallai colouring templates, are a widely studied class of objects in extremal combinatorics. In the present work, we fully determine the set of edge densities (α₁,α₂,α₃) such that if |E(G_i)| >α_in² for each i and n is sufficiently large, then G must contain a rainbow triangle. This resolves a problem raised by Aharoni, DeVos, de la Maza, Montejanos and Šámal, generalises several previous results on extremal Gallai colouring templates, and proves a recent conjecture of Frankl, Győri, He, Lv, Salia, Tompkins, Varga and Zhu.

A random graph model on a host graph (Formula presented.) is said to be 1-independent if for every pair of vertex-disjoint subsets (Formula presented.) of (Formula presented.), the state of edges (absent or present) in (Formula presented.) is independent of the state of edges in (Formula presented.). For an infinite connected graph (Formula presented.), the 1-independent critical percolation probability (Formula presented.) is the infimum of the (Formula presented.) such that every 1-independent random graph model on (Formula presented.) in which each edge is present with probability at least (Formula presented.) almost surely contains an infinite connected component. Balister and Bollobás observed in 2012 that (Formula presented.) tends to a limit in (Formula presented.) as (Formula presented.), and they asked for the value of this limit. We make progress on a related problem by showing that (Formula presented.) In fact, we show that the equality above remains true if the sequence of complete graphs (Formula presented.) is replaced by a sequence of weakly pseudorandom graphs on (Formula presented.) vertices with average degree (Formula presented.). We conjecture the answer to Balister and Bollobás's question is also (Formula presented.).

Following Bradonji´c and Saniee, we study a model of bootstrap percolation on the Gilbert random geometric graph on the 2-dimensional torus. In this model, the expected number of vertices of the graph is n, and the expected degree of a vertex is a log n for some fixed a>1. Each vertex is added with probability p to a set A0 of initially infected vertices. Vertices subsequently become infected if they have at least θa log n infected neighbours. Here p, θ ∈ [0, 1] are taken to be fixed constants.

We show that if θ <(1+p)/2, then a sufficiently large local outbreak leads with high probability to the infection spreading globally, with all but o(n) vertices eventually becoming infected. On the other hand, for θ >(1+p)/2, even if one adversarially infects every vertex inside a ball of radius O(√log n), with high probability the infection will spread to only o(n) vertices beyond those that were initially infected.

In addition we give some bounds on the (a, p, θ) regions ensuring the emergence of large local outbreaks or the existence of islands of vertices that never become infected. We also give a complete picture of the (surprisingly complex) behaviour of the analogous 1-dimensional bootstrap percolation model on the circle. Finally we raise a number of problems, and in particular make a conjecture on an ‘almost no percolation or almost full percolation’ dichotomy which may be of independent interest.