Papers

We show that the toric ideal of the Fano matroid polytope does not have a quadratic Gröbner basis. This resolves in the negative a strong version of White's conjecture from matroid theory. This result was found independently by De Loera, Ferroni, Morales, and Rambau. Our approach is based on a new characterization of regular unimodular flag triangulations, which reduces the problem to an instance of SMT involving boolean and real variables. We then use an SMT solver to prove unsatisfiability. Using this approach, we also show that all 8-element matroids which do not have the Fano matroid or its dual as a minor, with the possible exception of the matroid $T_8$, have toric ideals which admit quadratic Gröbner bases.

Compact graphs are graphs for which the fractional automorphism polytope has no genuinely fractional vertices. This paper proposes a quantum analogue of this idea by evaluating the fundamental magic unitary of the quantum automorphism group on states, which we show to produce a closed convex set of doubly stochastic matrices sitting between the classical automorphism polytope and the full fractional automorphism polytope. Our main result is that the natural quantum analogue of compactness is classical, that is, a quantum compact graph is classically compact. We also relate this set to the quantum orbital algebra and obtain a hierarchy of classical and quantum compactness pseudo notions. The framework recovers familiar consequences of compactness through commutants and suggests quantum analogues of generous transitivity and distance-transitivity. We also isolate examples and open problems indicating where quantum symmetries may strictly refine the classical compactness theory.

We prove a degree-four Sum-of-Squares lower bound for the standard vector-coordinate formulations of mutually unbiased bases. For every dimension $d$ and every proposed number $m$ of bases, we construct a degree-four pseudoexpectation satisfying the orthonormality constraints and the cross-unbiasedness constraints in the quartic equality formulation. The construction is expectation over $m$ independent Haar-random orthonormal bases. We also prove that the same pseudoexpectation satisfies the degree-four localizing constraints for the natural $2\times 2$ Hermitian semidefinite formulation of the cross-coherence inequalities. Consequently, degree-four vector-coordinate SoS cannot refute the existence of $m$ mutually unbiased bases, even when $m>d+1$. In particular, under the two vector-coordinate encodings explicitly described in Randomstrasse101 Open Problem 23, degree-four SoS cannot prove that seven mutually unbiased bases do not exist in $\mathbb C^6$. We contrast this with a centered projector-coordinate Gram formulation, where degree-four SoS already recovers the elementary upper bound $m\le d+1$, giving a simple separation between vector-coordinate and projector-coordinate degree-four relaxations.

We consider a partition of the projective space PG(m + n - 1, K), with K any (commutative) field, into one space of dimension m - 1 while all other spaces of the partition have dimension n - 1. Characterizations of particular partitions of this type are given. This research is motivated by some interesting problems on translation generalized quadrangles. In the paper we apply our results to generalized ovoids and generalized quadrangles. Finally we give some ideas for further research.

Configuration spaces of graphs frequently grow factorially in complexity with the number of particles they parametrize. However, for suitable families of nested graphs $G_\bullet$ with compatible symmetric group actions, Ramos and White prove that, for fixed $k$, the rational homology of the $k$\textsuperscript{th} configuration spaces of $G_\bullet$ has multiplicity stability. In the current work, we derive the stable range and use computer algebra to determine the stable representations on homology for $k=2$ and $G_\bullet$ several families of graphs, including the complete graphs, the complete bipartite graphs on $2n$ vertices, the crown graphs on $2n$ vertices, and the complete tripartite graphs on $2n+1$ vertices. We determine the stable multiplicities for certain irreducible components in the case $k=3$ and $G_\bullet$ the complete graphs.

Let \(G\) be a finite abelian group, and let \(\mu(G)\) denote the least size of a subset \(S\subseteq G\) with \(3\mid |S|\), total sum zero, and no partition into zero-sum triples; put \(\mu(G)=\infty\) if no such subset exists. We prove the exact classification \(\mu(G)=\infty\) precisely for groups of order at most \(8\) and for \(G\cong C_3^2\), while \(\mu(G)=6\) for every other finite abelian group. The cyclic special case gives \(\mu(\mathbb Z_n)=\infty\) for \(1\le n\le 8\) and \(\mu(\mathbb Z_n)=6\) for \(n\ge 9\), answering the corresponding non-partite cyclic question. We also record a higher-uniformity interval construction which explains the large cyclic witnesses as the case \(k=3\) of a general \(k\)-tuple obstruction.

In this paper, we introduce the notions of uniform modulo-recurrence and strong modulo-recurrence. We show that Sturmian words and maximal complexity words are strongly modulo-recurrent. Next, a relationship between the window complexity and the classical complexity of the Thue-Morse word is established. We provide an aperiodic recurrent word such that the window complexity is bounded. We also construct a family of aperiodic recurrent words such that their window complexity $P^w(n)$ is in $O(n^\alpha)$, while at least $n^\alpha$ for infinitely many $n$, where $0<\alpha<1$. Finally, we establish that the window complexity of a uniformly recurrent aperiodic word is unbounded.

Sunflowerability, or the infinite sunflower property, was introduced and studied by Ackerman, Karker and Mirabi as a structural generalization of the well-known \Delta-system lemma for sets. It turns out that for relational Fra\”issé limits with strong amalgamation, this property is equivalent to the so-called galah property, which was introduced by Sullivan and Winkel as an asymmetric variation of indivisibility. This paper is about these two properties and is divided into three parts. In the first part, we show that the conjecture proposed by Ackerman, Karker and Mirabi about the infinite sunflower property in higher dimensions is far from being true by proving that no infinite structure has the infinite n-sunflower property in dimension k for any n, k \geq 2. In the second part, we give a complete characterization of the galah property for Henson directed graphs, homogeneous metric spaces and homogeneous ultrametric spaces, thereby answering the second question asked by Sullivan and Winkel. The third part contains several additional results about the finite sunflower property, including a strengthening of recent results about indivisibility for some classes of undirected graphs obtained by Guingona et al..

We prove a local bijection between alternating sign matrices (ASMs) and descending plane partitions (DPPs) in the refined fibres of Behrend–Di Francesco–Zinn-Justin. The map is constructed by moving a boundary line through the ASM and DPP pictures. At each step only a bounded neighbourhood of that boundary is changed. In growth-diagram language, the boundary states are ordinary ASM row frontiers and shifted DPP path frontiers, and the elementary moves are reversible Fomin-type square rules. The proof checks that overlapping local moves are confluent, that every square is invertible, and that the completed boundary again satisfies the ordinary ASM and DPP coordinate inequalities. The only terminal choice is resolved by a radius-two fan rule on the visible height contour. The same local framework gives a statistic on refined ASMs whose generating function is the DPP degree enumerator. The statistic has a Striker–Fulmek quadratic core \[ Q_{\rm SF}(A)= \sum_{1\le r<s\le n}\ \sum_{1\le b<a\le n} (n-r+1)A_{r,a}A_{s,b}, \] plus a bounded fan-boundary correction and, outside the normal boundary gauge, an explicit compact-potential endpoint term. In the normal gauge this is \[ W_{\rm ASM}^{\rm SF}(A)=Q_{\rm SF}(A)+B_{\rm fan}(A). \] Thus the paper gives both a local ASM–DPP bijection and a statistic-preserving refined \(q\)-enumeration. The supplementary files reproduce selected local checks and the displayed arithmetic examples.

We prove a growth dichotomy for infinite approximate groups, and more generally approximate semigroups, in hyperbolic groups. If \(G\) is a finitely generated hyperbolic group and \(A\subseteq G\) is infinite with \[ A^2\subseteq AX \] for some finite \(X\subseteq G\), then either \(\langle A\rangle\) is virtually cyclic, or \(A\) has positive exponential growth in the ambient word metric. We also introduce a product-growth criterion for the existence of growth rates of approximate semigroups. The criterion applies to hyperbolic groups: if \(G\) is hyperbolic with finite generating set \(S\), then there is a constant \(c_{G,S}>0\) such that \[ |UV| \geq c_{G,S}\,\frac{|U||V|}{n+k+1}, \qquad U\subseteq B_n,\; V\subseteq B_k. \] The linear loss is optimal in order whenever \(G\) contains an element of infinite order. In the free group with its standard generating set one may take \(c_{G,S}=1/4\). We also prove that, in a free group, if \(U\subseteq S_n\) and \(V\subseteq S_k\), then \[ |UV|\geq \left(\frac{2}{3}+\frac{1}{3\cdot 4^{\min\{n,k\}}}\right)|U||V|, \] and this constant is sharp for all \(n,k\).

There exist an absolute constant $c>0$ and arbitrarily large finite sets $A\subset \mathbb{R}$ with $$\left| \left\{x+y+(x-y)^2:\ x, y \in A\right\}\right| \le|A|^{2-c}.$$ Since $x+y+(x-y)^2 \in \mathbb{R}[x,y]$ is a polynomial which is neither additive nor multiplicative, this provides a counterexample for the Elekes-Rónyai problem. The proof combines two amplifications of the same local congruence defect: horizontal amplification over squarefree products of rational primes, and vertical amplification through bounded root-discriminant towers in which those primes split completely. In this way a fixed local density defect becomes macroscopic, producing a power saving. This phenomenon also suggests a broader mechanism for producing similar extremal constructions throughout combinatorics and number theory.

We discover six new families of modular Nahm sums in ranks 3 and 4. Two of them are rank three sums obtained by modifying two of Zagier's rank three examples. Three rank four families are derived by applying the lift-dual operation to the rank three tadpole Nahm sums studied by Milas and Wang, while the other rank four family is found by the constant term method. To prove modularity, we establish Rogers-Ramanujan type identities that express these Nahm sums as infinite products which are modular.

We obtain an optimal proximity bound for integer linear programs in standard form max{cx: Ax=b, x nonnegative integer}, where A is an integer mxn matrix of rank m<n and b is an integer vector. Specifically, we show that the Euclidean distance from any optimal vertex solution of the LP relaxation to a nearest optimal integer solution is bounded by $\sqrt{\det(AA^t)}-1$ and that this estimate is asymptotically tight. We also derive bounds for the optimal integer solutions involving the product function $\prod_{i=1}^{n}(x_i+1)$ and discuss their applications in the knapsack setting.

A skew-Hadamard difference set (SHDS) in a finite group $G$ is a classical combinatorial object with deep connections to design theory, coding theory, group theory, and the construction of Hadamard matrices. Even though the abelian case has been extensively studied – with strong structural constraints known, such as the necessity of $G$ being a $p$-group for some prime $p \equiv 3 \pmod{4}$ – there are still some open questions regarding existence of SHDSs for the abelian case. The non-abelian case remains largely unexplored, despite the known existence of non-abelian SHDSs. In this paper, we establish new necessary conditions on the order and structure of a finite group $G$ that admits an SHDS. These results provide the first general structural restrictions for SHDSs in non-abelian groups. In particular, we prove that if a group $G$ is nilpotent and admits an SHDS, then $G$ is a $p$-group. Our method makes use of the structure of the rational group algebra, and completely avoids the use of the group characters.

In 2018, Hamaker and Reiner introduced weak order for monotone triangles, which extended the usual notion of weak order on the symmetric group. Monotone triangles on $\{1, \ldots, n\}$ are well-known to be in bijection with the set ASM$(n)$ of $n \times n$ alternating sign matrices. Hamaker and Reiner defined weak order on ASM$(n)$ to be induced from weak order on monotone triangles via the standard bijection. Recently, the present authors used an a priori different definition of weak order on ASM$(n)$ to give a combinatorial characterization of the codimension of ASM varieties and to show that the natural K-theoretic representatives of these varieties satisfy a divided difference recurrence. In the present work, we establish compatibility of these definitions of weak order on ASM$(n)$. Additionally, we give three different explicit means of computing weak order covering relations on ASM$(n)$: on ASMs themselves, on monotone triangles in a manner different from that given by Hamaker and Reiner, and on bumpless pipe dreams, which are a newer family of combinatorial objects also in correspondence with ASMs. Finally, using the language of bumpless pipe dreams, we characterize the fibers of the weak order operators, each of which forms a sublattice of the strong Bruhat order on ASM$(n)$.

Cospectral graphs (graphs that share the same eigenvalues) expose the limitations of using the graph spectrum to uniquely identify graphs, and they also help to understand what structural properties a graph spectrum cannot capture. Switching methods, which are standard tools for constructing cospectral graphs, require specific structural and algebraic conditions to hold for the operation to preserve the graph's spectrum. However, there is no guarantee that the obtained cospectral switched graph is non-isomorphic. In this paper we study this isomorphism problem for a recent and prolific switching method to produce cospectral graphs with respect to the adjacency spectra: Wang-Qiu-Hu (WQH) switching. We do so by using common-neighbour multisets associated with a WQH partition, which allows us to derive an external common-neighbour criterion for certifying non-isomorphism after WQH-switching. Then, we apply the new criterion to clique extensions and to weak tensor products, with coclique extensions as a special case. As an application we obtain infinite families of cospectral non-isomorphic graphs, including some known constructions. Finally we extend the conditions of WQH-switching to generalized adjacency matrices and, under an additional degree condition, to Laplacian and signless Laplacian matrices.

A finite subset $X$ of $\mathbb R^d$ is called Ramsey if for every $k$ there exists an $n$ such that whenever $\mathbb R^n$ is $k$-coloured there exists a monochromatic congruent copy of $X$. K\v rí\v z showed that if there is a soluble group of symmetries of $X$ that acts transitively on $X$, then $X$ is Ramsey. Determining which sets are Ramsey is a major unsolved problem. In this paper we show that if there is a finite group of isometries of $\mathbb R^d$ that acts transitively on a set $X$, and also on a set $Y$, then the `prism' formed by $X$ and $Y$ in $\mathbb R^{d+1}$ (meaning the set $X$ together with a translate of $Y$ in the direction perpendicular to $\mathbb R^d$) is itself contained in a finite set on which a group of isometries acts transitively. Moreover, if the initial group of isometries is soluble then so is the final group. This provides a new tool for generating Ramsey sets.

Let \(H=(V,\mathcal E)\) be a finite hypergraph. For positive integers \(p\) and \(q\), the \((p:q)\)-biased discrepancy game on \(H\) is played in complete rounds. In each round, Balancer first claims \(p\) previously unclaimed vertices, and then Unbalancer claims \(q\) previously unclaimed vertices. Let \(B\) and \(U\) be the final sets of vertices claimed by Balancer and Unbalancer, respectively. For an edge \(e\in\mathcal E\), define $D_e = q|B\cap e|-p|U\cap e| = (p+q)|B\cap e|-p|e|$. Thus \(D_e\) measures the deviation of Balancer's share of \(e\) from the density \(p/(p+q)\). In 2005, Alon, Krivelevich, Spencer and Szabó proved a Chernoff-type potential criterion for the unbiased alternating discrepancy game, corresponding to the case \(p=q=1\), and asked for a biased analogue for general $p,q$. In this paper, we prove a complete biased analogue in the complete-round formulation. More precisely, for every finite hypergraph \(H=(V,\mathcal E)\) and every fixed bias \((p:q)\), we give an explicit exponential condition under which Balancer has a strategy forcing $-L_e^- \le D_e \le L_e^+$ for every $e\in\mathcal E$, where \(L_e^+\) and \(L_e^-\) are prescribed edge-dependent target values.

A (strongly) concave composition of an integer $n$ is a sequence of positive integers that is (strictly) decreasing to a point and then (strictly) increasing thereafter, such that the sum of the entries equals $n$. The value at the low point is called the center part. The difference between the number of entries before and after the low point of the sequence is referred to as the rank of the (strongly) concave composition. The rank functions $V_d(m,n)$ and $V(m,n)$ are defined as the number of concave compositions and strongly concave compositions, respectively, of $n$ with rank $m$. By constructing the difference systems that characterize the rank generating functions, we establish monotonicity properties for the rank functions of both strongly concave compositions and concave compositions for all positive integers $n$. Moreover, we also study the monotonicity properties for the rank functions of (strongly) concave compositions with fixed center parts.

The relationship between linear codes in the Hamming metric and projective algebraic varieties has led to deep interactions between coding theory and algebraic geometry, with classical examples such as Reed-Solomon codes and the rational normal curve. On the other hand, the sum-rank metric has recently gained attention due to applications in network coding, distributed storage, and post-quantum cryptography, with linearized Reed-Solomon codes emerging as optimal constructions. Despite recent advances, their structural and geometric properties are still not fully understood, and existing distinguishers remain limited. In this paper, we develop a geometric framework for linearized Reed-Solomon codes by considering a $q$-analogue of the rational normal curve. This yields a geometric characterization for certain parameter choices and reveals that the corresponding sets of points satisfy unexpectedly many $(q+1)$-degree hypersurface conditions. Our approach extends Schur-product-based techniques from the Hamming and rank-metric settings to the sum-rank metric case. Finally, we study the Hilbert function of the associated coordinate ring, providing a detailed description of its behavior and identifying its regularity, which also sheds new light on Gabidulin codes.

Given a square matrix, the permanent is a determinant-like function without signs. In this paper, we study inequalities involving permanents of certain submatrices. We first focus on a family of zero-one totally nonnegative matrices that arise as anti-adjacency matrices of unit interval orders. For these matrices, we prove a collection of inequalities comparing products of permanents of consecutive principal submatrices with products of permanents of parity-selected principal submatrices. We also study a related combinatorial problem involving two families of permutations: a Young subgroup and a set of parity alternating permutations. We construct a bijective map from the first family to the second family, and verify computationally for n at most 13 that each permutation is below its image in Bruhat order. We conjecture that this property holds for all n. If true, this would imply one of the main permanent inequalities for all totally nonnegative matrices in the balanced case. More broadly, we conjecture that the full family of inequalities holds for all totally nonnegative matrices.

We prove that the reversible elementary second order cellular automaton rule 115 is periodic when started on finite initial configurations. We also study some families of finite configurations that have interesting period functions.

We present an algorithm for computing the join of two elements in the weak order of the Coxeter group of type B. This extends Markowsky's algorithm for computing joins of standard permutations to signed permutations, and allows us to confirm a conjecture of Dyer concerning a geometric interpretation of these joins.

A symmetric function is called Schur-positive if it admits an expansion in the Schur basis with nonnegative coefficients. In this paper, we study the Schur-positivity of symmetric functions naturally associated with set partitions, with respect to a descent set function that considers i as descent, if i and i+1 share a block in the partition. The Schur expansion involves hook-shaped Young diagrams, and the corresponding coefficients are given by Touchard-Riordan polynomials, which enumerate matchings by their number of crossings.

Let $\mathcal{H}$ be a family of graphs. A graph is said to be $\mathcal{H}$-free if it contains no subgraph isomorphic to a graph in $\mathcal{H}$. The planar Turán number $ex_{_\mathcal{P}}(n,\mathcal{H})$ is defined as the maximum number of edges in an $\mathcal{H}$-free planar graph on $n$ vertices. In this paper, we determine the exact value of $ex_{_\mathcal{P}}(n,\{K_{4}, \Theta_{6}^{1}\})$ and a tight upper bound of $ex_{_\mathcal{P}}(n,\{K_{4}, \Theta_{6}^{2}\})$.

A critical set in a Latin square of order $n$ is a set of entries in an $n\times n$ array which can be embedded in precisely one Latin square of order $n$, with the property that if any entry of the critical set is deleted, the remaining set can be embedded in more than one Latin square of order $n$. The cardinality of the largest critical set in any Latin square of order $n$ is denoted by $lcs(n)$. In 1978 Curran and van Rees proved that $lcs(n)\leq n^2-n$. In Chapter 4, it is shown that $lcs(n)\leq n^2-3n+3$. Chapter 5 provides new bounds on the maximum number of intercalates in Latin squares of orders $2^\alpha m$ and $2^\alpha m+1$, and a new lower bound on $lcs(4m)$. In Chapter 6 a construction is given which verifies the existence of a critical set of size $\displaystyle{\frac{n^2}{4}} + 1$ when $n$ is even and $n\geq 6$. In Chapter 7 the representation of Steiner trades of volume less than or equal to nine is examined. Computational results are used to identify those trades for which the associated partial Latin square can be decomposed into six disjoint Latin interchanges. Chapter 8 focusses on critical sets in Latin squares of order at most six and extensive computational routines are used to identify all the critical sets of different sizes in these Latin squares.

An edge-cut of a graph is said to be essential if its removal results in a graph with at least two non-trivial components. The essential edge-connectivity of a graph $G$ is the minimum cardinality among all essential edge-cuts of $G$. The spectral gap of $G$ is the difference between its largest and second largest eigenvalues. In this paper, we prove that for any integers $t$ and $r$ with $6\leq r\leq t\leq 2r-3$, the maximum spectral gap among all connected $r$-regular graphs with essential edge-connectivity at most $t$ is equal to $\frac{1}{2}(r+7-\sqrt{(r+7)^2-8t-32})$ when $t-r$ is odd and $\frac{1}{2}(r+6-\sqrt{(r+6)^2-8t-32})$ when $t-r$ is even. We construct a family of connected $r$-regular graphs achieving these bounds.

Given an ordered tuple $\mathbf v=(v_0,\ldots,v_d)$ of vectors in $\mathbb{R}^d$, let $A_{\mathbf v}=[\,v_1-v_0\ \cdots\ v_d-v_0\,]$ be its edge matrix. We prove that, in every finite colouring of $\mathbb{R}^d$, one colour class realizes every prescribed value of the higher characteristic coefficients \[ (c_2(A_{\mathbf v}),\ldots,c_d(A_{\mathbf v})). \] This extends Graham's theorem on volumes, which corresponds to the last coefficient $c_d(A_{\mathbf v})=\det(A_{\mathbf v})$. We also prove a discrete analogue: if $E\subseteq\mathbb{Z}^d$ has positive upper Banach density, then, for some $q\geq 1$, the set of coefficient tuples realized by ordered tuples in $E$ contains \[ q^2\mathbb{Z}\times q^3\mathbb{Z}\times\cdots\times q^d\mathbb{Z}. \] Finally, we show that the ordinary trace $c_1(A_{\mathbf v})$ cannot be added to these conclusions. The proof combines a quantitative directional expansion result for ergodic actions of free abelian groups with a trace calculation for a family of model edge matrices.

Flag-rank-metric codes arise as a natural generalization of rank-metric codes in the context of network communication. While recent research has mainly focused on algebraic and structural properties of these codes, the combinatorial geometry underlying the flag-rank metric remains largely unexplored. In this paper, we initiate a detailed investigation of this geometry. We explicitly determine the size of spheres of small flag-rank radius in the space $\mathrm{U}(n,\mathbb{F}_q)$ of upper triangular matrices over the finite field $\mathbb{F}_q$, and consequently obtain formulas for the size of balls of radius at most $3$. Using these enumerative results, we derive a sphere-packing bound for flag-rank-metric codes and introduce the notion of perfect codes with respect to the flag-rank metric. We observe that no non-trivial perfect flag-rank-metric codes exist in $\mathrm{U}(n,\mathbb{F}_q)$ for $n\in\{2,3\}$. We then investigate the possible parameters of perfect codes in higher dimensions. For minimum distance $3$, we obtain a characterization in terms of the codimension of the code, and show that suitable maximum flag-rank distance codes with minimum distance $3$ yield non-trivial perfect codes. For minimum distances $5$ and $7$, we derive explicit quadratic and cubic conditions, respectively, that any perfect code must satisfy. Finally, using asymptotic estimates for balls of fixed radius, we prove that for fixed length $n$ and $\delta\in\{3,5,7,9,11\}$, perfect linear flag-rank-metric codes with minimum distance $\delta$ do not exist over $\mathbb{F}_q$ for all sufficiently large $q$.

Balanced words on a finite alphabet are those words in which every letter of the alphabet occurs the same number of times. The notion of descents and major index extends in a natural way to words. It is known that the bivariate generating polynomials for descents and major index over balanced words on the alphabet $[k]$ with $n$ occurrences each is palindromic, but a bijective proof has been missing even for balanced binary words. We give an explicit bijection proving this result. For permutations (which are also balanced), our bijection is different from the complementation map. We also show that for balanced binary words, this bijection simultaneously flips the ascent and comajor index as well.