Papers

We present a generating-function approach to the topological entropy of finite strongly connected digraphs, working throughout with digraphs in which loops are allowed but multiple edges are excluded. Using dominant singularities of path-generating functions, we recover by new analytic–combinatorial arguments the known first and second positive-entropy minimizers from the previously studied loopless spectral setting, and extend the corresponding extremal statements to the present framework. For the class $\mathcal{SC}_{m+1}(m)$ of strongly connected digraphs with $m$ vertices and $m+1$ edges, we introduce a unified $(t,k_1,k_2)$-butterfly parametrization. The entropy of $\mathcal{B}^{\,t}_{k_1,k_2}$ depends only on $(k_1,k_2)$ and is determined by the unique root $R\in(0,1)$ of $1-z^{k_1}-z^{k_2}=0$ via $h=-\ln R$. This parametrization yields a detailed entropy hierarchy within $\mathcal{SC}_{m+1}(m)$. We introduce the Pyramidal Entropy Diagram, determine the entropy order completely for $m\leq 7$, and identify its first structural bifurcation at $m=8$. We further establish maximal stable initial and terminal segments consisting of ten entropy minima and two entropy maxima, respectively, and derive an explicit formula for the minimum order required to realize a positive entropy not exceeding a prescribed threshold.

Answering a question of Chepoi and Hagen, we give two constructions of bounded degree CAT(0) square complexes that cannot be isometrically embedded into any finite product of trees. The first is based on Burling graphs and has degree at most five, which is optimal. These square complexes topologically embed into $\R^3$ since we further prove that every CAT(0) square complex whose vertices have degree at most five can be topologically embedded into the product of a line and a star. It turns out that in this setting, Burling graphs are the only obstruction: we prove that CAT(0) square complexes that topologically embed into $\R^3$ and whose crossing graph forbids some induced Burling graph can be isometrically embedded into a finite product of trees. Our second CAT(0) square complex has degree at most six and its crossing graph forbids an induced Burling graph. Of independent graph-theoretic interest, along the way we construct intersections of chordal and interval graphs with arbitrarily large girth and chromatic number. We also discuss connections to nice labellings of event structures.

We give a deterministic polynomial-time algorithm that, given rational Hermitian matrices $H_1,\dots,H_N$ of rank at most one, finds signs $s\in\{\pm1\}^N$ with $\|\sum_i s_i H_i\|\le 13\|\sum_i H_i^2\|^{1/2}$. As a corollary, for vectors $v_i$ with $\sum_i v_iv_i^*=I$ and $\|v_i\|^2\le\delta$, the signs yield a partition $[N] = S_1 \cup S_2$ such that each part satisfies $\|\sum_{i \in S_j} v_i v_i^* - \frac{I}{2}\| \leq \frac{13}{2}\sqrt\delta$ for $j = 1,2$. This gives a deterministic polynomial-time algorithm for the Kadison–Singer problem, in Weaver's equivalent discrepancy-theoretic $\mathsf{KS}_2$ formulation, with a universal constant.

We consider weighted lattice point enumeration in lecture hall order polytopes. We observe that these half-open polytopes are closed under weight-lifting for a large class of polynomial weights, including monomials and weights given by binomial coefficients. For rooted trees, we prove that the corresponding (weighted) $h^\ast$-polynomial is real-rooted thereby complementing previous results of Savage-Visontai and Brändén-Leander.

A skew morphism on a finite group $A$ is a permutation $\varphi$ on $A$ that fixes the identity element of $A$ and for which there exists an integer-valued function $\pi:A\to\mathbb{Z}_{|\varphi|}$ such that $\varphi(xy)=\varphi(x)\varphi^{\pi(x)}(y)$ for all $x,y\in A$. The kernel of $\varphi$ is the subgroup $\Ker\varphi=\{x\in A\mid \pi(x)=1\}$, and the index $[A:\Ker\varphi]$ is called the skew-type of $\varphi$. In this paper we construct, classify and enumerate the skew morphisms of skew-type four on cyclic $2$-groups. Our main results give explicit formulas for all such skew morphisms and closed-form expressions for their numbers.

Spectral Turán-type problems ask how the absence of prescribed subgraphs constrains the spectral radius of a matrix associated with a graph. Given a family of graphs $\mathcal{F}$, a graph is called $\mathcal{F}$-free if it contains no member of $\mathcal{F}$ as a subgraph. The theta graph $\theta(l_1,\ldots,l_k)$ consists of $k$ internally disjoint paths of lengths $l_1,\ldots,l_k$ with two common end vertices. In this paper, we study two spectral Turán-type extremal problems for the signless Laplacian spectral radius. First, among all $\{C_3,C_4\}$-free graphs of fixed order with no pendant vertices, we determine the maximum signless Laplacian spectral radius and uniquely characterize the extremal graph attaining it. The extremal structure exhibits a parity phenomenon: odd and even orders give rise to two distinct graph families. These results, in particular, sharpen a recent general upper bound for this class given by Liu and Wang (2026). Next, we obtain the corresponding extremal results for all $\{\theta(1,2,2),\theta(1,2,3)\}$-free graphs of fixed size with no pendant vertices when the size is congruent to $1$ modulo $3$ and $2$ modulo $3$, again obtaining unique but structurally different maximizing graphs in the two cases. Together with the previously known result for sizes congruent to $0$ modulo $3$ by Liu and Wang (2026), this completes the fixed-size problem across all three congruence classes modulo $3$.

For a nontrivial finite abelian group $G$, let $\nu(G)$ be the smallest integer $\ell$ such that every zero-sum free sequence $T$ over $G$ of length at least $\ell$ has the following property: all nonzero elements of $G$ that do not occur as a subsequence sum of $T$ lie in a proper coset of some subgroup of $G$. It is easy to check that $\mathsf d (G)-1 \le \nu (G) \le \mathsf d (G)$, where $\mathsf d (G)$ is the small Davenport constant of $G$. A conjecture by Gao from the year 2000 stated that equality should always hold at the lower bound. This conjecture has since been confirmed for many families of groups (including all p-groups and groups of rank at most two). In the current note, we disprove the conjecture.

The forced colouring function of a graph gives the probability that a random assignment of colours to a random subset of vertices can be extended, by a simple local process called forcing, to give a proper colouring of the whole graph using the same set of available colours. This is a polynomial for each fixed number of colours, and was introduced as a subject for research on the general theory of graph polynomials. In this paper we establish its fundamental properties and give combinatorial interpretations of its derivatives at two particular points. We also prove that the problem of computing its value at any specific point in a certain interval is #P-hard.

We determine exactly how harmonic sums, taken over integers with a given number of occurrences of a fixed block of digits, depend on that number of occurrences. Language factorizations, combined with stochastic radix expansions, relate these harmonic sums to the iteration of an operator whose eigenvectors are the Lebesgue measure and distributional derivatives of singular measures. The dual picture is given by a Riesz basis of eigenpolynomials in a suitable Hardy space. The resulting modal expansion admits a natural interpretation as a block-directed Euler-Maclaurin formula interpolating between Euler-Maclaurin and Taylor expansions.

We give new bounds for list sizes of random linear codes at capacity, max loads of linear hash functions, and Furstenberg sets, over every finite field $\mathbb{F}_q$. 1. Random linear codes over $\mathbb{F}_q$ with rate $1 - H_q(p) - \epsilon$ are $(p, O(q H_q(p)/\epsilon))$-list decodable with high probability for all values of $p, q, \epsilon$, including the high error regime. This nearly matches the list size lower bound of $H_q(p)/\epsilon$ due to Guruswami, Li, Mosheiff, Resch, Silas, and Wootters [IEEE Trans. Inf. Theory 2022]. Our bound is the first uniform improvement for $q > 2$ since Guruswami, Håstad, and Kopparty [STOC 2010]. 2. Linear hash functions over $\mathbb{F}_q$ hashing $n$ balls to $n$ bins achieve maximum load $O(q \ln \ln q / {\ln q}) \cdot \ln n / {\ln \ln n}$, both in expectation and with probability $1-o(1)$. This nearly matches the lower bound of $\ln n / {\ln \ln n}$. Previously, only a polylogarithmic upper bound was known for $q > 2$, due to Alon, Dietzfelbinger, Miltersen, Petrank, and Tardos [J. ACM 1999]. We reduce list decodability and linear hashing to strong Furstenberg set lower bounds, which we prove using a new polynomial method of multiplicity gaps. While previous polynomial methods analyze a set $S$ by studying polynomials that vanish on it, we consider polynomials that vanish everywhere, but with higher multiplicity inside $S$ than outside.

In this note we announce the limiting shape for the height function of a uniformly distributed alternating sign matrix (equivalently, a six-vertex model with equal weights and domain-wall boundary conditions)

Cladograms of size $n$ are unrooted binary trees whose leaves are labelled from 1 to $n$. Aldous introduced in 2000 a Markov chain on cladograms, a step of which consists of removing a leaf uniformly at random and reinserting it on a uniformly chosen edge. We introduce a coupling for this walk, which follows multiple colored subtrees in parallel. We go around the lack of independence of the colored components by finding a relevant statistic, namely the sum of the squares of the sizes of all colored components, which we prove has a drift. We deduce that the mixing time of the walk is of order $n^2$, solving a conjecture of Aldous.

Let $\mathcal S(T)$ be the adjacency spectral center of a tree $T$, and let $\mathcal C(T)$ be its characteristic set. We determine the largest possible separation $d(T) := \operatorname{dist}_T(\mathcal{S}(T), \mathcal{C}(T))$ among trees of every order $n\ge3$. Writing $\Delta_n:=\max_{|V(T)|=n}d(T)$, we prove $\Delta_n=0\quad(3\le n\le11),\quad \Delta_{12}=1$, and $\Delta_n=\left\lfloor\frac{n-11}{2}\right\rfloor \quad(n\ge13)$. The argument rests on a simple opposition between two rooted-tree weights. An endpoint-rooted path minimizes adjacency spectral radius, but maximizes bottleneck Perron value. A one-sided replacement by a path therefore cannot decrease the distance between the two centers. Quantitatively, this gives the sharp estimate $|V(T)|\ge 2d(T)+11 \quad(d(T)\ge2)$. A preliminary six-vertex barrier shows that disjoint center sets require at least twelve vertices, and the four-leaf broom is extremal for every $n\ge12$.

Burson and Eichhorn proposed infinite and finite coefficientwise non-negativity conjectures for products arising from copartitions. We obtain several further results. First, both products admit decompositions into elementary local blocks, and the finite conjecture reduces exactly to its diagonal specialization. The finite conjecture is proved when the first truncation parameter is one or when the two residue parameters are equal. We also prove that every finite product has non-negative coefficients below the third shifted signed exponent. For fixed finite parameters, the coefficient sequence is shown to be eventually quasipolynomial; an explicit period bound, an explicit onset for the quasipolynomial formula, and the leading term on every residue class are obtained. This yields eventual strict positivity, apart from forced odd-degree zeros in one solved diagonal case. For the infinite conjecture, we prove non-negativity under the broader condition $a\equiv b\pmod m$, which includes the known case $a=b$. Finally, for arbitrary $b\mid a$, we improve the uniform initial non-negative range from degrees below $a+m$ to degrees below $a+2m$.

We devise a polynomial-time $3.159$-approximation algorithm for the metric unsplittable Capacitated Vehicle Routing Problem. We build on the Relative Greedy Algorithm suggested by Traub (2025), which can be considered as a variant of the LP rounding algorithm of Friggstad, Mousavi, Rahgoshay, and Salavatipour (2025). Our main ingredient is the Average Greedy Algorithm, a new algorithm that controls both tour costs and the coverage of clients with high demand. This additional control enables a sharper averaging argument for the cost of subsequent greedy choices. Similarly to Zhao and Xiao (2026), combining the Average Greedy with variants of tour partitioning and a matching algorithm yields the final approximation guarantee.

Hall algebras can be associated with a broad class of combinatorial structures through the theory of 2-Segal sets. In this paper, we study the Hall algebras arising from the 2-Segal sets of rooted trees, undirected graphs, and directed graphs. In each case, we establish an analogue of Green's theorem giving a twisted bialgebra structure to the Hall algebra, describe the primitive elements, and derive a presentation by generators and relations. As an application, we realize the Hall algebra of an undirected graph as the cohomology ring of a topological space. In the case of directed graphs, we introduce the Hall polynomial, defined as the Poincaré polynomial of the space of primitive elements. The Hall polynomial is an invariant of the underlying undirected graph which we show to be closely related to the Tutte polynomial. We furthermore give examples of graphs with equal Tutte polynomials but distinct Hall polynomials showing thus that the Hall polynomial encodes different information from that of the Tutte polynomial.

We classify the labelled final layer orders of ordinary orthogonal 2 x 2k maps whose mountain-valley assignments are periodic with period two in each crease family. For k >= 2, local flat-foldability leaves 16 of the 64 formal period words. Eight pleat words have a unique labelled state. The remaining eight words reduce, under labelled symmetries, to two constant-row families described by row pivots. For the canonical word MMMMVV, an ordered pivot pair (a,b) is realizable exactly when a = 1, a = m, or a = b, where m = 2k - 1. For MVMMMM, realizability is equivalent to BR(a) = BR(b). In both families each compatible ordered pivot pair determines a unique labelled state. The resulting state counts are 0, 1, 6k - 5, and 4k - 3. The case k = 1 is treated separately because two formal period bits have no physical crease carriers.

The ordered Ramsey number $r_<(G,H)$ of ordered $k$-graphs $G$ and $H$ is the least integer $N$ such that every red-blue edge-coloring of the naturally ordered complete $k$-graph on $[N]$ contains a blue ordered copy of $G$ or a red ordered copy of $H$. We prove that there is an absolute constant $c>0$ such that, for every integer $d\ge1$, there is a constant $C_d>0$ for which every weakly $d$-degenerate ordered $3$-graph $H$ on $t$ vertices satisfies \[ r_<\bigl(H,K_3^{(3)}(n)\bigr) \le t\,2^{C_d n^{2-c/d}} \] for every positive integer $n$. This resolves a problem posed by Balko and Vizer (SIAM J. Discrete Math., 2022) in a stronger form. Furthermore, we show that the weak-degeneracy hypothesis cannot be replaced by bounded standard degeneracy. In particular, for every sufficiently large $n$, there exists a $1$-degenerate ordered $3$-graph $F$ on at most $2^{O(n)}$ vertices such that $r_<\bigl(F,K_3^{(3)}(n)\bigr)>2^{\Omega(n^2)}.$

We study three plane-partition enumerators arising from Schreier-Aigner's quasi-symmetry classes. Their realizations as lattice-point enumerators, together with staircase translations of interior lattice points, yield factorizations by Ehrhart-Macdonald reciprocity. We determine the consecutive linear factors, the parity and degree of the residual polynomials, and explicit divisibility bounds for their coefficient denominators. The denominator argument includes the half-integral translation required by the second-kind classes. We also derive a corrected size-five formula for the symmetric second-kind class. Exact computations verify irreducibility of the quasi-symmetric residual polynomials for every size from $3$ to $24$.

Grünbaum asked whether every planar convex body admits, for every $0\leq t\leq 1/4$, two orthogonal lines cutting it into pieces with cyclically ordered areas $t,t,1/2-t,1/2-t$. Bárány posed the analogous question for well-behaved planar measures and conjectured that the answer there is negative. We confirm Bárány's conjecture in a particularly robust form: for every fixed $0<t<1/4$ we construct smooth, strictly positive, centrally symmetric, strongly log-concave measures arbitrarily close to the standard Gaussian for which the prescribed partition does not exist. In contrast, we prove that the partition exists for every $t$ whenever the measure is invariant under an orientation-reversing affine involution. We also exhibit a $96$-point counterexample for which no pair of perpendicular lines produces cyclic counts $8,8,40,40$.

In this article, we study $2$-$(v,k,\lambda)$ designs $\mathcal{D}$ admitting a flag-transitive almost simple automorphism group $G$ with socle one of the Mathieu groups. In conclusion, we obtain all such $2$-designs with explicit constructions with appropriate references to known designs. To our knowledge, we obtain $101$ newly-constructed flag-transitive $2$-designs.

The recently established duality between tensor, symmetric and exterior products of uniform matroids on the one hand, and abstract (bi-)rigidity matroids on the other hand, connects theorems and open questions from both areas, previously thought unrelated. In particular, a 1981 question of Mason asks if any two uniform matroids admit a freest product. Via duality, its reformulation due to Cruickshank, Jackson, Jordán and Tanigawa asks if the generic birigidity matroid is the freest abstract birigidity matroid for its parameters. A related conjecture of Jackson and Tanigawa asks if the generic $2$-hyperconnectivity matroid is the freest $\{K_4,K_{3,3}\}$-matroid. We show that these problems can be addressed effectively, and often solved completely for the class of linearly representable matroids. To this end, we introduce star-basis normal forms that allow to compare representations of abstract (bi-)rigidity matroids over the same field, resulting in a refinement of the weak order relation on the underlying matroids. Utilizing it, we prove that the generic birigidity matroid is the freest linearly representable abstract $(a,b)$-birigidity matroid. This confirms Mason's conjecture for linear matroids. We prove that every representable abstract $2$-rigidity matroid admits a rigidity matrix representation. This is a strengthening of the maximality property of the generic $2$-rigidity matroid. We also prove that every representable abstract $2$-rigidity matroid in which every copy of $K_{3,3}$ is a circuit admits a hyperconnectivity matrix representation. It follows that the generic rigidity and hyperconnectivity families $\mathcal{R}_2$ and $\mathcal{H}_2$ are the only linearly representable $2$-rigidity families.

An $A$-module $E$ is annihilator multiplication if the annihilator of each element equals that of $IE$ for a finitely generated ideal $I$. We characterize rings for which every faithful module has this property as the commutative quasi-Frobenius rings, and rings for which every module has the property as the Artinian principal ideal rings. Both characterizations reduce to two-generated modules. Over a reduced ring with finitely many minimal primes, faithful annihilator multiplication modules are exactly the regular-torsion-free modules, and principal ideals suffice in the definition. An ascending chain condition on annihilator ideals gives finite detection of the module annihilator, yielding localization and graph rigidity results. We also prove equality of associated primes with those of the faithful quotient and establish projective tensor and trace characterizations. Over local square-zero rings, the property is equivalent to nonsingularity of a bilinear multiplication map. A projective dimension argument gives a sharp length bound, attained by explicit faithful indecomposable nonprojective modules whose endomorphism rings are computed. Every cyclic submodule of these examples embeds in the ring, although the whole module is not torsionless. Support, hereditary torsion, and amalgamation criteria connect these structural results with further module constructions.

For $n\geq3$, the group $\mathrm{SL}_n(\mathbb Z)$ has property $(T)$, so every finite generating set has a positive Kazhdan constant. However, it was recently shown that the infimum of these constants over all finite generating sets is $0$. This naturally raises the question of whether the infimum remains zero when the cardinality of the generating sets is bounded in advance. We prove that the infimum of the Kazhdan constants of $\mathrm{SL}_n(\mathbb Z)$ over all two-element generating sets is $0$ for every $n\geq3$.

Factor complexity counts the distinct factors of each length in an infinite word, while palindromic complexity counts those invariant under reversal. For recurrent aperiodic words with reversal-closed language, the total number of palindromic factors in two consecutive lengths is at most the one-step growth of factor complexity plus two. We prove that equality is forced whenever the factor complexity at a given length does not exceed three halves of that length plus one. We construct examples showing that the bound is optimal. We also obtain an adaptive local criterion and consequences for reversal-closed quasi-Sturmian words and palindromic defect.

We study the augmented Zarankiewicz problem, in which disjoint pairs of cells are added to a binary matrix with no all-one $2\times2$ submatrix. The pairs must satisfy compatibility conditions, and the objective counts each original occupied cell and each added pair once. We show that starting with a maximum $C_4$-free matrix can lower the final optimum, answering a question of Qi, Cui, and Xu. Let ${z_A}(m,n)$ be the optimum over all $C_4$-free initial matrices, and ${z_L}(m,n)$ the optimum when the initial matrix must have the maximum number of occupied cells. As $n\to\infty$ with $n\le m=o(n^2)$, we prove \[ {z_A}(m,n)-{z_L}(m,n)\ge\left(\frac1{30}-o(1)\right)mn \] and determine the sharp second-order term: \[ {z_A}(m,n)=\frac{mn}{3}+\left(\frac1{\sqrt6}+o(1)\right)n\sqrt m. \] An explicit construction gives a separation at $m=n=1893$. We also find a sharp density threshold: when $n\to\infty$ and $m/n^2\to c>0$, the limited density ${z_L}(m,n)/(mn)$ tends to $1/3$ if and only if $c\ge1/12$. The proofs combine density and stability estimates, combinatorial constructions, and an exact polynomial certificate.

We introduce new techniques for determining combinatorial properties of sets of multiple recurrence by considering weighted averages with quickly growing weights. Our main result is a far-reaching generalization of Szemerédi's Theorem which additionally confirms a conjecture of Bergelson-Moreira-Richter and contains as special cases both the Polynomial Szemerédi Theorem due to Bergelson-Leibman-Lesigne and the fact that if $f$ belongs to a broad class of smooth functions and satisfies $x^{d-1}\prec f(x)\prec x^d$ for some $d\in \mathbb{N}$ then for any $\ell\in \mathbb{N}$, any invertible measure preserving system $(X,\mathscr{B},\mu,T)$, and any $A\in \mathscr{B}$ with $\mu(A)>0$, the set $\{n\in \mathbb{N}: \mu(A\cap T^{-[f(n)]}A\cap T^{-2[f(n)]}A\cap \cdots\cap T^{-\ell[f(n)]}A )>0\}$ is thick, meaning that it contains arbitrarily long intervals of natural numbers. Additionally, we formulate and prove a generalization to weighted averages of Boshernitzan's criterion for uniform distribution which we use in the proof of our main result.

We prove that if we take a rooted product of a circulant graph with universal perfect state transfer with a path of fixed length whose end edge is weighted with a transcendental number, then there is pretty good state transfer between any pair of endpoints of these paths. As a consequence, in a path with an even number of vertices with transcendental weights on the two edges incident to the endpoints, there is pretty good state transfer.

We study diagonal billiard trajectories inside the Young diagram of an integer partition $\lambda$. A trajectory has slope $\pm 1$, passes straight through sides shared by adjacent cells, and reflects from the exterior boundary until it closes. Let $\sigma(\lambda)$ be the number of closed orbits. This extends the mirror-curve model of Chokwe sona sand drawings studied by Gerdes from rectangular grids to arbitrary Young diagrams. Let $G_\lambda$ be the cell-adjacency graph of $\lambda$, with its natural planar embedding. We identify the billiard orbits with the components of the medial link of $G_\lambda$, and deduce that $\sigma(\lambda) = 1 + \dim \mathcal{B}(G_\lambda) = \mathrm{nullity}\, L(G_\lambda)$ over $\mathbb{F}_2$, where $\mathcal{B}$ is the binary bicycle space and $L$ the mod-2 Laplacian. Writing $\lambda^\square$ for the diagram obtained by deleting the first row and column of $\lambda$, we further prove $\sigma(\lambda) = 1 + \mathrm{nullity}_{\mathbb{F}_2} A(G_{\lambda^\square})$. For rectangles this recovers Gerdes' formula $\sigma(n^m) = \gcd(m,n)$ via identities for Fibonacci polynomials over $\mathbb{F}_2$, and in general it gives the characterization: $\sigma(\lambda) = 1$ if and only if $\lambda^\square$ has an odd number of domino tilings. Using the checkerboard bipartition of $\lambda^\square$, we decompose $\sigma(\lambda) - 1$ into a color-imbalance term, related to the BG-rank of Berkovich-Garvan, and an even rank-deficiency term. This yields parity restrictions and lower bounds for the orbit number, and shows that for any fixed $d$, asymptotically all partitions have more than $d$ orbits. We also prove that $\sigma(\lambda)$ is at most the Durfee length of $\lambda$, determine $\sigma(n, n-1, \ldots, 1) = \lceil n/2 \rceil$ for staircase partitions, and show that the adjacency-nullity formula is independent of the ground field.

We study the minion homomorphism poset of multisorted Boolean clones. Our main result completely determines the subposet induced by products of Boolean clones: every inequality between prod- ucts is induced by inequalities between their Boolean factors. Furthermore, we determine the minion cores of all products of Boolean clones, thereby identifying canonical representatives of their minion homomorphic equivalence classes.