Papers

We give a complete determination of the exact optimal worst-case repair bandwidth and repair I/O for linear exact repair of $(n,n-2,2)$ MDS array codes over every finite field $\mathbb{F}_q$ and for every admissible code length $3\le n\le q^2+1$. For repair bandwidth, we prove that the optimum is governed, up to a short explicit list of small exceptional cases, by the maximum of the sharpened $n$-only lower bound $\lceil(5n-8)/4\rceil$ and the projective counting, equivalently incidence-multiplicity, bound $2n-q-3$. For repair I/O, we obtain the analogous exact formula with $\lceil(4n-6)/3\rceil$ in place of $\lceil(5n-8)/4\rceil$, with the single special value at $n=4$. Thus, we completely resolve the first non-trivial redundancy and sub-packetization regime $(r,\ell)=(2,2)$ for both repair bandwidth and repair I/O.

Given a graph $G=(V,E)$, a vertex $u \in V$ ve-dominates all edges incident to any vertex of $N_G[u]$. A set $S \subseteq V$ is a ve-dominating set if for all edges $e\in E$, there exists a vertex $u\in S$ such that $u$ ve-dominates $e$. The minimum cardinality among all ve-dominating sets is known as the vertex-edge domination number (or simply ve-domination number) and denoted by $\gamma_{ve}(G)$. Finding a minimum ve-dominating set was proved to be NP-complete. Restricted to trees, the problem admits a linear-time algorithm. Treewidth is a commonly used parameter for solving NP-hard problems. In this paper, we present a polynomial-time algorithm for finding a minimum ve-dominating set on graphs with bounded treewidth. Moreover, we show that the treewidth of a planar graph $G$ with ve-domination number $\gamma_{ve}(G)$ is $O(\sqrt{\gamma_{ve}(G)})$ and present an $O(c^{\sqrt{k}}|V(G)|)$-time algorithm for the $k$-ve-domination problem on planar graphs.

In this paper, we prove a conjecture of Andrews and Bachraoui relating a generating function arising from two-color partitions (with odd smallest part and restrictions on the even parts) to a Hecke-type double sum. Our proof is based on Zwegers' theory of indefinite theta functions together with modular transformation properties of mock theta functions.

Motivated by Stanley's “Schubert shenanigans” paper, commendable attempts have been made to understand the principal specializations of Schubert or Grothendieck polynomials. In this paper, we prove that when a permutation $w$ does not contain the $1423$ pattern, the principal specialization of the corresponding $\beta$-Grothendieck polynomial can be expressed nonnegatively in terms of the occurrences of patterns in $w$. Using an inverse conservation principle, we further obtain the nonnegativity expansion for permutations avoiding the $1342$ pattern. Our results partially resolve conjectures raised respectively by Gao (independently observed by Gaetz), Meśzáros–Tanjaya, and Dennin. The proofs are achieved based upon a reduction algorithm performing on the classic pipe dream model of $\beta$-Grothendieck polynomials.

The sequence A176677 in the Encyclopedia of Integer Sequences enumerates Motzkin paths where two types of horizontal steps may occur, but only on odd indexed levels. We show how to perform the enumeration, also dealing with partial such Motzkin paths leading to a particular level or to any level (open paths). The method is the kernel method where functional equations are manipulated in a suitable way. The coefficients of sequence A176677 satisfy a holonomic recursion that was recently discussed on the arxiv. We show how this can be established in an (almost) automatic fashion. Eventually we switch the roles of `odd' and `even'. One could also allow more versions of horizontal steps but we leave this to the interested readers.

A "dominating $K_t$-model" in a graph $G$ is a sequence $(T_1,\dots,T_t)$ of pairwise vertex-disjoint connected subgraphs of $G$, such that whenever $1\leq i<j\leq t$ every vertex in $T_j$ has a neighbour in $T_i$. Replacing "every vertex in $T_j$" by "some vertex in $T_j$" retrieves the standard definition of $K_t$-model, which is equivalent to a $K_t$-minor in $G$. We prove that every graph with no dominating $K_5$-model is $4$-colourable. This generalises and is significantly stronger than the 4-colour theorem for planar graphs or for graphs with no $K_5$-minor. It also makes progress towards Hajós' conjecture on $K_5$-subdivisions in $5$-chromatic graphs.

Let $\Omega \subset \mathbb{R}^2$ be a bounded convex domain. Steinerberger (2026) introduced the Buffon discrepancy problem: given length $L$, construct a one-dimensional set $S\subset\Omega$ such that the number of intersections of $S$ with a line $\ell$ approximates the Crofton-normalized chord length $$ \frac{2L}{\pi|\Omega|}\cdot\mathcal{H}^1(\ell\cap\Omega).$$ Steinerberger proved a universal upper bound of order $L^{1/3}$ using a Steinhaus longimeter construction, and showed that the disk admits bounded discrepancy. We prove that a randomly shifted Steinhaus construction improves the order of the universal upper bound to $L^{1/5}(\log L)^{2/5}$.

We study the $C$- and $G$-patterns associated with rank $3$ skew-symmetrizable matrices of $B$-invariant type, including the Markov quiver. Motivated by the self-contained simple mutations in Markov-type cluster algebras, we prove that large classes of subpatterns of modified $c$- and $g$-vectors are linearly isomorphic, yielding a fractal structure of the corresponding $G$-fan. We further derive explicit recursive formulas for all modified $c$- and $g$-vectors in terms of integer pairs satisfying a recursion analogous to the Calkin-Wilf tree, which leads to a parameterization by coprime integers. As an application, we describe all connected components of the complement of the support of the $G$-fan, and show that they are generated recursively by three kinds of linear maps.

Menger's theorem is an important building block of numerous results in the study of graph structure. We consider a variant in terms of coarse geometry. We say that a set of graphs has the weak coarse Menger property if there exist functions $f$ and $g$ such that for any graph $G$ in this set, subsets $X$ and $Y$ of vertices of $G$, and positive integers $k$ and $r$, either there exist $k$ paths between $X$ and $Y$ pairwise at distance at least $r$, or there exists a union of at most $f(k,r)$ balls of radius at most $g(k,r)$ intersecting all paths between $X$ and $Y$. Nguyen, Scott and Seymour proved that the set of all graphs does not have the weak coarse Menger property and asked whether every proper minor-closed family of finite graphs has it. In this paper, we provide a positive answer to this question in a stronger form: it is true for the set of locally finite graphs with an excluded finite minor, and the functions $f$ and $g$ can be chosen so that $f$ only depends on the number $k$ of the paths in the packing and the function $g$ is a linear function of the distance threshold $r$ and is independent of $k$, which is optimal up to a constant factor. Our result extends to every length space quasi-isometric to a locally finite graph or metric graph with an excluded finite minor, such as complete Riemannian surfaces of finite Euler genus, string graphs, and Cayley graphs of finitely generated minor-excluded groups.

In this paper, we provide a simple criterion for the Schubitope $\mathcal{S}_{D}$ associated to a diagram $D$ to be lattice-free. We further show that $\mathcal{S}_{D}$ is lattice-free if and only if its Ehrhart polynomial is equal to the product of Ehrhart polynomials of the Schubert matroid polytopes corresponding to each column of $D$. As applications, we obtain that the Newton polytopes of the Schubert polynomial $\mathfrak{S}_w(x)$ and the Grothendieck polynomial $\mathfrak{G}_w(x)$ are lattice-free if and only if $w$ avoids the patterns 1423, 1432, 13254, and confirm several conjectures by Mészáros, Setiabrata, and St.Dizier on the support of Grothendieck polynomials for this class of permutations.

We extend the augmented bipartite graph framework for biquadratic sum-of-squares (SOS) ranks by introducing $3$-edges – triples of cells representing squares of three-term bilinear forms. We define suitable generalized cycle-free conditions that are purely combinatorial yet sufficient to guarantee that the SOS rank equals the total number of edges, carefully distinguishing occupation by $1$/$2$-edges from occupation by $3$-edges. The main theorem states that for any generalized cycle-free augmented bipartite graph $G$ satisfying the simplicity condition (S), the associated triply simple biquadratic form $P_G$ satisfies $\operatorname{sos}(P_G) = |E_1| + |E_2| + |E_3|$. The proof extends the orthogonality method with a novel trick: when a $2$-edge and a $3$-edge interact, the $3$-edge condition must be invoked rather than the $2$-edge condition. We give three applications. A $5 \times 3$ construction with two $2$-edges, inadmissible under the original definition, is admissible under our new definition, yielding $z_{3L}(5,3) \ge 10$ and improving $z_L(5,3)=9$. A $10 \times 5$ graph using a column-fully-degenerate $3$-edge gives $z_{3L}(10,5) \ge 27$, separating it from $z_L(10,5)=26$. A $15 \times 6$ graph using a half-row-degenerate $3$-edge improves the lower bound for $\operatorname{BSR}(15,6)$ from $43$ to $44$. These are the first explicit applications of $3$-edges to obtain improved lower bounds for $\operatorname{BSR}(m,n)$, and the $5 \times 3$ example demonstrates the power of the refined conditions.

The distance spectral radius of a connected hypergraph is the largest eigenvalue of the distance matrix of the hypergraph. A pendant path of length l with l greater than or equal to 1 in a hypergraph G at vertex v sub l plus 1 is a path consisting of vertices and edges v1 e1 v2 up to vl el v(l+1). The vertex v(l+1) has degree at least 2, vertex v1 has degree 1, and each vertex vi has degree 2 for i from 2 to l. Every vertex belonging to edge ei except vi and v(i+1) has degree 1 for all i from 1 to l. We find the unique hypertree that maximizes or minimizes the distance spectral radius among all r-th power hypertrees with m edges and k pendant paths of length l, where r is no less than 3, k and l are no less than 1, and the product of k and l is smaller than m.

A set $M$ of nonzero integers is said to split a finite abelian group $G$ if there exists a subset $S\subseteq G$ such that $M\cdot S = G\setminus\{0\}$. Such a splitting is called purely singular if every prime divisor of $|G|$ divides some element of $M$. In 1995, Woldar \cite{W1995} conjectured that the finite abelian groups admitting a purely singular splitting by the set $\{1,2,\dots,k\}$ are precisely the cyclic groups of orders $1$, $k+1$, and $2k+1$. In this paper, we prove this conjecture.

Width-based automated theorem proving is a framework where counterexamples to graph-theoretic conjectures are searched width-wise relative to some graph width measure, such as treewidth or pathwidth. In a recent work it has been shown that dynamic programming algorithms operating on tree decompositions can be combined together with the purpose of width-based theorem proving. This approach can be used to show that several long-standing conjectures in graph theory can be tested in time \(2^{2^{k^{O(1)}}}\) on the class of graphs of treewidth at most \(k\). In this work, we give the first steps towards evaluating the viability of this framework from a practical standpoint. At the same time, we advance the framework in two directions. First, we introduce a state-canonization technique that significantly reduces the number of states evaluated during the search for a counterexample of the conjecture. Second, we introduce an early-pruning technique that can be applied in the study of conjectures of the form \(\mathcal{P}_1 \rightarrow \mathcal{P}_2\), for graph properties \(\mathcal{P}_1\) and \(\mathcal{P}_2\), where \(\mathcal{P}_1\) is a property closed under subgraphs. As a concrete application, we use our framework in the study of graph-theoretic conjectures related to coloring triangle-free graphs. In particular, our algorithm is able to show that Reed's conjecture for triangle-free graphs is valid on the class of graphs of pathwidth at most 5, and on graphs of treewidth at most 3. Perhaps more interestingly, our algorithm is able to construct in a completely automated way counterexamples to invalid strengthenings of Reed's conjecture. These are the first results showing that width-based automated theorem proving is a promising avenue in the study of graph-theoretic conjectures.

Addressing a question posed by Chen and Ma from an asymptotic point of view, we present a short proof for the edge density needed to guarantee that two vertices of the same degree are connected by a path of a fixed length. In particular, we show that for any sufficiently large graph, a density of at least $1/2+o(1)$ enforces the existence of two such vertices. This bound is tight for paths of odd length.

Grothendieck weights, introduced by Shah, are $K$-theoretic analogues of Minkowski weights on smooth toric varieties. We study Grothendieck weights on the permutohedral fan and prove two main results: a $K$-balancing condition that characterizes Grothendieck weights by a finite system of linear equations, and an explicit product rule for the ring structure. We apply this framework to matroids, giving a combinatorial characterization of Grothendieck weights on matroidal fans. As the main application, we compute the motivic Chern class of the hyperplane arrangement complement in its wonderful compactification and show that the result depends only on the matroid, not on the realization. This allows us to extend the definition of the motivic Chern class to all loopless matroids.

We study homomorphisms of Hecke monoids, notably parabolic homomorphisms, which map parabolic elements to parabolic elements, and injective ones. The importance of the first class stems from the fact that parabolic elements form a rather mysterious submonoid of the Hecke monoid, and we found a plethora of parabolic homomorphisms. Concerning injective ones, as a first step towards their classification, we classified all locally injective connected homomorphisms between Hecke monoids of classical types and expect all of them to be injective. As a surprising byproduct of our study of parabolic and injective homomorphisms we described, to some extent, all homomorphisms between Hecke monoids.

In this work, we introduce TreeWidzard, an engine for developing dynamic programming algorithms that decide graph-theoretic properties parameterized by treewidth and pathwidth. Besides providing a unified framework for algorithms deciding atomic graph-theoretic properties, our engine allows one to combine such algorithms for two purposes: to obtain dynamic programming algorithms for more complex graph properties, and to support treewidth-based automated theorem proving. Within this context, given the specification of a Boolean combination \(P\) of graph properties \(P_1, P_2, \ldots, P_r\), and a positive integer \(k\), our engine can be used to determine whether all graphs of treewidth at most \(k\) satisfy \(P\). The main goal of the present work is to provide a system description of TreeWidzard. In particular, we provide a step-by-step account of how to implement dynamic programming algorithms in our framework and how to combine these algorithms for model checking and automated theorem proving.

For words in the variables $X$ and $Y$ satisfying the commutation relation of the $q$-deformed generalized Ore algebra, $XY-qYX= \mu I + \nu Y$, we show that the corresponding normal ordering coefficients can be given an interpretation in terms of mixed placements of rooks and files. In particular, the associated $q$-deformed Ore-Stirling and Ore-Lah numbers are treated in detail. We show that the $q$-deformed Ore-Stirling numbers (resp., $q$-deformed Ore-Lah numbers) are given as mixed placement numbers of rooks and files on the staircase board (resp., Laguerre board). Using this combinatorial interpretation, their recurrence relations are derived. In addition, the normal ordered form of the binomial $(X+Y)^m$ in the $q$-deformed generalized Ore algebra is determined. These considerations are then extended to the $q$-deformed polynomial Weyl algebra generated by $X$ and $Y$ satisfying $XY-qYX=f(Y)$ for some polynomial $f\in \mathbb{C}[Y]$. In particular, associated $q$-deformed polynomial Stirling and Lah numbers are introduced and their properties studied. The normal ordered form of the binomial is also extended to the $q$-deformed polynomial Weyl algebra.

Majorization is a stochastic ordering relation that compares the relative diversity of probability distributions with numerous applications in econometrics, spectral theory, and ecology. It is well-known that the majorization partial order forms a complete lattice on the set of ordered probability distributions. In this work, we study the properties of Rényi entropy on the majorization lattice. We establish a fundamental relation between the comonotone coupling and the independent coupling associated with a collection of marginal distributions. Consequently, we show that, for every order $\alpha \in [0,\infty]$, the Rényi entropy is subadditive on the majorization lattice. We further characterize the supermodular regime, showing that Rényi entropy is supermodular on the majorization lattice for $\alpha \in \{0\} \,\cup \, [1,\infty]$. For the Tsallis entropy, we show that it also satisfies subadditivity on the majorization lattice, for every order $\alpha \in [0,\infty)$. Finally, we show that, unlike the Rényi entropy, the Tsallis entropy is supermodular on the majorization lattice for every $\alpha \in [0,\infty)$.

We study the two-player coupon-collector competition in which two independent collectors draw one coupon each per round from a set of $d$ equally likely coupon types. Myers and Wilf gave finite formulae for several two-player events and explicitly left open the ballot-type problem of finding the probability that the ultimate winner was never behind. We prove that this probability satisfies $$ b_d \sim \frac{2}{d}, \qquad d\to\infty .$$ The proof uses a renewal decomposition at the tie boundary. The first one-sided tie-break has an explicit entrance distribution; its level, scaled by $d^{1/2}$, converges to a Rayleigh law; and, after the break, the leader's survival probability is governed by a Catalan, or gambler's-ruin, harmonic. The main estimate shows that the accumulated defect of this comparison harmonic in the exact simultaneous-round chain is negligible.

This paper presents a novel construction method for symmetric Sudoku-type games based on Lee distance perfect codes and diameter perfect codes. The proposed method utilizes the tiling property of these codes to define the structure of the subgrid constraints of Sudoku-type games. In this way, our games inherit the symmetric properties of Sudoku. We provide a detailed analysis of two small cases: a $5 \times 5$ Sudoku in $\mathbb{Z}_5^2$, and an $8 \times 8$ Sudoku in $\mathbb{Z}_8^2$. By defining equivalence relations via rigid motions, we provide a complete enumeration of valid grids, identifying 17 inequivalent solutions for $5\times 5$ Sudoku. For two different types of $8\times 8$ Sudoku, we characterize 232,735 and 304,014 inequivalent solutions, respectively. Furthermore, to verify practical playability, we implement a human-like solver that assesses the difficulty of the generated games. The analysis confirms that our $5\times5$ Sudoku games offer a balanced distribution of difficulty levels, ranging from Easy to Hard, making them a viable alternative to traditional $9 \times 9$ Sudoku.

In this paper, we introduce a new combinatorial operation, called a flip, on arbitrary partially ordered sets. We define a mutation to be a flip that maps a lattice to a lattice. We study properties of flips, and give a necessary and sufficient condition for a flip to be a mutation. We introduce locally mutable lattices and mutable lattices in terms of flips, and prove that mutable lattices are semidistributive. We show that type-A and type-B Cambrian lattices are locally mutable, and those associated with the finite-type Coxeter quivers with different orientations are related also by the sequence of mutations. Finally we introduce a new class of lattices, called Ordovician lattices, as the lattices obtained from Cambrian lattices by iterated mutations. We provide conjectures on the structure of Ordovician lattices and on the compatibility between our mutation and the mutation in the theory of cluster algebras.

In this paper, we introduce the comaximal graph $\Gamma(L)$ of a finite-dimensional Lie algebra $L$, whose vertices are the nontrivial proper Lie subalgebras of $L$ over a field $\mathbb{F}$, and two vertices $A$ and $B$ are adjacent if and only if $\langle A, B\rangle =L$. We establish general structural properties, including a characterization of isolated vertices via the Frattini subalgebra and a criterion for completeness in terms of $\mu$-algebras. We classify $\Gamma(L)$ for all Lie algebras of dimension at most three over a finite field $\mathbb{F}_q$, providing an explicit description in each case. The resulting graphs exhibit a rich range of behaviors, depending on the structure of the derived algebra and the action of $\operatorname{ad}x$. For $L\cong \mathfrak{sl}_2(\mathbb{F}_q)$, we determine several graph invariants, including the degree sequence, clique number, chromatic number, domination number, diameter, and radius, and show that $\Gamma(L)$ is connected and non-planar. The graph contains a large clique formed by the nonsplit semisimple lines together with the Borel subalgebras, while the nilpotent and split semisimple lines have a more restricted adjacency structure governed by their containment in Borel subalgebras.

Let $[n]$ (resp. $V$) be an $n$-element set (resp. $n$-dimensional vector space over the finite field $\mathbb{F}_{q}$), and $\binom{[n]}{k}$ (resp. $\genfrac{[}{]}{0pt}{}{V}{k}$) denote the set of all $k$-subsets of $[n]$ (resp. $k$-dimensional subspaces of $V$). We say that $\mathcal{F}\subseteq\binom{[n]}{k}$ (resp. $\mathcal{F}\subseteq \genfrac{[}{]}{0pt}{}{V}{k}$) and $\mathcal{G}\subseteq \binom{[n]}{k'}$ (resp. $\mathcal{G}\subseteq \genfrac{[}{]}{0pt}{}{V}{k'}$) are $\ell$-weakly cross $t$-intersecting if $\sum_{1\leq i,j\leq \ell}|F_{i}\cap G_{j}|\geq \ell^{2}t-\ell+1$ (resp. $\sum_{1\leq i,j\leq \ell}\dim(F_{i}\cap G_{j})\geq \ell^{2}t-\ell+1$) for all distinct $F_{1},\ldots,F_{\ell}\in\mathcal{F}$ and $G_{1},\ldots,G_{\ell}\in\mathcal{G}$. In this paper, we provide an alternative proof of the set version of the $\ell$-weakly cross $t$-intersecting theorem and an explicit lower bound for $n$. Moreover, we prove that if $\mathcal{F}$ and $\mathcal{G}$ are $\ell$-weakly cross $t$-intersecting subspace families, then \[ |\mathcal{F}| \cdot |\mathcal{G}| \leq\genfrac{[}{]}{0pt}{}{n-t}{k-t}\genfrac{[}{]}{0pt}{}{n-t}{k'-t} \] holds, provided that $n\geq (2k-t+1)(t+1)+(k-t+1)k'+k+2\ell-1$. This extends the theorem of Cao, Lu, Lv and Wang [J. Combin. Theory Ser. A 193 (2023), 105688], who established the upper bound for the product of the sizes of cross $t$-intersecting subspace families.

For integers $n\ge s\ge2$, let $e(n,s)$ denote the maximum size of a family $\mathcal F\subseteq2^{[n]}$ with no $s$ pairwise disjoint members. The problem of determining $e(n,s)$, now called the Erdős–Kleitman problem, is the non-uniform analogue of the Erdős matching conjecture. We prove that for every fixed $m\ge3$, there exist constants $\beta_m$ and $\delta_m$ such that for sufficiently large $s$, the extremal families for $e(ms+c,s)$ are \[ \mathcal P'(m,s,\ell;L'):=\binom{L'}m\cup\binom{[ms+c]}{\ge m+1} \] for some $L'$ with $\ell=s-c$ and $|L'|=m\ell-1$, when $\beta_m s^{(m-1)/m}\le c\le \delta_m s$. This determines the extremal families in an unknown range when $\ell$ is large, complementing our earlier work on the range when $\ell$ is small. Moreover, for $m=3$, we sharpen this to the asymptotically optimal range. Let \[ t(s)=\frac{17-18s+\sqrt{49-852s+1284s^2}}{20}=0.8916\cdots s+O(1) \] We prove that \(\mathcal P'(3,s,\ell;L')\) is the unique extremal family when $t(s)<\ell<s-((4/3)^{1/3}+o(1))s^{2/3}$. Note that the lower bound \(t(s)\) of $\ell$ is exact, while the the constant \((4/3)^{1/3}\) in the upper bound of $\ell$ is best possible. Kupavskii and Sokolov introduced four candidate extremal families and conjectured that the value of $e(n,s)$ is the maximum of their sizes. We disprove this conjecture by constructing a new family $\mathcal R(m,s,\ell)$ that is larger than each of their four proposed candidates when $\alpha_{\mathrm R}s^{1/2}\le c\le \beta_{\mathrm R}s^{(m-1)/m}$ for some constants $\alpha_{\mathrm R}$ and $\beta_{\mathrm R}$. This also shows that the exponent $(m-1)/m$ in the first result is tight.

We introduce the moduli space of metric Möbius graphs, which extend ribbon graphs to the non-orientable world. This space contains both the moduli space of Riemann surfaces and the moduli space of non-orientable Klein surfaces. Each metric Möbius graph is equipped with a measure of non-orientability. We count lattice points in this moduli space, weighted by the measure of non-orientability, and prove a refined version of Norbury's recursion for this count. Taking the limit as the mesh becomes finer, we deduce a recursion for the Euclidean volumes, yielding a refined version of the Witten–Kontsevich recursion. As an application, we give a geometric definition of the refined Euler characteristic of the moduli space and compute it explicitly, thereby answering a question of Goulden, Harer, and Jackson.

We resolve exercise 7.2.2.4–224 of Knuth's Pre-Fascicle 8a (10 April 2026 draft, rated [46]): the digraph $\mathit{SB}(3,n)$ has no Hamiltonian cycle when $n$ is even. The argument is a sign-of-permutation obstruction. Writing the successor map of a candidate Hamiltonian cycle as $f_S = A_b \circ \sigma$, $\operatorname{sgn}(A_b)=+1$ when $m$ is odd, so $\operatorname{sgn}(f_S)=\operatorname{sgn}(\sigma)$ for every choice set $S$. A short dihedral Burnside computation shows $\operatorname{sgn}(\sigma)=-1$ on $\Sigma_3^n$ for even $n$, contradicting the sign $+1$ required of a single $3^n$-cycle. The same argument gives the stronger statement that $\mathit{SB}(m,n)$ has no Hamiltonian cycle whenever $m$ is odd with $m\equiv 3\pmod 4$ and $n$ is even; this restricts the residue classes in which Knuth's hint to Ex.~225 (existence of Hamiltonian cycles in $\mathit{SB}(m,n)$ for all $m>3$ and $n>2$) can hold.

Let $G$ be a cubic graph admitting a $2$-factor consisting of exactly two odd circuits, and let the complementary $1$-factor contain precisely three spokes (along with an arbitrary number of chords). We show that four perfect matchings can cover $G$. As a consequence, $G$ fulfils the 7/5-Conjecture of Alon and Tarsi.

Achlioptas processes such as the Bohman–Frieze process are much harder to analyse than the classical Erdős–Rényi process, due to the dependence between edges added at different stages. This dependence means that most analysis so far is dynamic, often based on the differential equation method. In the Erdős–Rényi case there is an alternative static approach, pioneered by Erdős, Rényi and Bollobás, based on evaluating the expectation (and higher moments) of various subgraph counts, and using this to study the component structure. Here we show that this latter approach can be applied (with some complications) to the Bohman–Frieze process. For example, we are able to show that the expected number $\mu_{k,t,n}$ of $k$-vertex tree components after $tn$ steps satisfies (essentially) $\mu_{k,t,n}=c_{k,t}n(1+O(k/\sqrt{n}))$. Our method gives a very complicated formula for $c_{k,t}$, which seems to be unusable. However, since $c_{k,t}$ does not depend on $n$, we may use recent results obtained by the differential equation method and branching process analysis to find the asymptotics of $c_{k,t}$ as $k\to\infty$. The latter results also give a formula for $\mu_{k,t,n}$ of the form $c_{k,t}n$ plus an error term, with a much more usable description of $c_{k,t}$ but a much worse error term. We combine the best of both worlds to prove a number of new results about the process near criticality. In particular, we obtain extremely sharp bounds on the size of the largest non-giant component near criticality, including the limiting distribution of its fluctuations.