Let $\mathcal{F}$ be a family of r-uniform hypergraphs. The chromatic threshold of $\mathcal{F}$ is the infimum of all non-negative reals c such that the subfamily of $\mathcal{F}$ comprising hypergraphs H with minimum degree at least $c \binom{| V(H) |}{r-1}$ has bounded chromatic number. This parameter has a long history for graphs (r = 2), and in this paper we begin its systematic study for hypergraphs.

Łuczak and Thomassé recently proved that the chromatic threshold of the so-called near bipartite graphs is zero, and our main contribution is to generalize this result to r-uniform hypergraphs. For this class of hypergraphs, we also show that the exact Turán number is achieved uniquely by the complete (r + 1)-partite hypergraph with nearly equal part sizes. This is one of very few infinite families of non-degenerate hypergraphs whose Turán number is determined exactly. In an attempt to generalize Thomassen's result that the chromatic threshold of triangle-free graphs is 1/3, we prove bounds for the chromatic threshold of the family of 3-uniform hypergraphs not containing {abc, abd, cde}, the so-called generalized triangle.

In order to prove upper bounds we introduce the concept of fibre bundles, which can be thought of as a hypergraph analogue of directed graphs. This leads to the notion of fibre bundle dimension, a structural property of fibre bundles that is based on the idea of Vapnik–Chervonenkis dimension in hypergraphs. Our lower bounds follow from explicit constructions, many of which use a hypergraph analogue of the Kneser graph. Using methods from extremal set theory, we prove that these Kneser hypergraphs have unbounded chromatic number. This generalizes a result of Szemerédi for graphs and might be of independent interest. Many open problems remain.

A tournament T on a set V of n players is an orientation of the edges of the complete graph Kn on V; T will be called a random tournament if the directions of these edges are determined by a sequence {Yj[ratio ]j = 1, …, (n2)} of independent coin flips. If (y, x) is an edge in a (random) tournament, we say that y beats x. A set A ⊂ V, |A| = k, is said to be beaten if there exists a player y ∉ A such that y beats x for each x ∈ A. If such a y does not exist, we say that A is unbeaten. A (random) tournament on V is said to have property Sk if each k-element subset of V is beaten. In this paper, we use the Stein–Chen method to show that the probability distribution of the number W0 of unbeaten k-subsets of V can be well-approximated by that of a Poisson random variable with the same mean; an improved condition for the existence of tournaments with property Sk is derived as a corollary. A multivariate version of this result is proved next: with Wj representing the number of k-subsets that are beaten by precisely j external vertices, j = 0, 1, …, b, it is shown that the joint distribution of (W0, W1, …, Wb) can be approximated by a multidimensional Poisson vector with independent components, provided that b is not too large.

It has been known for several years that the lattice of subspaces of a finite vector space has a decomposition into symmetric chains, i.e. a decomposition into disjoint chains that are symmetric with respect to the rank function of the lattice. This paper gives a positive answer to the long-standing open problem of providing an explicit construction of such a symmetric chain decomposition for a given lattice of subspaces of a finite (dimensional) vector space. The construction is done inductively using Schubert normal forms and results in a bracketing algorithm similar to the well-known algorithm for Boolean lattices.

We consider the problem of minimizing the number of edges that are contained in triangles, among n-vertex graphs with a given number of edges. For sufficiently large n, we prove an exact formula for this minimum, which partially resolves a conjecture of Füredi and Maleki.

For any c ≥ 2, a c-strong colouring of the hypergraph G is an assignment of colours to the vertices of G such that, for every edge e of G, the vertices of e are coloured by at least min{c,|e|} distinct colours. The hypergraph G is t-intersecting if every two edges of G have at least t vertices in common.

A natural variant of a question of Erdős and Lovász is: For fixed c ≥ 2 and t ≥ 1, what is the minimum number of colours that is sufficient to c-strong colour any t-intersecting hypergraphs? The purpose of this note is to describe some open problems related to this question.

If φ is a scattered order type, and μ is a cardinal, then there exists a scattered order type ψ such that holds.

We prove a generalization of a theorem of Ganter concerning the embedding of partial Steiner systems into Steiner systems. As an application we discuss a further version of the problem of Rosenfeld on embedding graphs into strongly regular graphs.

Let h > w > 0 be two fixed integers. Let H be a random hypergraph whose hyperedges are all of cardinality h. To w-orient a hyperedge, we assign exactly w of its vertices positive signs with respect to the hyperedge, and the rest negative signs. A (w,k)-orientation of H consists of a w-orientation of all hyperedges of H, such that each vertex receives at most k positive signs from its incident hyperedges. When k is large enough, we determine the threshold of the existence of a (w,k)-orientation of a random hypergraph. The (w,k)-orientation of hypergraphs is strongly related to a general version of the off-line load balancing problem. The graph case, when h = 2 and w = 1, was solved recently by Cain, Sanders and Wormald and independently by Fernholz and Ramachandran. This settled a conjecture of Karp and Saks.

We compute the large N limit of the partition function of the Euclidean Yang–Mills measure on orientable compact surfaces with genus $g\geqslant 1$ and non-orientable compact surfaces with genus $g\geqslant 2$ , with structure group the unitary group ${\mathrm U}(N)$ or special unitary group ${\mathrm{SU}}(N)$ . Our proofs are based on asymptotic representation theory: more specifically, we control the dimension and Casimir number of irreducible representations of ${\mathrm U}(N)$ and ${\mathrm{SU}}(N)$ when N tends to infinity. Our main technical tool, involving ‘almost flat’ Young diagram, makes rigorous the arguments used by Gross and Taylor (1993, Nuclear Phys. B400(1–3) 181–208) in the setting of QCD, and in some cases, we recover formulae given by Douglas (1995, Quantum Field Theory and String Theory (Cargèse, 1993), Vol. 328 of NATO Advanced Science Institutes Series B: Physics, Plenum, New York, pp. 119–135) and Rusakov (1993, Phys. Lett. B303(1) 95–98).

The Tutte polynomial $T(G;x,y)$ of a graph evaluates to many interesting combinatorial quantities at various points in the $(x,y)$ plane, including the number of spanning trees, number of forests, number of acyclic orientations, the reliability polynomial, the partition function of the Q-state Potts model of a graph, and the Jones polynomial of an alternating link. The exact computation of $T(G;x,y)$ has been shown by Vertigan and Welsh [8] to be #P-hard at all but a few special points and on two hyperbolae, even in the restricted class of planar bipartite graphs. Attention has therefore been focused on approximation schemes. To date, positive results have been restricted to the upper half plane $y>1$, and most results have relied on a condition of sufficient denseness in the graph. In this paper we present an approach that yields a fully polynomial randomized approximation scheme for $T(G;x,y)$ for $x>1,\ y=1$, and for $T(G;2,0)$, in a class of sparse graphs. This is the first positive result that includes the important point $(2,0)$.

We study relaxations of proper two-colourings, such that the order of the induced monochromatic components in one (or both) of the colour classes is bounded by a constant. A colouring of a graph G is called (C1, C2)-relaxed if every monochromatic component induced by vertices of the first (second) colour is of order at most C1 (C2, resp.). We prove that the decision problem ‘Is there a (1, C)-relaxed colouring of a given graph G of maximum degree 3?’ exhibits a hardness jump in the component order C. In other words, there exists an integer f(3) such that the decision problem is NP-hard for every 2 ≤ C < f(3), while every graph of maximum degree 3 is (1, f(3))-relaxed colourable. We also show f(3) ≤ 22 by way of a quasilinear time algorithm, which finds a (1, 22)-relaxed colouring of any graph of maximum degree 3. Both the bound on f(3) and the running time greatly improve earlier results. We also study the symmetric version, that is, when C1 = C2, of the relaxed colouring problem and make the first steps towards establishing a similar hardness jump.

We prove that for every tree $T$ of radius $h$, there is an integer $c$ such that every $T$-minor-free graph is contained in $H\boxtimes K_c$ for some graph $H$ with pathwidth at most $2h-1$. This is a qualitative strengthening of the Excluded Tree Minor Theorem of Robertson and Seymour (GM I). We show that radius is the right parameter to consider in this setting, and $2h-1$ is the best possible bound.

Which patterns must a two-colouring of $K_n$ contain if each vertex has at least $\varepsilon n$ red and $\varepsilon n$ blue neighbours? We show that when $\varepsilon \gt 1/4$, $K_n$ must contain a complete subgraph on $\Omega (\log n)$ vertices where one of the colours forms a balanced complete bipartite graph.

When $\varepsilon \leq 1/4$, this statement is no longer true, as evidenced by the following colouring $\chi$ of $K_n$. Divide the vertex set into $4$ parts nearly equal in size as $V_1,V_2,V_3, V_4$, and let the blue colour class consist of the edges between $(V_1,V_2)$, $(V_2,V_3)$, $(V_3,V_4)$, and the edges contained inside $V_2$ and inside $V_3$. Surprisingly, we find that this obstruction is unique in the following sense. Any two-colouring of $K_n$ in which each vertex has at least $\varepsilon n$ red and $\varepsilon n$ blue neighbours (with $\varepsilon \gt 0$) contains a vertex set $S$ of order $\Omega _{\varepsilon }(\log n)$ on which one colour class forms a balanced complete bipartite graph, or which has the same colouring as $\chi$.

A collection of graphs is nearly disjoint if every pair of them intersects in at most one vertex. We prove that if $G_1, \dots, G_m$ are nearly disjoint graphs of maximum degree at most $D$, then the following holds. For every fixed $C$, if each vertex $v \in \bigcup _{i=1}^m V(G_i)$ is contained in at most $C$ of the graphs $G_1, \dots, G_m$, then the (list) chromatic number of $\bigcup _{i=1}^m G_i$ is at most $D + o(D)$. This result confirms a special case of a conjecture of Vu and generalizes Kahn’s bound on the list chromatic index of linear uniform hypergraphs of bounded maximum degree. In fact, this result holds for the correspondence (or DP) chromatic number and thus implies a recent result of Molloy and Postle, and we derive this result from a more general list colouring result in the setting of ‘colour degrees’ that also implies a result of Reed and Sudakov.

We observe returns of a simple random walk on a finite graph to a fixed node, and would like to infer properties of the graph, in particular properties of the spectrum of the transition matrix. This is not possible in general, but at least the set of eigenvalues can be recovered under fairly general conditions, e.g., when the graph has a node-transitive automorphism group. The main result is that by observing polynomially many returns, it is possible to estimate the spectral gap of such a graph up to a constant factor.

For an orientation H with n vertices, let T(H) denote the maximum possible number of labelled copies of H in an n-vertex tournament. It is easily seen that T(H) ≥ n!/2e(H), as the latter is the expected number of such copies in a random tournament. For n odd, let R(H) denote the maximum possible number of labelled copies of H in an n-vertex regular tournament. In fact, Adler, Alon and Ross proved that for H=Cn, the directed Hamilton cycle, T(Cn) ≥ (e−o(1))n!/2n, and it was observed by Alon that already R(Cn) ≥ (e−o(1))n!/2n. Similar results hold for the directed Hamilton path Pn. In other words, for the Hamilton path and cycle, the lower bound derived from the expectation argument can be improved by a constant factor. In this paper we significantly extend these results, and prove that they hold for a larger family of orientations H which includes all bounded-degree Eulerian orientations and all bounded-degree balanced orientations, as well as many others. One corollary of our method is that for any fixed k, every k-regular orientation H with n vertices satisfies T(H) ≥ (ek−o(1))n!/2e(H), and in fact, for n odd, R(H) ≥ (ek−o(1))n!/2e(H).

Strengthening Hadwiger’s conjecture, Gerards and Seymour conjectured in 1995 that every graph with no odd $K_t$ -minor is properly $(t-1)$ -colourable. This is known as the Odd Hadwiger’s conjecture. We prove a relaxation of the above conjecture, namely we show that every graph with no odd $K_t$ -minor admits a vertex $(2t-2)$ -colouring such that all monochromatic components have size at most $\lceil \frac{1}{2}(t-2) \rceil$ . The bound on the number of colours is optimal up to a factor of $2$ , improves previous bounds for the same problem by Kawarabayashi (2008, Combin. Probab. Comput. 17 815–821), Kang and Oum (2019, Combin. Probab. Comput. 28 740–754), Liu and Wood (2021, arXiv preprint, arXiv:1905.09495), and strengthens a result by van den Heuvel and Wood (2018, J. Lond. Math. Soc. 98 129–148), who showed that the above conclusion holds under the more restrictive assumption that the graph is $K_t$ -minor-free. In addition, the bound on the component-size in our result is much smaller than those of previous results, in which the dependency on $t$ was given by a function arising from the graph minor structure theorem of Robertson and Seymour. Our short proof combines the method by van den Heuvel and Wood for $K_t$ -minor-free graphs with some additional ideas, which make the extension to odd $K_t$ -minor-free graphs possible.

We prove two estimates for the expectation of the exponential of a complex function of a random permutation or subset. Using this theory, we find asymptotic expressions for the expected number of copies and induced copies of a given graph in a uniformly random graph with degree sequence(d1, …, dn) as n→ ∞. We also determine the expected number of spanning trees in this model. The range of degrees covered includes dj= λn + O(n1/2+ε) for some λ bounded away from 0 and 1.

It is proven that a conjecture of Tao (2010) holds true for log-concave random variables on the integers: For every $n \geq 1$, if $X_1,\ldots,X_n$ are i.i.d. integer-valued, log-concave random variables, then

\begin{equation*} H(X_1+\cdots +X_{n+1}) \geq H(X_1+\cdots +X_{n}) + \frac {1}{2}\log {\Bigl (\frac {n+1}{n}\Bigr )} - o(1) \end{equation*}

$H(X_1) \to \infty$

$H(X_1)$

$U_1,\ldots,U_n$

$(0,1)$

\begin{equation*} h(X_1+\cdots +X_n + U_1+\cdots +U_n) = H(X_1+\cdots +X_n) + o(1), \end{equation*}

$H(X_1) \to \infty$

$h$

$o(1)$

Let ${\mathbb{G}(n_1,n_2,m)}$ be a uniformly random m-edge subgraph of the complete bipartite graph ${K_{n_1,n_2}}$ with bipartition $(V_1, V_2)$ , where $n_i = |V_i|$ , $i=1,2$ . Given a real number $p \in [0,1]$ such that $d_1 \,{:\!=}\, pn_2$ and $d_2 \,{:\!=}\, pn_1$ are integers, let $\mathbb{R}(n_1,n_2,p)$ be a random subgraph of ${K_{n_1,n_2}}$ with every vertex $v \in V_i$ of degree $d_i$ , $i = 1, 2$ . In this paper we determine sufficient conditions on $n_1,n_2,p$ and m under which one can embed ${\mathbb{G}(n_1,n_2,m)}$ into $\mathbb{R}(n_1,n_2,p)$ and vice versa with probability tending to 1. In particular, in the balanced case $n_1=n_2$ , we show that if $p\gg\log n/n$ and $1 - p \gg \left(\log n/n \right)^{1/4}$ , then for some $m\sim pn^2$ , asymptotically almost surely one can embed ${\mathbb{G}(n_1,n_2,m)}$ into $\mathbb{R}(n_1,n_2,p)$ , while for $p\gg\left(\log^{3} n/n\right)^{1/4}$ and $1-p\gg\log n/n$ the opposite embedding holds. As an extension, we confirm the Kim–Vu Sandwich Conjecture for degrees growing faster than $(n \log n)^{3/4}$ .