Papers

In the literature, several graph matrices based on vertex degrees have been introduced, and the study of their spectral properties has attracted considerable attention in recent years. Motivated by these developments, in this paper, we investigate the spectral radius of the weighted adjacency matrix $A_f(G)$, where the function $f$ satisfies property $P^{*}$. More precisely, we characterize the graphs that attain the maximum spectral radius of $A_f(G)$ among graphs with a vertex cut set of prescribed order, graphs with exactly $s$ cut edges, and graphs with given vertex connectivity and independence number. Our results further develop the unified framework for studying extremal spectral properties of degree-based weighted adjacency matrices and extend this framework to several classes of graphs with prescribed structural parameters.

For type $A$ braid varieties, including Richardson varieties and positroid varieties, we prove that the standard torus has a dense orbit exactly when the associated link is smoothly slice. More generally, we relate the smooth slice genus to the codimension of a generic standard-torus orbit. For knots, this codimension equals twice the slice genus. We also characterize algebraic tori among open affine Richardson varieties and positroid patches by 2-crown avoidance in their Bruhat intervals. Finally, positroid links have equal Seifert and slice genera, so a positroid link is smoothly slice exactly when it is an unlink.

A weak form of the Hellinger conjecture of Anantharam, Bogdanov, Chakrabarti, Jayram, and Nair for the binary symmetric channel is proved: dictator functions maximize Hellinger $\Phi$-entropy among all Boolean functions of the input and all one-bit statistics of the output of a noisy channel. The technical heart of the matter is an explicit inequality in three real parameters, which is proved using explicit polynomial approximations and computer-assisted positivity checks. The results are also formally verified in Lean 4.

Kahn proved that, among bipartite $d$-regular graphs on $n$ vertices, the number of independent sets is maximized by a disjoint union of copies of $K_{d,d}$. Zhao later extended this result to all $d$-regular graphs. We prove a robust version of this theorem in which independent sets are replaced by sets spanning few internal edges. If $G$ is $d$-regular on $n$ vertices, then the number of subsets spanning at most $\gamma dn$ edges is at most $$ 2^{n/2}\exp\left\{ O\bigl(\gamma\log(e/\gamma)n\bigr) + O\bigl(n/d\bigr) \right\}. $$ Both correction terms are sharp up to absolute constants: the $\gamma\log(1/\gamma)n$ term is necessary when $d$ is sufficiently large in terms of $\gamma$, while the $n/d$ term is already necessary for independent sets. Our result answers a question of Seth.

Recently, Heath, McCourt, Parker, Schwieder, and Zerbib initiated the systematic study of the $r$-Kneser Ramsey number $R_r^{KG}(s,t)$ and investigated related Ramsey-type problems. A central motivation for their work comes from a question of Holmsen, Hrusak, and Roldán-Pensado, who asked whether, for $n=2k-1$ and sufficiently large $k$, every red/blue edge-coloring of the complete graph on the vertex set $V = \binom{[n]}{k}$ necessarily contains a monochromatic triangle $ABC$ with $A,B,C \in V$ and $A \cap B \cap C = \emptyset$. Heath, McCourt, Parker, Schwieder, and Zerbib established that this conclusion holds when $n \ge \frac{7k}{3}$ and $k\ge 12$. We make substantial progress toward the problem of Holmsen, Hrusak, and Roldán-Pensado by proving that the conclusion already holds for every $k\ge 2$ whenever $n\ge 2k+1$. In addition, we obtain improved lower bounds for $R_r^{KG}(s,t)$ when $s$ and $t$ are fixed and $r$ is sufficiently large.

We study the Ooms multiplicities of Frobenius maximal parabolics $W(a,b)$ of type~$A$. For $a=mb+r$ with $1\le r<b$, the Euclidean algorithm relates their potential histograms to those of the smaller algebra $W(r,b-r)$. We prove strict unimodality for every positive coprime pair: the multiplicities increase strictly to the equal central values at eigenvalues $0$ and $1$, then decrease strictly. This strengthens the recent maximal-parabolic unimodality theorem of Giaquinto, Irving, Lauve, and Mastnak. We also prove log-concavity for the unbounded families $W(mb\pm t,b)$, where $t\in\{1,2,3\}$, $b>t$, $\gcd(b,t)=1$, and $m\ge1$. These results cover every Frobenius case with smaller block at most $8$, and also smaller block $10$. For each fixed residue class, we then prove that log-concavity of the whole family is determined by finitely many initial spectra. The finite cutoff is obtained symbolically. Exact integer verification of the resulting finite lists proves strict internal log-concavity whenever the smaller block is at most $128$, with no bound on the larger block. The unrestricted log-concavity conjecture is not proved here.

We prove a sparse version of the four-colour theorem of Brandt and Thomassé, answering a question of Allen, Böttcher, Kohayakawa and Roberts. For every fixed $0<\gamma\le1/10$ and every $p=p(n)\in(0,1]$, asymptotically almost surely every spanning triangle-free $H\subseteq G(n,p)$ with $\delta(H)\ge(1/3+\gamma)pn$ can be made four-partite by deleting at most $\min\{C_\gamma n/p,(1/8+\gamma)pn^2\}$ edges. In fact, deleting at most $C_\gamma n/p$ edges yields a graph that admits a homomorphism to an Andrásfai or Vega graph with certificate complexity at most $1/(3\gamma)$. Together with matching lower bounds from random blow-ups, this structural result determines, uniformly in $p$, the minimum-degree thresholds for $q$-partiteness with $O(n/p)$ edge deletions: $2/5$ for $q=2$, $10/29$ for $q=3$, and $1/3$ for every fixed $q\ge4$. For every fixed $q\ge2$ and $\log n/n\ll p\ll n^{-1/2}$, asymptotically almost surely $G(n,p)$ contains a spanning triangle-free subgraph with minimum degree $(1-o(1))pn$ that requires $(1/(2q)+o(1))pn^2$ edge deletions to become $q$-partite, showing that the coefficient $1/(2q)$ cannot be improved even under this stronger degree condition.

Motzkin paths of length $n$ and standard Young tableaux (SYT) with $n$ cells and at most three rows are both counted by the Motzkin numbers, and many bijections between them are known. The Riordan numbers count the subfamilies of Riordan paths (Motzkin paths with no horizontal step on the $x$-axis) and of tableaux whose three row lengths have the same parity, but none of the known bijections restricts to these subfamilies. We introduce the set of $321$-avoiding permutations in which every left-to-right maximum is either a descent or a fixed point. This family is counted by the Motzkin numbers, and its fixed-point-free elements are the “Riordan permutations” of Callan. We give a bijection from Motzkin paths to these permutations under which Riordan paths correspond to Riordan permutations. We then give a bijection from these permutations to SYT of height at most three, obtained from Robinson–Schensted insertion followed by a parity correction, under which Riordan permutations correspond to tableaux with rows of equal parity and the number of left-to-right maxima becomes a simple tableau statistic. Via Dyck paths, we connect these objects to further families counted by the Riordan numbers, including derangements of genus zero and SYT of shape $(k,k,1^{n-2k})$.

A conjecture of Lewis asserts that two reflection factorizations of the same element in a finite Coxeter group $W$ belong to the same Hurwitz orbit if and only if they generate the same subgroup $H$ of $W$ and have the same multiset of $H$-conjugacy classes. We prove this conjecture for every finite Coxeter group all of whose irreducible components are of type $A$, $B$ or $D$. Furthermore we prove a reduction, which reduces the conjecture to a finite problem for the exceptional types.

An eigenvalue of a signed graph is called main if there exists a corresponding eigenvector non-orthogonal to the all-ones vector. An important result of O'Rourke and Touri (2016) states that almost all (unsigned) graphs have all main eigenvalues. Akbari, França, Ghasemian, Javarsineh, and de Lima (2021) considered main eigenvalues of signed graphs and conjectured that for any unsigned connected graph $G \notin\{ K_2, K_4 - e\}$, there is a switching $\mathbf{s}$ such that all eigenvalues of the signed graph $G^{\mathbf{s}}$ are main. We prove two incomparable asymptotic versions of this conjecture. We show that for any graph $G$ of order $n$, there exists a switching $\mathbf{s}\in\{\pm1\}^n$ such that $G^{\mathbf{s}}$ has $n - O\!\left(\frac{n}{(\log n)^{1/4}}\right)$ main eigenvalues counted with multiplicity. Using a similar proof strategy, we also show that if $G$ has $d$ distinct eigenvalues, then there exists a switching $\mathbf{s}\in\{\pm1\}^n$ such that $G^{\mathbf{s}}$ has $d - O\!\left(\frac{d}{(\log d)^{1/4}}\right)$ main eigenvalues.

The slice rank method gives exponential bounds for sets with no three-term arithmetic progression in finite vector spaces of odd characteristic and for three-sunflower-free families of subsets of a fixed ground set. We show that for $k\ge4$, every tensor that is nonzero exactly on the $k$-term arithmetic progression relation or the $k$-sunflower relation has maximal slice rank over every coefficient field. When the support is prescribed only on pairwise distinct inputs, we obtain comparable lower bounds, which likewise rule out exponential savings.

Let $k$ be a field of characteristic $p\ge0$. We prove that $m$ points and $n$ lines in $k^2$ determine at most $3(mn)^{2/3}+m+n+2mn/p$ incidences, the last term being omitted in characteristic zero. Over the prime field $\mathbb{F}_p$ the coefficient of $mn/p$ can be replaced by $1$. The proof uses the polynomial method, and for $m=n$ the bound is sharp up to an absolute constant over prime fields. As applications, over prime fields in which $-1$ is not a square we obtain the $L^2\to L^r$ extension estimate for the paraboloid in $\mathbb{F}_p^3$ for $r>10/3$. Over every odd prime field, we show that a two-source extractor construction of Bourgain has exponentially small error at every min-entropy rate greater than $1/3$. We also improve sum-product estimates for small sets in positive characteristic and obtain projection and Furstenberg estimates over prime fields. The incidence inequalities with exact constants have been formalized in Lean.

We find a new coupling between the Airy sheet $\mathcal{S}$ and the Airy line ensemble $\{ \mathcal{A}_n \}_{n \in \mathbb{N}}$, which we call the down-the-middle isometry. In this coupling, the Airy sheet is encoded by last passage values that start at $\mathcal{A}_k(0)$ for some $k \in \mathbb{N}$ and end on the top line $\mathcal{A}_1$. Using this coupling, we give a new construction of the (extended) Airy sheet as a scaling limit of Brownian last passage percolation and study coalescence of geodesics in the directed landscape. This coupling extends to discrete polymers and last passage percolation models, as well as to the KPZ line ensemble and KPZ sheet.

The "$S_{n,n}$ conjecture" asserts that there does not exist a simple graph on $n$ vertices with Laplacian spectrum $\{0,1,2,\ldots,n-1\}$ for any integer $n \geq 2$. This conjecture has already been proved when $2 \leq n \leq 15$ and when $n \geq 6,649,688,933$. We prove all remaining cases and thus establish that the conjecture is true.

We study representations for relation algebras corresponding to certain edge colourings of complete graphs. Previously suitable colourings were obtained for the number of colours $n$ up to $2000$, with two exceptions: $n = 8$ and $n = 13$. Using a method that we have called the FBF (Fusion Beautiful Fusions) method, we find colourings for $8$ and $13$ colours. Our method is a new guess-and-check approach that we describe as an adaptation of Comer's finite-field method. Using FBF we construct novel colourings that are non-isomorphic to existing published colourings for 5, 6, 7, 9, 10, 11 and 12 colours.

A $\textit{magic-lined hypercube}$ (or, simply, $\textit{magic hypercube}$) of order $k$ and dimension $n$ is an arrangement of the numbers $1,\dots,k^n$ in a $k\times\cdots\times k$ ($n$-fold) grid such that every line of $k$ numbers parallel to a coordinate axis has the same magic sum. While such hypercubes exist for every order $k\ge 3$ and every dimension $n$, no magic-lined hypercube of order $2$ exists in any dimension $n\ge 2$. For hypercubes of order $2$, we thus relax the magic condition from lines to two-dimensional faces or planes. We call an arrangement of the numbers $1,\dots,2^n$ in a $2\times\cdots\times2$ ($n$-fold) grid magic-faced if every $2\times2$ face has the same magic sum. We prove that a magic-faced hypercube of order $2$ exists in every dimension $n\ge0$, and that it is unique up to a certain natural set of transformations of size $2^n(n+1)!$ when $n$ is even and $2^n n\cdot n!$ when $n$ is odd. As an application, we recover and generalize the classical $4\times4$ Khajuraho magic square, answer a question of Coxeter on the group acting on the $384$ “most-perfect" $4\times4$ magic squares, and extend the picture to higher dimensions. In particular, we prove that, in dimension $n$, these most-perfect objects form a single orbit under a certain natural action of the Weyl group $W(B_{2n})$.

For every $n\ge2$, we construct $4n-2$ nondegenerate Gaussian measures on $\mathbb{R}^{6n-3}$ that cannot be simultaneously equipartitioned by two affine hyperplanes. This disproves the Ramos conjecture for two hyperplanes. Combined with known upper bounds, the construction shows that $3\cdot2^{s-1}-2$ is the least dimension guaranteeing a common two-hyperplane equipartition of $2^s-2$ absolutely continuous probability measures, for every $s\ge3$. We characterize the Gaussian equipartition threshold in terms of the least number of positive definite quadratic measurements needed for phase retrieval. Modified complex polynomial multiplication gives $2r-2$ positive definite measurements in every even dimension $r\ge4$. This number is optimal when $r=2^k+2$, $k\ge1$.

Aldous and Fill (2002) conjectured the asymptotic maximum relaxation time of a random walk on a connected regular graph. Since the relaxation time of a $d$-regular graph $G$ is $d/\mu(G)$, where $\mu(G)$ denotes its algebraic connectivity, this conjecture is closely related to the problem of minimizing algebraic connectivity among regular graphs. Guiduli and Mohar (1996) conjectured that, for every fixed minimum degree $\delta=d\ge3$ and all sufficiently large orders, graphs with minimum algebraic connectivity are path-like and, apart from bounded portions near their two ends, have a prescribed block structure. Abdi and Ghorbani (2024) proposed an analogous structural conjecture for $d$-regular graphs with minimum algebraic connectivity and fixed degree $d\ge3$. In Part~I, we proved the Aldous–Fill conjecture, the Guiduli–Mohar conjecture, and for odd degrees, the Abdi Ghorbani conjecture. In this paper, we settle the remaining even-degree case, thereby completing the structural characterization of regular graphs with minimum algebraic connectivity. We also prove that, for every fixed even $d\ge4$, the minimum algebraic connectivity at order $n$ is $2(d-2)\pi^2/n^2+O_d(n^{-3})$, and that every minimizing graph has diameter $3n/(d+1)+O_d(1)$. For every fixed even $d\ge6$, $d$-regular graphs whose algebraic connectivity is asymptotically minimum have asymptotically maximum diameter. Finally, we obtain a sharp normalized-gap bound for all even regular degrees, including degrees that grow with $n$.

Aldous and Fill (2002) conjectured that the maximum relaxation time of a random walk on a connected regular graph with $n$ vertices is bounded above by $(1+o(1))\frac{3n^2}{2\pi^2}$, with asymptotic equality for even $n$. Since the relaxation time of a $d$-regular graph $G$ is $d/\mu(G)$, where $\mu(G)$ denotes its algebraic connectivity, this conjecture is closely related to the problem of minimizing algebraic connectivity among regular graphs. Guiduli and Mohar (1996) conjectured that, for every fixed minimum degree $\delta=d\ge 3$ and all sufficiently large orders, graphs with minimum algebraic connectivity are path-like and, apart from bounded portions near their two ends, have a prescribed block structure. For fixed odd degree $d\ge 3$, Abdi and Ghorbani (2004) conjectured that $d$-regular graphs with minimum algebraic connectivity have the same structure. We prove the Aldous–Fill conjecture and the Guiduli–Mohar conjecture, as well as the corresponding conjecture for $d$-regular graphs of fixed odd degree. Finally, we prove that, for every fixed odd degree $d\ge 3$, $d$-regular graphs, as well as graphs of fixed minimum degree $d\ge 3$, whose algebraic connectivity is asymptotically minimum have asymptotically maximum diameter. This establishes the corresponding cases of another conjecture of Abdi and Ghorbani.

For every fixed $\varepsilon\in(0,1/2)$, we prove that every spanning subgraph $H$ of an $n$-vertex $(p,\beta)$-bijumbled graph satisfying $\delta(H)\geq(1/2+\varepsilon)pn$ contains a rainbow Hamilton cycle under every globally $\mu pn$-bounded colouring, provided $\beta\leq cpn$ and $pn\geq M$ both hold. The same assertion holds under the relative condition $\deg_H(v)\geq(1/2+\varepsilon)\deg_G(v)$ for every vertex $v$, provided $\delta(G)\geq(1-\varepsilon/4)pn$ holds. Under either degree condition, there are at least $(apn)^n$ such cycles. Here, $c,\mu,a,M>0$ depend only on $\varepsilon$; in particular, $pn$ may be a sufficiently large constant. If $pn\geq D\log n$, then, upon fixing a coloured $H$, retaining each edge independently with probability $D\log n/(pn)$ preserves rainbow Hamiltonicity asymptotically almost surely. The logarithmic degree requirement is needed only for this percolation conclusion. The existence theorem answers a problem of Coulson, Keevash, Perarnau and Yepremyan for random graphs and extends it to deterministic pseudorandom hosts. In fact, all three conclusions hold with rainbowness replaced by avoidance of prescribed pairs of edges; each edge having at most $\mu pn$ conflicting partners. We construct an $O(1/(pn))$-spread probability measure on conflict-free Hamilton cycles; this then yields the enumeration and percolation results.

A length-$n$ binary $k$-deletion code is a set of binary strings such that if we delete any $k$ bits of a string, leaving a length-$(n-k)$ binary string, we can uniquely recover the codeword. In this paper, we consider $t$-list decodable deletion codes, where after $k$ bits of a codeword are deleted, we can identify a list of size at most $t$ such that the original codeword lies in the list. We prove a lower bound of $\Omega_k(2^n t\log^{1/t}n/n^{k+k/t})$ on the optimal size of a $t$-list decodable $k$-deletion code, giving a $\sqrt{\log n}$ improvement over the previously best known bounds for $2$-list decodable $2$-deletion codes [GH21] and providing the first nontrivial lower bound when $t>2$ or $k>2$. Our bound holds for all $t\leq n^k$, showing that $t=\Omega(\log n)-$list decodable deletion codes have optimal size $\Theta_k(2^n t/n^k)$, asymptotically matching the known upper bound. We also prove upper bounds on the number of common subsequences and common supersequences of a given length for any two binary strings.

In sparse random matrices, spectral outliers (eigenvalues and singular values located away from the bulk) emerge due to degree fluctuations: high degrees inflate the operator norm, while low column degrees reduce the least singular value. As proved by Feige and Ofek (2005) and Le, Levina, and Vershynin (2017), degree regularization enforces concentration at the expected norm scale. However, precise bounds incorporating the cutoffs remain unexplored and challenging since regularization introduces dependencies among entries. For the first time in the literature, we provide variance- and cutoff-dependent bounds for extreme singular values and eigenvalues of regularized inhomogeneous random matrices. In the absence of regularization, our lower bound for the least singular value matches the same leading constant obtained by Brailovskaya and van Handel (2024). Moreover, our error term vanishes under the milder condition $d/\log N\to\infty$, as opposed to their stronger requirement $d/(\log N)^4\to\infty$. A key ingredient is to extend spectral radius bounds for nonbacktracking matrices to the dependent setting. We build on approaches for independent cases established by Benaych-Georges, Bordenave, and Knowles (2020), as well as Dumitriu and Zhu (2024), and carefully handle edges traversed only once. Our proof framework separates deterministic spectral comparisons from probabilistic estimates: once Loewner inequalities and columnwise variance controls are established, the remaining probabilistic analysis boils down to verifying the graph moment conditions formulated in this paper. We hope this framework can be extended to handle general random matrices with more complex dependencies.

In this paper, we prove an Erdős-Ko-Rado characterisation of maximum intersecting families of blocks in Steiner $2$-designs arising from Desarguesian maximal arcs. This answers a recent question of Goryainov and Konstantinova, and implies that, among the known Steiner $2$-designs, only finitely many admit a maximum intersecting family that is neither canonical nor associated with a subdesign. We also perform a computational study of $2$-$(120,8,1)$ designs and find strong counterexamples to a problem of Godsil and Meagher. Finally, we give a parametric generalisation of $2$-$(66,6,1)$ designs with tight dual arcs as non-canonical maximum intersecting families.

We prove that every finite translational tile of $\mathbb Z^d$ of cardinality $2q$, where $q$ is an odd prime, or of cardinality nine admits a fully periodic tiling complement. The result holds in every dimension, regardless of the rank of the subgroup generated by the differences of points of the tile. The proofs combine coprime dilation, vanishing sums of roots of unity, and periodic two-colorings. After translating the tile, both arguments restrict to its intrinsic lattice, and every periodic complement constructed there extends to the ambient lattice. For cardinality $2q$, spectral filtering in the intrinsic lattice yields either a lattice complement or a periodic twofold covering compatible with a tiling complement. This compatibility allows the covering to be split by a periodic proper two-coloring. For nine points, intrinsic ranks $1$ and $2$ are treated separately; in higher intrinsic rank, the algebraic reduction in the intrinsic lattice yields either a lattice complement or spectral support on finitely many rational affine circles. These results also give a decision algorithm for tileability in both cardinality families. The circle-supported alternative is resolved by a conditional-density dichotomy and a periodic replacement argument for the exceptional half-density components.

The Ramsey number $r_k(s,n)$ is the smallest integer $N$ such that every $N$-vertex $k$-graph contains either a copy of $K_s^{(k)}$ or an independent set of size $n$. Erdős and Hajnal conjectured that for every fixed $s>k\ge 4$, one has $r_k(s,n)\ge \operatorname{twr}_{k-1}(\Omega(n))$. This conjecture was independently verified by Mubayi and Suk, and by Conlon, Fox and Sudakov, for $k\ge4$ and $s\ge k+3$. In this paper, we prove that $r_4(6,n)\ge 2^{2^{cn}}$ for some absolute constant $c>0$, improving upon our previous bound. Consequently, we confirm the Erdős–Hajnal conjecture for $r_k(k+2,n)$ for all fixed $k\ge4$.

We exhibit simple, rotationally symmetric Venn diagrams with 17 curves, with 19 curves and with 23 curves: $n$ Jordan curves carried to one another by rotation through $2\pi/n$, with every one of the $2^n$ regions present and connected and, since the diagrams are simple, every crossing on exactly two curves. Symmetric Venn diagrams exist for every prime number of curves (Griggs, Killian and Savage, 2004), but those diagrams have many curves through a point; simple ones were known only up to 13 curves (Mamakani and Ruskey, 2014). Four 17-curve, twelve 19-curve and six 23-curve diagrams were found by a Metropolis walk on rotation-invariant quadrangulations of the sphere in which regions may temporarily be duplicated, started from the Griggs-Killian-Savage diagram with its multiple crossings resolved. At 23 curves the walk was held for two weeks by duplicated regions near the poles; the two lineages that finished were the first whose $E=92$ states had none. Every diagram is given by a machine-checkable certificate; one certificate each of the 17-, 19- and 23-curve sizes has been verified by a formal proof in Lean 4. All of the diagrams are non-monotone, which is why the crossing-sequence searches that found the 11- and 13-curve diagrams could not have found them.

A central theme in extremal graph theory is to understand the relationship between the density of a graph and the richness of its cycle length spectrum, which is the set of distinct cycle lengths occurring in the graph. In 1966, Erdős and Hajnal suggested studying $s(G):=\sum_{\ell\in{C}(G)}1/\ell$ as a measure of the richness of the cycle length spectrum ${C}(G)$ of a graph $G$. Through a series of increasingly strong conjectures, Erdős suggested that the complete bipartite graphs minimise $s(G)$ among all graphs $G$ with the same average degree. The sharpest such conjecture, from 1981, states that the graph $K_{k, n-k}$ minimises $s(G)$ among all $n$-vertex graphs with at least $k(n-k)$ edges (where $k\leq n/2$). We prove this conjecture for all sufficiently large $k$, by showing the stronger statement that any $n$-vertex graph $G$ with $e(G)>(k-1)(n-k+1)$ and $n\geq 2k$ satisfies $s(G)\geq\sum_{\ell=2}^{k}1/(2\ell)$. Moreover, we show that the complete bipartite graph $K_{k,n-k}$ is the unique graph with at least $k(n-k)$ edges that achieves equality here.

In this paper we study whether there is a global to local principle for the homology of order complexes of finite lattices. We explore whether the non-vanishing of the homology of a lattice in degree $a+b-2$ forces the existence of a pair of lattice-complements whose open intervals below have non-vanishing homology in degrees $a$ and $b$ respectively. We consider the same question also in the language of multigraded free resolutions. We provide positive evidence for the existence of such pairs and give counterexamples to strengthenings of the question.

Inspired by the static problem $(\alpha,\beta)$-Dominating Set, we propose a general temporal domination problem, called $(\alpha,\beta)$-Temporal Dominating Set ($(\alpha,\beta)$-TDS). We show that this problem encompasses Temporal Dominating Set, and additionally provides first temporal extensions of problems such as $k$-Dominating Set and $\alpha$-Dominating Set. In this paper, we study the parameterised complexity of $(\alpha,\beta)$-TDS with respect to temporal neighbourhood diversity (TND), temporal modular-width (TMW), and temporal cliquewidth (TCW). We obtain fixed parameter tractability results for all values of $\alpha$ and $\beta$ with respect to TND; W[1]-hardness with respect to TMW and TCW whenever $\beta$ is in the problem input, or whenever $\alpha\in (0,1)$ and $\beta$ is a fixed constant; and para-NP-hardness with respect to TCW when $\alpha = 0$ and $\beta = 1$, or $\alpha = 1$ and $\beta = 0$.

We prove a quantitative palette-transference principle for rainbow spanning configurations in uniformly edge-coloured pseudorandom graphs. The input to our transference principle is an embedding result of a spanning configuration in an appropriately bijumbled graph $H$ with sufficiently large minimum degree. The output of our transference principle is the asymptotically almost sure existence of a rainbow copy of the same configuration in a uniformly edge-coloured graph $G$ whose bijumbledness and minimum are comparable and sometimes coincide with those of $H$. We then apply our transference principle in order to asymptotically almost surely obtain $K_k$-factors, including perfect matchings, Hamilton cycles, and a prescribed bounded-degree spanning tree in bijumbled graphs with appropriate parameters. In all of our results, the palette size exceeds the size of the target configuration by $\varepsilon n$, where $\varepsilon > 0$ is arbitrarily small yet fixed, and $n$ is the order of the configuration.