Papers

A digraph $D = (V,E)$ is 3-transitive (respectively, 3-quasi-transitive) if whenever $(u,v,w,z)$ is a directed path of length 3, $(u,z) \in E$ (respectively, $(u,z) \in E$ or $(z,u) \in E$). These digraphs extend the concepts of transitive and quasi-transitive digraphs, respectively. For 3-transitive and 3-quasi-transitive digraphs, only the strong case has been characterized. In this paper, we introduce the notion of semi-acyclic digraphs and use it to describe completely the structure of 3-transitive and 3-quasi-transitive digraphs. As an application of this type of structure description, we prove that the path partition conjecture holds for the class of extended semi-acyclic digraphs, which generalizes two previously known results on the conjecture.

We present a proof of the two-token graph reconstruction conjecture. Every finite simple graph $G,H$ of order at least three, $F_2(G) \cong F_2(H)$ if and only if $G \cong H$. We also classify the automorphism groups of two-token graphs whose connected roots have order at least five. Combining these results, we show that, for connected graphs $G,H$ of order at least five, every isomorphism $\phi:F_2(G)\to F_2(H)$ admits a factorization $\phi=\eta\circ\sigma^{(2)}$, where $\sigma^{(2)}$ is induced by a graph isomorphism $\sigma:G\to H$, and $\eta\in \operatorname{Aut}(F_2(H))$ is a product of twin-cut switches or Cartesian exchanges.

In this paper we examine the special class of bipartition complete matroids, which includes free products and principal sums of matroids (Crapo and Schmitt, 2005; Bonin and Kung, 2015). A matroid $\mathcal{M}_{SQ}$ on $S \uplus Q$ is said to be $\{S,Q\}$–complete iff whenever $b^1_S \uplus b^1_Q, \, b^1_S \uplus b^2_Q,$ and $b^2_S \uplus b^1_Q$ are bases of $\mathcal{M}_{SQ},$ we also have $b^2_S \uplus b^2_Q$ as a base of $\mathcal{M}_{SQ}.$ We use the linking operation $\mathcal{M}_{SP} \leftrightarrow_{\mathcal{M}} \mathcal{M}_{PQ} :\equiv (\mathcal{M}_{SP} \vee \mathcal{M}_{PQ}) \times (S \uplus Q)$ (Theja and Narayanan, 2014) for this study. We construct the $\{S, Q\}$–augmentation of an arbitrary matroid and show that this augmentation is again a matroid, that the dual of the augmentation is the augmentation of the dual matroid and that the $\{S, Q\}$–augmentation of an $\{S, Q\}$–complete matroid leaves it unchanged. We also show that bipartition completeness is stable under minors in the appropriate bipartitioned sense. Finally, we show that free products and principal sums of matroids $\mathcal{M}_{S},\mathcal{M}_{Q}$ are $\{S, Q\}$–complete and give explicit minimal decompositions for them.

An $(r,z,g)$-mixed cage is a mixed graph that is $r$-regular in edges, $z$-regular in arcs, of girth $g$ and of minimum order $n=n(r,z,g)$. We give a general lower bound for $n(r,z,g)$. In the case $g=3$, we determine the exact value $n(r,z,3)=r+2z+1$. For $g=4$ we give two improved lower bounds and we determine the exact value $n(r,z,4)=2r+4z$ for $r\geq 2z-2$. We also present computational results, obtaining mixed cages and computational lower bounds by means of exhaustive backtracking searches with symmetry reductions. Moreover, we give an upper bound for $n(1,z,g)$ that matches all our computed values.

The $(0,x,1,2)$-hiccup sequence starts at $x$ and increases by 1 when the current index has already appeared as a value, and by 2 otherwise. We prove directly that for $x\geq3$ the gaps between its missing values are $1,2,3,\ldots$, each repeated $x-2$ times, and we derive closed formulas, an explicit error bound, and a generating function in terms of Ramanujan's theta functions. The counting functions of the complements satisfy nested recurrences. The sequences of missing values are the partial complements of polygonal numbers. In particular, the $(x-2)$-fold composition of the enumeration of the positive integers that are not $x$-gonal is the hiccup sequence minus 1. We extend the nested recurrence and a tree interpretation to every miss increment $z\geq2$ and every initial value $x\geq2$. Further interpretations involve polyomino vertices, monochromatic pairs, and, by a theorem of Bickle, Ramsey core numbers.

Two graphs are degree similar if their adjacency matrices and their degree matrices are simultaneously similar, a notion recently introduced by Godsil and Sun. We extend it to signed graphs in two ways, degree similarity and net-degree similarity, according to whether the degree or the net-degree matrix is used. We prove that signed trees are determined by their degree similarity class, but not by their net-degree similarity class. We then develop constructions of (net-)degree similar signed graphs, based on a signed version of Godsil–McKay switching, on partial transposition and on block extensions. As a byproduct, we obtain infinite families both of pairs of net-degree similar unicyclic signed graphs with non-isomorphic underlying graphs, and of unicyclic signed graphs, not necessarily regular, which are not determined by their degree similarity class. This settles the net-degree version of a problem of Godsil and Sun on unicyclic graphs.

Using spectral and polynomial methods, we show several sharp spectral bounds for the clique and chromatic numbers of graph powers that only use spectral information from the original graph. In particular, we strengthen earlier spectral-radius estimates to obtain an asymptotically sharp colouring bound for general graph powers, and prove a sharp bound for powers of line graphs with a complete characterisation of equality. We also develop polynomial methods yielding upper and lower bounds for clique numbers of graph powers. Regarding the connection between the clique and coloring parameters of graph powers, we propose a spectral analogue of Wegner's conjecture, determine the extremal values for graph squares, and establish the conjecture for all powers when the spectral-radius bound is sufficiently small. Finally, we connect our spectral polynomial method with coding theory: we prove that for distance-regular graphs, optimisation over the adjacency algebra recovers Delsarte's linear programming bound for anticodes.

An $n$-vertex graph $G$ is $(\rho, d)$-dense if for all $U \subseteq V(G)$ of size at least $\rho n$, the induced subgraph $G[U]$ contains at least $\frac{d}{2}|U|^2$ edges. In 2010, partly motivated by the theory of quasirandomness, Kohayakawa, Nagle, Rödl, and Schacht conjectured that, for any fixed graph $F$, the number of homomorphic copies of $F$ in a given $n$-vertex $(o(1),d)$-dense graph is at least $(1-o(1))d^{e(F)}n^{v(F)}$. Despite considerable effort, only a few graphs are known to satisfy the conjecture. We find a new broad class of graphs that satisfy the conjecture, including cographs.

Abstract polytopes and hypertopes are thin and residually-connected incidence geometries or, equivalently, chamber systems. Their degree of regularity is understood by looking at the action of their automorphism group on the set of their chambers. When this action has only one orbit, they are called regular. In this article, we are interested in polytopes and hypertopes with exactly two orbits on their chambers. Let $I = \{1,2,\ldots,n\}$. For any $J\subsetneq I$ with $|I| \geq 3$, we show that there exists a class $2_J$ two-orbit hypertope whose diagram is any graph on $|I|$ vertices, with edges all labeled by $\infty$. In order to do so, we first establish a general framework for constructing hypertopes as quotient of chamber systems, and then exploit the machinery of acylindrically hyperbolic groups for showing that this framework can be used to create two-orbit polytopes and hypertopes of class $2_J$. Note that all polytopes and hypertopes constructed in this paper are infinite.

Let $D$ be an oriented graph. For $X \subseteq V(D)$, the inversion of $X$ in $D$ is the oriented graph that is obtained via changing the direction of all edges which have both endpoints in $X$. The inversion number of $D$, $\operatorname{inv}(D)$, is the minimum number of inversions necessary in order to remove all cycles from $D$. A dijoin $D_1 \to D_2$ is the oriented graph obtained by taking disjoint copies of $D_1,D_2$ and adding edges from all $v \in V(D_1)$ to each $u \in V(D_2)$. It was conjectured by Bang-Jensen, da Silva and Havet that $\operatorname{inv}(D_1 \to D_2) = \operatorname{inv}(D_1) + \operatorname{inv}(D_2)$ for all $D_1, D_2$. This was disproved by simultaneous constructions of various $D_1$, $D_2$ with $\operatorname{inv}(D_1 \to D_2) = \operatorname{inv}(D_1)+\operatorname{inv}(D_2)-1$. However, no known constructions achieved more than this gain of 1. Moreover, all of the constructions exploit a gap of 1 between $\operatorname{inv}(D)$ and the minimum rank of a family of related matrices, a gap that can never be more than 1, suggesting that perhaps something close to the original conjecture might be true. We prove that in fact additivity fails badly. In particular, for all $\varepsilon>0$ we show that there exist tournaments $D_1$, $D_2$ with arbitrarily large inversion numbers such that $\operatorname{inv}(D_1 \to D_2) \leq \left(\frac{1}{2} +\varepsilon\right)(\operatorname{inv}(D_1)+\operatorname{inv}(D_2))$.

We study the list chromatic number of generalized Johnson graphs. Recall that the vertices of such graphs are all possible $r$-element subsets of $[n] = \{1, \dotsc, n\}$ and an edge is drawn between two vertices if and only if corresponding sets have exactly $s$ common elements. We prove that for any fixed $s \geq 1$ and $r \geq 2s + 2$ we have $\chi_L(G(n,r,s)) = \Theta(n^{s+1}\ln n)$. In case where $s = 0$ we prove that for all $4\ln n \leq r \leq n/20$ we have $\chi_L(G(n,r,0)) \geq \frac{n}{120}\ln\left(\frac{en}{r}\right)$. Together with previous results of Bulankina, Inozemtsev and Kupavskii this proves that $\chi_L(G(n,r,0)) = \Theta\left(n\ln\left(\frac{en}{r}\right)\right)$ uniformly for $2 \leq r \leq (1/2-\varepsilon)n$.

We prove optimal dual Furstenberg estimates for Frostman and Katz–Tao configurations for which the shadings are not locally concentrated near pencils. The starting point is the sticky estimate of Orponen and Shmerkin in a companion paper. We deduce restricted projection theorems in the plane and in higher dimensions. In particular, Ahlfors-regular measures on the circle satisfy a Marstrand-type projection theorem. Applications include restricted projections to surfaces in the $\mathbb{G}(4,2)$ Grassmannian, pinned distances, discretized sum-product, and a new proof of the dimension formula for planar self-affine sets.

We introduce spread-out measures, a notion of local non-concentration near pencils for measures on Grassmannians. We establish an optimal $\delta$-discretized dual Furstenberg estimate for “sticky spread-out” shadings. A simple-to-state corollary is the following. Assume that $\nu$ is an Ahlfors $s$-regular measure on $\mathbb{G}(2,1)$ with $s > 0$. Let $E \subset \mathbb{R}^{2}$ be a Borel set with equal Hausdorff and packing dimension. Then, $\dim_{\mathrm{H}} \Pi_{V}(E) = \min\{\dim_{\mathrm{H}} E,1\} \quad \text{for $\nu$-a.e. } V \in S^1$. The general $\delta$-discretized estimate for “sticky spread out” configurations here is the starting point for a more general theorem in the companion paper of Cohen, Shmerkin, Wang and Zakharov, where the “stickiness” hypothesis is removed. For instance, the assumption of equal Hausdorff and packing dimension in the result stated above will be dispensed with in the companion paper.

We apply the generalized monoid of words and logarithmic-prefix functionals of \cite{C1} to the regularization of the divergent product \[ P_{\omega}=\prod_{n=1}^{\infty} n^{(-1)^{\omega(n)}}, \] where \(\omega(n)\) is the number of distinct prime divisors of \(n\). The associated Dirichlet series \(D_{\omega}(s)=\sum_{n\ge1}(-1)^{\omega(n)}n^{-s}\) has a natural boundary at \(\Re(s)=0\), as established by Meretov (1987) and recovered here as a special case of the Estermann–Dahlquist theory of Euler products, which makes zeta regularization impossible: the derivative \(D_{\omega}'(0)\) does not exist. This product therefore lies completely beyond the reach of classical regularization methods. We construct the canonical net encoding the sign sequence, define the logarithmic-prefix functional with exponent \(\alpha=2\), and extract a finite value through the weighted evaluation functional of the monoid framework. The evaluation functional is shown to converge absolutely, and this convergence is unconditional: it follows from the classical zero-free region of \(\zeta(s)\) (de la Vallée Poussin), which yields the effective bound \(T_{\omega}(x)=O(x\,e^{-c\sqrt{\log x}})\) for some \(c>0\). Numerical computation up to \(N=10^7\) gives the regularized value \[ P_{\omega,\mathrm{ren}}\approx 0.7731, \] a new constant of arithmetic origin that cannot be obtained by any classical summation method. We also compute the second derivative of the Dirichlet series at \(s=1\), \[ D_{\omega}''(1)=8\,C_2\ln 2, \] where \(C_2\) is the Hardy–Littlewood twin prime constant, which provides an unconditional analytical link to the arithmetic structure of the sequence \((-1)^{\omega(n)}\). A self-contained proof of the natural boundary, based on the Estermann–Dahlquist theorem, is given in Appendix~A.

Chromatic villainy measures the largest number of vertices that must change color to repair a rearrangement of an optimal coloring while preserving every color multiplicity. Weak villainy allows different multiplicities in the repair. On the odd cycle $C_{2r+1}$, we determine the largest repair distance from arbitrary color assignments with a prescribed color-count vector (profile) $\mathbf m$ to proper colorings with any realizable target profile $\mathbf p$: it equals $2r+1-\sum_X\min\{p_X,\lceil m_X/2\rceil\}$. In particular, every feasible profile $(a,b,c)$ has ordinary and weak repair radius $\lfloor a/2\rfloor+\lfloor b/2\rfloor+\lfloor c/2\rfloor$, and $B(C_{2r+1})=r$ for $r\ge2$, answering a question of Clark et al. For arbitrary complete multipartite graphs, we give an arithmetic formula for ordinary villainy with at most $k^2$ candidates and an exact finite formula for weak villainy, where $k$ is the number of parts. Both values are fixed-parameter tractable in $k$ for binary-encoded part sizes. We also determine the maximum of each parameter among all $n$-vertex $k$-chromatic graphs. For $k\ge3$, the ordinary maximum is $\min\{n,4(n-k)\}$, except when $n=4(n-k)-1$ or $(n,k)\in\{(5,3),(7,3)\}$, when it is $n-1$. For $k\ge2$, the weak maximum is $n-\max\{\lceil n/k\rceil,2k-n\}-\varepsilon$, where $\varepsilon\in\{0,1\}$ is determined explicitly by $n$ and $k$. Both extrema are attained by complete multipartite graphs, and a weak extremizer needs at most three distinct part sizes.

Chromatic villainy is the maximum, over rearrangements of optimal graph colorings, of the minimum Hamming distance to a proper coloring with the same color multiplicities. Weak villainy allows the repair to change these multiplicities. We give exact composition laws for disjoint unions and determine the eventual growth under repetition. Write $mG$ for the disjoint union of $m$ copies of $G$. For every graph $G$, with $k=\chi(G)$, weak villainy satisfies $B_{\mathrm w}(mG)=mF_k(G)$ whenever $k\mid m$, where $F_k(G)$ is the maximum distance to a proper $k$-coloring over all assignments of $k$ color labels to vertices. Its bounded defect from $mF_k(G)$ is eventually periodic; we give an explicit stabilization bound and identify the least period, which divides $k$. For ordinary villainy, we obtain a computable rational slope $\Lambda(G)\ge F_k(G)$ such that $B(mG)=m\Lambda(G)+O_G(1)$, where the error is bounded independently of $m$ and eventually periodic, with a computable period and threshold. Consequently the difference between the two values is bounded exactly when $\Lambda(G)=F_k(G)$, and otherwise grows linearly. The slope is determined by a finite optimization using at most $k$ source assignments. We also answer the unrestricted superadditivity questions negatively: for every $C>0$, a connected graph can lose more than $C$ in weak villainy after union with a triangle, and some connected $3$-chromatic graph $G$ satisfies $B(G\sqcup G)<2B(G)-C$. Finally, both exact values on an $n$-vertex graph can be computed in time $f(B_{\mathrm w}(G))(n+1)^{O(1)}$, without either value being supplied. Threshold recognition is fixed-parameter tractable as well.

We continue the systematic study initiated in arXiv:2602.05185 of the relationship between the spectral theory and descriptive combinatorics of bounded-degree Borel pmp graphs, particularly in the non-regular setting. We first adapt a classical result of Nikiforov to give a new spectral lower bound on the approximate measurable chromatic number. For certain non-regular graphs, this bound improves on the approximate measurable version of Hoffman's classical bound established in arXiv:2602.05185. Next, we strengthen a characterization in arXiv:2602.05185 of approximate measurable bipartiteness in terms of the spectrum of the adjacency operator by generalizing to the case of non-regular graphs. Finally, we introduce the measurable domination number and adapt several classical results of Lu, Liu, and Tian to give a bound on the spectral gap of the Laplacian operator in terms of the measurable domination number.

A permutation is $n$-universal if it contains every permutation of length $n$ as a pattern. We prove that a uniformly random permutation of length $32n^2$ is $n$-universal with probability at least $1-\exp(-c n/\log n)$, for an absolute constant $c>0$ and all sufficiently large $n$. This removes a $\log\log n$ factor from an earlier result of He and Kwan~\cite{He-Kwan} and resolves an open problem of Alon~\cite{Alon2016}. The proof was found by GPT-6 Pro.

In a Latin square, every row can be interpreted as a permutation, and therefore has a parity (even or odd). We prove that in a uniformly random $n\times n$ Latin square, the probability that all rows are even is of the form $2^{-n+o(n)}$. This fills a gap left by recent work of Kwan, Petrova and Sawhney: they proved that the row parities behave like a sequence of independent coin flips in a variety of different senses, but they were not able to lower-bound the all-even probability, as their approach had a small number of "exceptional rows" whose parities they could not control. In fact, we prove a more general theorem on the probability of any possible prescription of row parities, column parities and symbol parities. Our approach extends the ideas of Kwan, Petrova and Sawhney, introducing a new way to "bootstrap" intercalate switchings to control more complex switching operations.

The DP color function $P_{DP}(\mathcal{H}, k)$ of a hypergraph $\mathcal{H}$ is defined as the minimum possible value of $P_{DP}(\mathcal{H}, \mathcal{F})$ taken over all $k$-fold covers $\mathcal{F}$ of $\mathcal{H}$. It serves as an extension of the classical chromatic polynomial. In this paper, we investigate the DP color function for two constructions: the join of a hypergraph with a complete graph and vertex-gluings of certain hypergraphs. Both constructions extend some results of Becker et al.

We prove that the dimension of the deformation cone of any polytope combinatorially equivalent to a 2-cubical zonotope is bounded above by the number of generators of the zonotope. This bound is tight, and we show that it cannot be improved to an identity. We further extend our results to any 2-cubical polytope whose normal fan is combinatorially isomorphic to a pseudohyperplane arrangement, but we show that it cannot be extended to arbitrary 2-cubical polytopes.

Given a graph $G$, a set $W$ of vertices of $G$ is a resolving set if, for any pair of vertices $z_1$ and $z_2$ of $G$, there is a vertex $w\in W$ such that $d(w,z_1)\ne d(w,z_2)$, where $d(u,v)$ denotes the length of a shortest path between the vertices $u$ and $v$. The metric dimension of a graph $G$, $\beta(G)$, is the minimum cardinality of a resolving set of $G$. A resolving set $W$ is fault-tolerant if $W\setminus \{w\}$ is a resolving set for any $w\in W$. The fault-tolerant metric dimension of a graph $G$, denoted by $\beta'(G)$, is the minimum cardinality of a fault-tolerant resolving set of $G$. In this paper, we study the fault-tolerant metric dimension problem in maximal outerplanar graphs. In particular, we show that there are exactly two maximal outerplanar graphs with $\beta'(G)=3$. We also show that $4\le \beta'(G) \le 6$ for any maximal outerplanar graph $G$ of order at least 7 and metric dimension 2. Moreover, we establish the upper bound $\beta'(G) \le \left\lceil \frac{2n}{3} \right\rceil$ for maximal outerplanar graphs $G$ of order $n\ge 5$, by building in linear time a fault-tolerant resolving set of cardinality $\left\lceil \frac{2n}{3} \right\rceil$.

This work extends the study of mobile resolvability in connected graphs by introducing completely mobile resolving sets. As with mobile resolving sets, we consider stationing a collection of robots at the vertices in a resolving set of a graph. Robots may move one at a time to any adjacent vertex as long as set of occupied vertices remains a resolving set. In this new variant, we ask that every robot can traverse every vertex in the graph through a sequence of permitted moves. Graphs possessing at least one completely mobile resolving set are termed mobile-resolvable. We completely characterise the non-mobile-resolvable graphs as paths of order at least three and subdivided stars with three or more leaves and at most two subdivided edges. For trees, we explicitly determine the completely mobile metric dimension, showing that it exceeds the classical metric dimension by one for most mobile-resolvable trees, and by two for certain subdivided stars. Furthermore, we evaluate this parameter across fundamental graph classes-including cycles, complete bipartite graphs, grid graphs, and circulant graphs.

Brambles of constant congestion in directed graphs have interesting structural and algorithmic applications, and it is desirable to find the smallest function $f_c(k)$ such that if a digraph has directed treewidth at least $f_c(k)$, then it contains a bramble of size at least $k$ and congestion at most $c$. By the Directed Grid Theorem of Kawarabayashi and Kreutzer [STOC 2015], such a function $f_c(k)$ exists for every value $c \geq 2$ of the congestion. However, even using the recent improvements due to Hatzel et al. [FOCS 2024], the resulting function is a power tower of height $22$. Recently, Masařík et al. [SIAM J. Discrete Math. 2022] proved that, for congestion $8$, the function $f_8(k)$ can be made polynomial; more precisely, they showed that $f_8(k) = \mathcal{O}(k^{48} \cdot \log^{13} k)$. They asked whether it is possible to decrease the congestion, ideally to $2$, even at the cost of a higher polynomial function. In this work we answer their question affirmatively with the best possible value of the congestion, by proving that $f_2(k) = \mathcal{O}(k^{96}\cdot \log^{23} k)$. We also obtain smaller polynomials for higher congestion, namely $f_4(k) = \mathcal{O}(k^{72} \cdot \log^{21} k)$ and $f_6(k) = \mathcal{O}(k^{66} \cdot \log^{18} k)$. Our results are inspired by the proof for congestion $8$, which we improve by introducing walkages. Walkages allow us to avoid technicalities of the original proof by translating ideas due to Reed and Wood [Eur. J. Comb. 2012] that work for undirected graphs to the directed setting. Our proofs are constructive and naturally yield polynomial-time algorithms to find the brambles assuming a certificate for large directed treewidth is given. Moreover, we discuss algorithmic applications of our results for the Directed Disjoint Paths with Congestion problem, and to half-integral packings of subgraphs with large directed treewidth.

We prove that any subset $A \subseteq \{1, \dots, N\}$ lacking non-trivial polynomial progressions $(x, x + y, x + y^2)$ satisfies $\lvert A \rvert \le CN \exp\bigl(-c(\log \log N)^\beta\bigr)$ for effective absolute constants $C, c, \beta > 0$. The argument develops a density increment framework localized to anisotropic quadratic Bohr sets. To handle mixed linear and quadratic frequencies, we establish a multilinear transference principle coupled with a relative quadratic inverse theorem based on Balog–Szemerédi–Gowers additive energy rigidity. Boundary stability across increments is maintained via semi-algebraic model regularization using cylindrical algebraic decomposition and Cauchy–Crofton estimates, while dimension growth is controlled by dissociated basis reduction and multidimensional Erdős–Turán–Koksma equidistribution.

Graph matrices that combine structural and metric information have attracted considerable attention in spectral graph theory. In this paper, we introduce the Degree–Adjacency–Diametrical (DAD) matrix of a connected graph $G$. The DAD matrix is defined by \[ (DAD(G))_{ij}= \begin{cases} d(v_i), & \text{if } i=j, 1, & \text{if } v_i\sim v_j, \operatorname{diam}(G), & \text{if } d(v_i,v_j)=\operatorname{diam}(G), 0, & \text{otherwise}, \end{cases} \] where $d(v_i)$ denotes the degree of the vertex $v_i$. We establish fundamental spectral properties of the DAD matrix by deriving trace identities, characteristic polynomials, and spectra for several classes of graphs. Furthermore, we obtain a spectral expression for the Wiener index of graphs with diameter two, derive upper bounds for the largest DAD eigenvalue, and establish lower bounds for the DAD energy. Explicit spectral characterizations are also obtained for complete multipartite graphs. The proposed matrix provides a unified spectral framework that simultaneously incorporates degree, adjacency, and diametrical information, thereby enriching the study of graph spectra and introducing a new graph matrix for spectral graph theory.

Let $G$ be a finite abelian group, and let $c_0(G)$ be the least integer such that every regular sequence over $G$ of at least this length is an additive basis. Let $\mathsf N(G)$ be the least integer $l$ such that every weak-regular sequence $S$ over $G$ with $|S|\ge l$ has a nonempty zero-sum subsequence $T$ satisfying $\mathsf v_g(T)=\mathsf v_g(S)$ for some $g\mid S$. We obtain a common upper bound for $c_0(C_q\oplus C_{nq})$ for groups of odd order, where $q$ is prime, and prove $\mathsf N(G)\ge r(n_r-1)+1$ when $G=C_{n_1}\oplus\cdots\oplus C_{n_r}$ with $1<n_1\mid\cdots\mid n_r$. If $n\ge1$ and $p\ge3$ is the smallest prime divisor of $np$, we obtain $\mathsf N(C_p\oplus C_{np^2})=2np^2-1$ and give upper bounds for $\mathsf N(C_p\oplus C_{np})$ when $p\nmid n$. We also determine $\mathsf N(C_n)$ for two infinite families of cyclic groups arising in earlier work.

We prove Pisanski's conjecture on quadrilateral embeddings of regular bipartite graphs. For integers $m\geq d\geq4$ with $4\mid md$, we construct both a connected simple $d$-regular bipartite graph $G$ with $m$ vertices in each bipartition class and an orientable quadrangulation. This graph's genus is \[ \ga(G)=1+\frac{m(d-4)}4. \] These quadrangulations attain the lower bound on the genus from Euler's formula. We give dihedral constructions for even $m$ and a cyclic construction for every $m\geq d$ with $4\mid d$. In each case, two cyclic permutations of a connection set of size $d$ determine all of the local rotations.

Random spanning forests provide probability models for partitions and Monte Carlo methods on graphs. In these applications, the distribution produced by a sampler determines which forest functionals can be estimated. The Aldous–Broder algorithm constructs a spanning tree from the first-entrance edges of a covering random walk. Its distribution is known, but a direct calculation requires summing over all orders in which a fixed tree can be discovered. We evaluate this sum through an identity for rooted forests and real matrices with zero row sums. Under a nonsingularity condition on the principal submatrices encountered during growth, the sum of products of harmonic extension entries equals a principal cofactor of a matrix on the roots. With one root, the sum is one. The identity gives a direct proof of the extended Aldous–Broder theorem for every finite irreducible Markov chain started at a fixed state, without assuming reversibility or bidirectional transition support. It also gives the conditional distribution of the discovery order and the law of the forest obtained by stopping after all nonroot vertices have been visited. A completion weight describes the difference between this stopped-walk law and the weight-proportional forest law, including the support restriction needed for importance correction. Numerical examples illustrate the sampling implications. The identity, the Aldous–Broder theorem, and the stopped-forest law are formalized in Lean4.

We prove that, for every fixed $d\geq 2$ and $\varepsilon>0$, the $\mathbb{F}_q$-points of a geometrically irreducible reflexive plane curve of degree $d$ over $\mathbb{F}_q$ can be covered by at most $\left(\frac{1}{d}+\varepsilon\right)q$ many $\mathbb{F}_q$-lines, provided that $q$ is sufficiently large. The same conclusion holds for $\mathbb{F}_q$-irreducible curves that are not geometrically irreducible, since they have only $O(d^2)$ $\mathbb{F}_q$-points. In particular, for sufficiently large $q$, the bound applies to every $\mathbb{F}_q$-irreducible plane curve of degree $d$ when $\operatorname{char}(\mathbb{F}_q)>d$. Our bound is asymptotically sharp. The proof combines Entin's Chebotarev density theorem for varieties over finite fields with the Pippenger–Spencer theorem on covers of nearly regular hypergraphs.