math.CO

A graph $G$ admits an $H$-tiling if it contains a collection of vertex-disjoint copies of $H$. In this paper, we confirm a conjecture proposed by K\"{u}hn, Osthus, and Treglown by showing that for any given graph $H$, there exists a constant $C(H)$ such that the following holds. If $G$ is a sufficiently large $n$-vertex graph satisfying $d(x) + d(y) \geq 2\left(1 - 1/\chi_{\text{cr}}(H)\right)n$ for all nonadjacent vertices $x, y \in V(G)$, then $G$ contains an $H$-tiling covering all but at most $C(H)$ vertices. Here $\chi_{\text{cr}}(H)$ denotes the critical chromatic number of $H$.

A graph $G$ admits an $H$-tiling if it contains a collection of vertex-disjoint copies of $H$. In this paper, we confirm a conjecture proposed by K\"{u}hn, Osthus, and Treglown by showing that for any given graph $H$, there exists a constant $C(H)$ such that the following holds. If $G$ is a sufficiently large $n$-vertex graph satisfying $d(x) + d(y) \geq 2\left(1 - 1/\chi_{\text{cr}}(H)\right)n$ for all nonadjacent vertices $x, y \in V(G)$, then $G$ contains an $H$-tiling covering all but at most $C(H)$ vertices. Here $\chi_{\text{cr}}(H)$ denotes the critical chromatic number of $H$.

What is the maximum, over all 2-colourings of the edges of the $n$-dimensional hypercube $Q_n$, of the minimal number of times a path between a vertex $v$ and its antipode $\bar{v}$ changes colour? A conjecture of Norine, in a form due to Feder and Subi, states that this maximum should be 1. The previous best-known upper bound on the number of colour changes was $(\tfrac{5}{16} + o(1))n$ due to Kirchweger, Peitl, Subercaseaux, and Szeider. We improve this bound and answer a question of Leader and Long by finding a geodesic path with at most $(\tfrac{\pi}{2} + o(1))\sqrt{n}$ colour changes. In fact, we show that this is the expected number of colour changes for a uniformly random start vertex. This is optimal (up to the constant) when the start vertex is chosen uniformly at random.

What is the maximum, over all 2-colourings of the edges of the $n$-dimensional hypercube $Q_n$, of the minimal number of times a path between a vertex $v$ and its antipode $\bar{v}$ changes colour? A conjecture of Norine, in a form due to Feder and Subi, states that this maximum should be 1. The previous best-known upper bound on the number of colour changes was $(\tfrac{5}{16} + o(1))n$ due to Kirchweger, Peitl, Subercaseaux, and Szeider. We improve this bound and answer a question of Leader and Long by finding a geodesic path with at most $(\tfrac{\pi}{2} + o(1))\sqrt{n}$ colour changes. In fact, we show that this is the expected number of colour changes for a uniformly random start vertex. This is optimal (up to the constant) when the start vertex is chosen uniformly at random.

High dimensional expanders simultaneously satisfying spectral and combinatorial (coboundary) expansion have recently played a major role in breakthroughs in PCP and coding theory, but the only known construction of such complexes is extremely involved, requiring deep algebraic number theory. In this work, we give an extremely simple combinatorial construction of a sub-polynomial degree complex based on projections of the flags complex (subspace chains) that is (i) a local spectral expander, (ii) a coboundary expander, and (iii) a swap coboundary expander. As a corollary, we also give the first near-linear size combinatorial hypergraphs with good agreement tests in the '1%' regime, and a simple PCP construction with near-linear size.

We prove measurable analogues of Whitney's classical theorems on weak isomorphisms of finite graphs. In the setting of locally finite graphings, we introduce a notion of weak isomorphism as an edge-measure-preserving Borel bijection that preserves cycles and hyperfinite subgraphs, modulo null sets. We first show a rigidity theorem, proving that for weakly 3-connected infinitely-ended graphings, every weak isomorphism is induced by an isomorphism of graphings. To our knowledge, this gives the first general sufficient condition in measurable combinatorics for the existence of an isomorphism between two given graphings. Next, we give a full measurable version of Whitney's theorem, showing that every weak isomorphism between graphings can be implemented by countably many measurable Whitney operations, which we introduce in this setting. The proofs require new measurable-combinatorial tools, including a careful analysis of infinitely-ended subforests. This work further develops the limit theory of matroids recently initiated by Lov\'asz.

Voloshyn introduced rational Weyl group elements in connection with rational normal forms on complex reductive groups and conjectured that, in type $D_r$ with $r$ odd, their number is $2^r-1$. We prove a stronger structural statement. For $r\geq 5$ odd, the rational Weyl group elements in $W(D_r)$ are exactly the longest element $w_0$ together with two explicitly described signed cyclic elements $c_I$ and $d_I$ for every non-empty subset $I\subseteq\{1,\ldots,r-1\}$. Consequently the rationality graph $\Gamma(D_r)$ is two explicitly labelled Boolean-type halves glued at $w_0$, its number of vertices is $2^r-1$, and its only vertices of valency one are $c_{\{1\}}$ and $d_{\{1\}}$. The proof combines an acyclic two-level description of the rationality graphs $\Gamma(c_I)$ with a rigidity argument for all one-step rational descents from $w_0$. The latter uses Voloshyn's descent lemma, while all type-$D$ exclusions are given by explicit loops or two-cycles in the root-poset rationality graph.

In this paper, we study Thrall's problem for the higher Lie modules $L_\lambda$. Our main result provides a tableau-theoretic description of the Schur expansion of the character of $L_\lambda$ when $\lambda$ has two rows, thereby solving Thrall's problem in this case. This formula is expressed in terms of standard Young tableaux with major index congruence conditions and a spin-parity condition defined through bijections with Yamanouchi domino tableaux. We also obtain tableau formulas for hook shapes and partitions with distinct parts, and these results extend to all partitions in which each part greater than $2$ occurs at most twice.

For $k\ge 3$, the $(k-2)$-uniform Tur\'an density $\pi_{k-2}(F)$ of a $k$-graph $F$ is the supremum of $d$ for which there are arbitrarily large $F$-free $k$-graphs that are uniformly $d$-dense with respect to the $k$-vertex cliques of every $(k-2)$-graph on the same vertex set. We develop a \emph{palette framework} for this density. For every family $\mathcal F$ of $k$-graphs, we prove that $\pi_{k-2}(\mathcal F)$ equals the corresponding palette Tur\'an density. We further establish palette classification tools for the existence of $k$-graphs satisfying prescribed palette colorability constraints. Those together allow us to reduce exact density computations to a palette-homomorphism framework without relying on the hypergraph regularity method. As applications, for all $k\ge 3$ and $r\ge 2$, we establish the following values \[ \frac{r-1}{r},\quad \frac{(r-1)^2}{r^2},\quad \frac{r-1}{2r},\quad \frac{(k-1)^k}{k^k},\quad \frac{4(k-2)^{k-2}}{k^k},\quad \frac{4(k-2)^{k-2}}{3k^k} \] as $(k-2)$-uniform Tur\'an densities of single $k$-graphs. Finally, for every $k\ge3$, we show that there exist $k$-graphs $F_1,F_2$ such that \[ \pi_{k-2}(\{F_1,F_2\})< \min\{\pi_{k-2}(F_1),\pi_{k-2}(F_2)\}, \] which provides the first examples of \emph{non-principal} families for this density.

Let $k\geq 2$. We show that, for a sufficiently small $\varepsilon>0$, any sufficiently large $n$-vertex Hamiltonian graph of minimum degree at least $n^{1-\varepsilon}$ contains a $2$-factor consisting of exactly $k$ cycles. This is the first minimum-degree condition which is polynomially smaller than linear. Our methods yield an analogous result when the host graph is not required to contain a Hamilton cycle, but only a $2$-factor consisting of at most $k$ cycles; this answers a question of Buci\'c, Jahn, Pokrovskiy and Sudakov.

Let $A\subset \mathbb{F}_p$ with density 1/2. We call a set $A$ almost affine invariant under an affine transformation $\phi(x)=ax+b$ if \[|A \triangle \phi(A)| =o(p).\] We determine that, the threshold value of $K$ such that $A$ is almost affine invariant simultaneously under all $\phi(x)$ with $|a|, |b|\le K$ and $a\neq 0$, is $K=o(\log p)$. This solves Ben Green's Open Problem 90.