Peer Revenue Fully funded

Papers

Fresh from arXiv, typeset properly. Highlighted words trade on the market.

Mathematics Combinatorics

math.CO Watch Combinatorics (sign in to use)

Wednesday 9 September

Combinatorics · Cross-listed from math.AG

The Reye geometry inside the 64 lines of the Schur quartic

We identify the classical geometry hidden in the Naskręcki–Pokora $(24_4,32_3)$ configuration on the Schur quartic. Using Höhn's identification of the $24$ selected lines with the $24$ roots of $D_4$, the antipodal involution on the roots induces a fixed-point-free quotient of the incidence configuration, and this quotient is precisely the classical Reye configuration. We also determine the symmetry of the complete $64$-line incidence geometry: its automorphism group has order $4608$, the two Naskręcki–Pokora configurations form a single orbit, and the stabilizer of either has order $2304$ (projectively, $576$). The $64$ lines extend canonically to a $176$-line arrangement carried by six projectively equivalent Schur quartics, with $176=16+16+9\cdot16$ and induced surface permutation group $S_3\times S_3$. Finally, the antipodal quotient itself extends coherently through this six-quartic geometry: on each Schur quartic it produces two Reye configurations sharing the same $16$-element incidence skeleton, and on the full $176$-line arrangement it gives a compatible global quotient. This reveals a precise incidence-theoretic connection with classical desmic geometry, while showing that this connection is not a literal identification with the two Reye configurations arising from the classical desmic construction in $P^3$.
Read the full abstract

Combinatorics · Cross-listed from math.AG

Long range divided differences, clusters, and Graham-positivity

We study torus-orbit closures in the type $A$ complete flag variety naturally associated to cones in the positive cluster fan, together with their left $S_n$-translates. The torus-equivariant degree maps can be computed via composites of long-range divided difference operations encoded by noncrossing alternating forests, and we give combinatorial algorithms to expand the torus-equivariant homology classes into Graham-positive combinations of Schubert cycles. As applications we obtain combinatorial Graham-positive Schubert cycle expansions for all torus-invariant curves (generalizing the AJS-Billey formula for torus-fixed points), generic torus-orbit closures, and Richardson varieties for Bruhat intervals $[w,wc']$ where $c'\le s_{n-1}s_{n-2}\cdots s_1$. Projecting to Grassmannians we also obtain Graham-positive Grassmannian Schubert cycle decompositions of torus-orbit closures associated to lattice path matroids on permuted ground sets.
Read the full abstract

Combinatorics · Cross-listed from quant-ph

Perfect $(s,r)$-state transfer

Much work has been done in the last two decades on the topic of quantum state transfer in a quantum spin network. One can model such a system of interacting qubits using an undirected graph, and studying vertex-to-vertex dynamics. This setup has recently been relaxed to allow for dynamics between linear combinations of two vertex states, i.e.\ from $\mathbf u = \mathbf e_a + s \mathbf e_b$ to $\mathbf \mu=\mathbf e_{\alpha} + r \mathbf e_{\beta}$, where $r=s$ is either $-1$ (which corresponds to pair state transfer) or $+1$ (which corresponds to plus state transfer), or more recently $r=s$ is taken to be any real number (which corresponds to $s$-pair state transfer). Here, we broaden the investigation of $s$-pair state transfer to \textit{perfect $(s,r)$-state transfer}, which is perfect state transfer from $\mathbf u = \mathbf e_a + s \mathbf e_b$ to $\mathbf \mu=\mathbf e_{\alpha} + r \mathbf e_{\beta}$ (up to some dilation) where $r,s\in \mathbb C$. We identify infinite families of graphs with perfect $(s,r)$-state transfer and provide characterizations of cases when $|r|= |s|$ and when $|r|\neq |s|$, showing situations when the degree of entanglement between vertex states is preserved, and when it is not preserved. The latter is particularly important as it represents perfect state transfer from an entangled pair of qubits to another one where the degree of entanglement need not be the same\mdash in fact, it can be set up so as to “boost” (increase) entanglement. We provide an algorithm that finds the vector with two nonzero entries that maximizes the fidelity of transfer for a fixed time $t$ starting from a given $s$-pair state $\mathbf u$. Finally, we provide a sensitivity analysis, with respect to readout time errors, of perfect $(s,r)$-state transfer.
Read the full abstract

Combinatorics · Cross-listed from math.RT

The $E_6$ Restricted Hyperplane Arrangement and its $E_7$ Shadow: Weyl Transport on a Minuscule Bruhat Poset

We study the restricted fan cut inside the dual fundamental Weyl chamber by the weights of a $27$-dimensional minuscule representation of $E_6$; the two such representations are dual and give the same arrangement. Only $11$ of the $27$ weights have kernels meeting its interior, and we prove that they determine the entire fan. It has exactly $14$ chambers and $18$ extreme rays, every chamber is a six-dimensional simplicial cone, and we determine all facets, rays, and incidence relations. The chamber count was previously obtained by Diaconescu and Entin; the simplicial structure, extreme rays, and incidence data are new. The geometry of the $27$ lines on a cubic surface then explains and organizes the resulting chamber architecture. We also enumerate all faces, compute both characteristic polynomials—the arrangement is not supersolvable—together with lattice indices and projective chamber volumes, and describe the oriented matroid. Our main result is representation-theoretic. A distinguished $14$-element visible subposet of the minuscule $\mathbf{56}$ of $E_7$, defined entirely inside $E_7$, has Hasse diagram equal to the chamber adjacency graph of the $E_6$ arrangement. Three canonical $7+7$ splittings of it, of types $A_7$, $D_7$, and $E_7$, are the visible traces of Levi-center $\mathfrak{u}(1)$-charge decompositions of the $\mathbf{56}$ and reproduce the three level-$8$ decompositions on the $E_6$ side. More strongly, the simple-root labels on its covers, transported by minimal-length coset representatives, recover chamber by chamber all six facets and, globally, the $11$ active weight hyperplanes and the boundary walls of the dual Weyl chamber. Thus the $E_7$ shadow records not merely the chamber graph but, once matched with the independent $E_6$ classification, the full local wall architecture of $I(E_6,\mathbf{27})$.
Read the full abstract

Combinatorics

The maximum spectral radius of outerplanar and planar $k$-uniform hypergraphs

For an integer $k\ge3$, a $k$-angulation is a simple $2$-connected outerplane graph whose interior faces are bounded by $k$-cycles, and a closed $k$-angulation is a simple $2$-connected plane graph all of whose faces, the outer face included, are bounded by $k$-cycles; the face hypergraph of either is the $k$-uniform hypergraph whose edges are the vertex sets of those faces. For $k=3$ these are the outerplanar and planar hypergraphs of Ellingham, Lu and Wang, who determined the outerplanar extremal hypergraph for large $n$ and conjectured the planar one. In this paper, we determine the extremal hypergraphs in both classes for every $k$. In the outerplanar case, for all sufficiently large admissible $n$, it is the fan, in which a single vertex lies on every face, and the maximum equals $(4f)^{1/k}(1+o(1))$ with $f=(n-2)/(k-2)$. In the planar problem the maximum has order $n^{1/3}$ when $k=3$ and order $n^{2/k}$ when $k\ge4$. For $k\ge4$ the extremal hypergraphs are the face hypergraphs of the balanced theta graphs, in which two vertices are joined by internally disjoint paths and every face is a $k$-cycle through both: for $k=4$, where the closed $4$-angulations are the quadrangulations of the sphere, this holds for every $n\ge5$, the extremal hypergraph being $\mathcal{H}(K_{2,n-2})$, and for $k\ge5$ for all sufficiently large admissible $n$. For $k\ge6$ the extremal hypergraph is not unique: when the number of faces is even there are exactly $\lfloor(k-2)/2\rfloor$ of them up to isomorphism. For $k=3$ two vertices of a plane triangulation lie on at most two common faces, the balanced theta graphs are unavailable, and the extremal hypergraph is instead, for all sufficiently large $n$, the face hypergraph of $K_2+P_{n-2}$; this confirms a conjecture of Ellingham, Lu and Wang.
Read the full abstract

Combinatorics

The 2-Adic Valuation of the Order of the All-Ones Class in the Sandpile Group of a Square

Place one grain at every nonsink vertex of the wired $n\times n$ square, and let $L(n)$ be the order of this operation in the sandpile group. Thus $L(n)$ is the least positive $q$ for which $q$ uniform grain layers form an integral combination of toppling moves. We prove that, for every $n\ge1$, \[ \nu_2(L(n))= \begin{cases} 2,&n=1,\\ 1,&n\ge2\text{ even},\\ \nu_2(n+1)+2,&n\ge3\text{ odd}. \end{cases} \] For even squares, this follows from the domino–sandpile results of Florescu, Morar, Perkinson, Salter, and Xu, completed by a short parity observation. For odd squares, a unimodular cyclic basis identifies the folded cokernel with a quotient by two shifted Chebyshev polynomials and sends the all-ones class to $1$. Its order is determined by the constant part of this polynomial ideal, not just by a determinant. Two normalized Euclidean remainders reduce to consecutive Fibonacci polynomials over $\mathbb F_2$, giving the exact valuation.
Read the full abstract

All authors Turgay Akyar, Artem Beliakov, Konstantin Delchev, Nikita Kalinin, Ernesto Lupercio, Higinio Serrano, Mikhail Shkolnikov, Daniel Tabares, Nikolai Terekhov

Combinatorics · Cross-listed from cs.DS

Subexponential Approximation of the Permanent in Deterministic Polynomial Time

We give the first deterministic polynomial time algorithm that approximates the permanent of arbitrary nonnegative rational matrices within a subexponential factor. For a matrix of order $n$, the approximation factor is \[ \exp\!\left(O\!\left(\frac{n(\log\log n)^2}{\log n}\right)\right)=\exp(o(n)). \] All previously known deterministic polynomial time guarantees for unrestricted inputs had approximation factors $\exp(\Omega(n))$. Our proof uses convex optimization to tighten an upper bound on the permanent. The bound is based on weighted sums over all matchings in a bipartite graph representing the matrix, and correlations between unmatched vertices control its error. We approximate these sums deterministically using correlation decay and a bound on the effect of vertex deletion.
Read the full abstract

Combinatorics

Unimodality shenanigans in Ehrhart theory

We show the existence of counterexamples to a four-decade-old conjecture attributed to Stanley concerning the unimodality of $h^*$-polynomials of IDP polytopes. As additional applications of our main constructions, we also disprove a conjecture by Brenti on the log-concavity of $h^*$-polynomials of Gorenstein IDP polytopes, and a conjecture by Ferroni and Higashitani concerning the log-concavity of the Ehrhart series of IDP polytopes. We also answer their question about the existence of very ample polytopes with non-log-concave interior Ehrhart series. Our class of examples arises by taking Cayley sums of rectangular prisms, and hence they possess regular unimodular flag triangulations by a result of Haase, Paffenholz, Piechnik and Santos. For the unimodality conjecture, we can even find smooth counterexamples.
Read the full abstract

Combinatorics · Cross-listed from math.CT

Noetherian forms of free non-symmetric operads

In this paper, we study certain categories of labeled finite rooted ordered trees over a fixed set of labels where each label is equipped with an arity: a fixed number of children that the vertex with the given label must have. Equivalently, these are expression trees for operations in a free non-symmetric operad. A morphism between these trees matches a pruning of one tree (a prefix) with an entire subtree of another (a suffix). We characterize such categories, up to isomorphism, in terms of suitable exactness properties. It turns out that these categories exhibit strong algebraic behavior, in the sense that every such category, when appended with a strict initial object, has a particularly nice noetherian form.
Read the full abstract

Combinatorics

The Distribution of Double Deficiencies in Pattern-Avoiding Permutations

We study the distribution of the number of double deficiencies (DD) in permutations of length n avoiding one or two patterns of length 3. Using structural decompositions of these avoidance classes–together with a lattice-path decomposition in the 321-avoiding case–we derive functional equations and convolution-type recurrences that efficiently compute the corresponding double-deficiency generating functions in all but one single-pattern case. In the 321-avoiding permutations, the resulting generating function is algebraic; we derive exact formulas for the mean and variance and prove that the distribution is close in total variation to Bin(n-2,1/4), with an explicit convergence rate. We also identify a DD-preserving symmetry that yields DD-Wilf equivalences, reducing the number of two-pattern cases that need to be considered separately. For the resulting two-pattern classes, we obtain explicit recurrences, including C-finite relations.
Read the full abstract

Combinatorics · Cross-listed from math.DS

From Nilspace Theory to Simplicial Homotopy Theory

We construct a faithful functor from the category of cubespaces, arising in structured ergodic theory and nilspace theory, to the category of (condensed) simplicial sets. This functor translates the weak structure theorem of a nilspace to a Postnikov tower of the corresponding simplicial set. In particular, nilspaces are mapped to Kan complexes and the structure groups of the nilspace correspond to the simplicial homotopy groups of the Kan complex. The functor is constructed via pullback along a special cosimplicial cubical set, whose combinatorial properties may be of independent interest.
Read the full abstract

Combinatorics · Cross-listed from math.DS

A Categorical Approach to Nilspace Theory

Originating in ergodic structure theory, nilspace theory is concerned with the study of cubical spaces. A first key result in this theory, the weak structure theorem, is the representation of a concrete fibrant compact cubespace as a tower of its canonical truncations, exhibiting each step over the previous one as a principal bundle by a compact abelian group. We present a categorical proof of the weak structure theorem by systematically interpreting the relevant concepts in an appropriate context.
Read the full abstract

Combinatorics

Induced Forest Minor Theorem for Graphs Without an Induced Star

Motivated by recent work on tree independence number, we study the path independence number of a graph $G$: the minimum integer $k$ such that there is a path decomposition of $G$ where each bag induces a graph with independence number at most $k$. We show that every graph excluding both an induced forest minor and an induced star has bounded path independence number. This characterises when a graph class that excludes an induced star has bounded path independence number while also partially resolving a conjecture of Dallard, Krnc, Kwon, Milanič, Munaro, Štorgel and Wiederrecht (2024). Furthermore, we show that graphs excluding both an apex-forest induced minor and an induced star have bounded tree independence number. As a consequence, for every fixed apex-forest $H$ and integer $t$, there is a polynomial-time algorithm to test whether a $K_{1,t}$-induced-subgraph-free graph contains $H$ as an induced minor. Moreover, it follows that the Maximum Weight Independent Set problem, as well as several other NP-hard problems, can be solved in polynomial-time on $K_{1,t}$-induced-subgraph-free graphs that exclude $H$ as an induced minor.
Read the full abstract

Combinatorics · Cross-listed from math.MG

Hyperbolic distance matrix completion

A completion theory for hyperbolic distance data is developed at the interface of matrix analysis, graph theory, and hyperbolic geometry. Krein's characterization of the metric space embeddability in Lobachevsky space leads to a natural anchoring procedure that transforms the indefinite data into a positive semidefinite kernel. In analogy with positive semidefinite and Euclidean distance matrix completion, chordality of the specification graph is shown to be the necessary and sufficient condition for local Lorentz-Gram data to admit global completion. Existence is complemented by explicit constructions. For trees, we obtain geodesic-rectification and product-distance completions; for chordal graphs, the latter extends to matrix-valued transfers along clique-trees. The resulting canonical completion is characterized by sparsity of its inverse and by a maximum-absolute-determinant principle. Its metric distortion exhibits a sharp dichotomy governed by clique separator size. Applications to exact recovery from sparse hyperbolic measurements and to hierarchical and phylogenetic data are developed.
Read the full abstract

Combinatorics

Superpolynomial lower bounds for vertex numbers of real projective space triangulations via a topological Figiel-Lindenstrauss-Milman theorem

We prove that every simplicial triangulation of real projective $d$-space has $\exp(\Omega(\sqrt d))$ vertices. Together with known constructions, this determines the minimum vertex number as $\mu_d=\exp(d^{1/2+o(1)})$. The result follows from a topological generalization of the Figiel–Lindenstrauss–Milman inequality, answering a recent question of Frick, Hosseini, and Vasileuski: a finite strongly regular CW complex with a free cellular involution, $v$ vertices, and $f$ maximal cells has $\mathbb{Z}/2$-index at most $O(\log v\log f)$. We bound the dimensions of Morse cells by a trace estimate for a constrained Hessian, obtaining a Morse-theoretic proof of the classical inequality for centrally symmetric polytopes. As further applications of this inequality, we give an $\exp(\Omega(\sqrt t))$ lower bound for the order of a triangle-free topologically $t$-chromatic graph and bound the index of sign complexes by $O(d\log^2 N)$ for total matrices and $O(d\log^3 N)$ for partial matrices, where $N\geq2$ is the number of columns and $d\geq1$ is the VC dimension.
Read the full abstract

All authors Florian Frick, Kaave Hosseini, Eric Myzelev, Arya Narnapatti, Aliaksei Vasileuski

Combinatorics · Cross-listed from math.PR

Periodic ASEP and random walks on affine Hecke Algebra

We study the large time behavior of a periodic ASEP with fixed period started from the step initial condition. We establish the limit shape theorem and the asymptotic distribution of a single second class particle. Our single-species results extend the previous results of Lam and Ayyer-Linusson about periodic TASEP to the ASEP case. These results can also be interpreted as describing the limit behavior of a random walk on affine Hecke algebra.
Read the full abstract

Combinatorics

The VC-dimension of strongly regular graphs

A graph $G$ is $n$-existentially closed or $n$-e.c. if, for all subsets $S\subseteq V(G)$ with $|S|=n$ and for all partitions $S=A\sqcup B$, there exists a vertex in $V(G)\setminus S$ adjacent to all vertices in $A$ and no vertices in $B$. We study the minimum number of edges $m(v,n)$ of a $v$-vertex $n$-e.c. graph, and show that $m(v,2)=3v+O(1)$ while $m(v,n)=\Theta(v\log v)$ for fixed $n\ge 3$. The latter result uses a connection to binary covering arrays. A related parameter is the VC-dimension of $G$, defined as the size of the largest subset of vertices shattered by the neighborhoods of vertices in $G$. We initiate systematic study of the VC-dimensions of strongly regular graphs (SRGs). We characterize the sufficiently large SRGs with VC-dimension 2. Furthermore, we determine the VC-dimension of sufficiently large Latin square graphs and of all SRGs of order at most 28, and prove upper bounds for SRGs arising from orthogonal arrays or Steiner systems.
Read the full abstract

Combinatorics · Cross-listed from math.NT

Quasi-modularity of symmetric quasi-shuffles

We develop an algebraic framework for the quasi-modularity of symmetric multiple $q$-zeta values. We identify natural classes of symmetric quasi-shuffles whose $q$-zeta values exhaust the algebra of level-one quasi-modular forms, and further classes whose $q$-zeta values are quasi-modular forms of finite level. We also obtain explicit symmetrization formulas and relate symmetric quasi-shuffles to symmetric and quasisymmetric functions.
Read the full abstract

Combinatorics

Jack Content Operators and the Deformed ${\mathcal W}_{1+\infty}$ Algebra

Frenkel and Wang obtained a representation of the Virasoro algebra by commuting Goulden's cut-and-join operator with the Heisenberg generators. A vertex-operator construction by Lascoux and the author extends this representation to $\mathcal W_{1+\infty}$ by means of differential operators whose eigenvalues are the power sums of the contents of a Young diagram. We develop a Jack deformation in the spherical degenerate double affine Hecke algebra and its stable limit. Starting from the Heckman–Polychronakos integrals, we isolate operators whose eigenvalues are the power sums of the $\alpha$-contents. Because the Goulden–Jackson product is defined in the convention dual to the usual Calogero–Sutherland Hamiltonians, the multiplication operators $\Delta_\mu(\alpha)$ are obtained by taking Hall adjoints. This gives conceptual derivations of the Jack cut-and-join operator and of the stable $3$-cycle operator. A normal-ordering construction due to Sergeev and Veselov makes the latter calculation explicit and suggests an integral form over $\mathbb Z[\alpha]$. The commutators of the cut-and-join operator contain one half of the usual Feigin–Fuchs realization, but this Virasoro completion is not the deformation of the Frenkel–Wang construction. The latter takes place in the deformed $\mathcal W_{1+\infty}$ algebra $\mathbf{SH}^c$, equivalently in the affine Yangian of $\mathfrak{gl}_1$: in our normalization its first nontrivial Cartan mode is $\psi_3=3\Delta_2(\alpha)+2(\alpha-1)E$, and its commutators with the first raising and lowering modes recursively generate the remaining currents. At $\alpha=1$ these relations specialize to the central-charge-one $\mathcal W_{1+\infty}$ representation used by Lascoux and the author.
Read the full abstract

Combinatorics

Sharp Bounds on the Number of Small Cuts

Let $\lambda$ be the minimum cut value of an $n$-vertex undirected multigraph. For every fixed $\alpha>1$, we prove that there are $O(n^{\lceil2\alpha\rceil-1})$ cuts of size strictly below $\alpha\lambda$. The exponent is sharp. The proof combines splitting off and sampling with a bound on the size of nested families of vertex sets.
Read the full abstract

Combinatorics

On Two Conjectures Related to the Boros-Moll Sequences

The Boros-Moll sequences $\{d_i(m)\}_{0\leq i\leq m}$ are defined as $$d_i(m)=2^{-2m}\sum_{k=i}^m 2^k \binom{2m-2k}{m-k}\binom{m+k}{k}\binom{k}{i}.$$ Consider the ratio sequence $$u_i(m)=\frac{d_{i-1}(m)d_{i+1}(m)}{d_i(m)^2}.$$ Chen and Gu conjectured that $\{u_i(m)\}_{2\leq i \leq m-2}$ is both reverse ultra log-concave and log-concave. In this paper, we prove the reverse ultra log-concavity conjecture using bounds of Chen-Gu and Zhao, and prove the log-concavity conjecture asymptotically by showing that $\{u_i(m)\}_{2\leq i \leq m-2}$ is strictly log-concave for all sufficiently large $m$. The key ingredient in the latter result is a recurrence of Kauers and Paule, which we interpret as a nonlinear discrete dynamical system through a backward map. We construct an approximation to the ratio sequence using its stable limiting fixed point and combine localization and contraction arguments with finite-difference estimates and separate interior and edge analyses to obtain the desired strict log-concavity.
Read the full abstract

Combinatorics · Cross-listed from math.RT

Derived equivalences between diagram categories of finite posets

We study universal derived equivalences between diagram categories indexed by finite posets. Starting from a construction of Ladkani, we give an intrinsic criterion for determining when a finite poset admits a decomposition to which this construction can be applied. This leads to the notion of an admissible cut, formulated entirely in terms of the order structure of the poset. Our main result therefore provides a method for producing, from a given finite poset admitting such a cut, a new poset that is universally derived equivalent to it. The construction is reversible once the partition is retained, so that the original mixed order relations can be recovered from the transformed poset. As applications, we show that every finite poset of height at most one is universally derived equivalent to its opposite, give a criterion characterizing source-to-sink transformations at minimal elements, and recover the universal derived equivalence of all orientations of a finite tree through sequences of such local transformations. These results are also applied to persistence modules indexed by finite posets and to extensions obtained by adjoining further finite parameters.
Read the full abstract

Combinatorics

On $S$-packing total colorings

In this paper, we generalize the concept of packing total coloring by introducing a new concept called the $S$-packing total coloring. For a graph $G$ and a non-decreasing sequence $S=(a_1,a_2,\ldots)$ of positive integers, an $S$-packing total coloring of $G$ is a mapping $c: V(G)\cup E(G)\rightarrow \{1,2,\ldots\}$ such that for any two distinct elements $A,B\in V(G)\cup E(G)$ with $c(A)=c(B)=i$, the distance between $A$ and $B$ is at least $a_i+1$. The smallest integer $k$ such that $G$ admits an $S$-packing total coloring using $k$ colors is called the $S$-packing total chromatic number of $G$, denoted by $\chi_S^{''}(G)$. For any sequence $S$, we establish general lower and upper bounds for $\chi_S^{''}(G)$, and characterize all graphs $G$ with $\chi_S^{''}(G)\in\{1,2,3\}$. Furthermore, we investigate $S$-packing total chromatic numbers of complete bipartite graphs, as well as infinite and finite paths and cycles.
Read the full abstract

All authors Jasmina Ferme, Jaka Hedžet, Petra Melicharova, Daša Mesarič Štesl

Combinatorics

Quasi-strongly regular digraphs constructed from transitive groups of degree $n\leq 110$

In this paper we present a method for constructing directed regular graphs from a transitive permutation group. This method is a generalization of a construction method for transitive 1-designs from a finite group, described in \cite{dean1}. Using this construction, we prove the existence of directed strongly regular graphs with parameters $(72,25,15,6,10)$, $(96,11,4,3,1)$, $(96,22,16,8,4)$, $(96,26,11,7,7)$, $(96,29,23,10,8)$, $(96,42,32,16,20)$, $(96,45,35,22,20)$ and $(165,60,36,23,21)$. Finally, we classify quasi-strongly regular digraphs arising from transitive permutation groups of degree at most $30$ and from primitive permutation groups of degrees from $31$ to $110$ and rank at most $30$.
Read the full abstract

Combinatorics

Asymptotic Bounds for Irredundant Covers of Square Grids by 2 x 2 Cards

We study an irredundant covering of an $m \times m$ square grid by $2 \times 2$ cards, where cards may overlap and every card must lie entirely inside the grid. Every square of the grid must be covered, and every card must contain at least one square that is covered only by itself. Let \(F(m)\) denote the maximum number of cards in such an irredundant cover. We develop a general framework for bounding the maximum possible size of such an irredundant cover based on square multiplicities, double counting, and local geometric restrictions arising around highly covered squares. These arguments yield a general upper bound whose leading term is $\frac{1}{2}m^2$, accompanied by a negative linear term. In the opposite direction, we construct a family of irredundant covers based on a density-$\frac{1}{2}$ covering pattern, referred to as the period-four staircase pattern, together with a boundary-repair construction. Thus, we obtain a lower bound with the same leading term and a linear-order error, proving that for every \(m\ge6\), \[ \frac{2m}{9} \le \frac12m^2-F(m) \le 2m-3, \] and consequently that the maximum density of an irredundant cover tends to $\frac{1}{2}$ as $m\to\infty$. The known $10\times 10$ case is used as motivation and as a finite benchmark for the general theory.
Read the full abstract

Combinatorics

Umbral calculus over a vector space

Let $V$ be a vector space over $\mathbb F=\mathbb R$ or $\mathbb C$. We develop a basis-free umbral calculus over $V$. We define the vector space of polynomials over $V$, and polynomial sequences in it. We discuss shift-invariant operators acting in polynomials over $V$. We define polynomial sequences of binomial type and Sheffer sequences over $V$. We provide equivalent characterizations of these polynomial sequences. We prove two recurrence formulas for Sheffer sequences. With each Sheffer sequence, we associate a linear operator acting in polynomials over $V$, which we call a Sheffer operator. We prove that the set of Sheffer operators is a group for the usual product of linear operators, which is isomorphic to the Riordan group of pairs of formal tensor power series in a variable from $V$. Under the assumption that $V$ is an algebra, we lift every Sheffer sequence over $\mathbb F$ to a Sheffer sequence over $V$. We provide examples of such lifting.
Read the full abstract

Combinatorics

Overlap-Helly theorems

In this paper we introduce a generalization of Helly's theorem closely connected to Bárány-Gromov overlap theorems (also called selection lemmas). Our main result implies both the topological colorful Helly of Kalai and Meschulam and Karasev's topological centerpoint theorem. We further investigate the topological fractional Helly theorem from this overlap perspective, and show an overlap theorem for dense complexes (a continuous second selection lemma for tame maps).
Read the full abstract

Combinatorics

An Improved Upper Bound for the Turán Number of the Hexagon

For a graph $F$, the Turán number $\operatorname{ex}(n,F)$ is the maximum number of edges in an $n$-vertex graph containing no copy of $F$. Determining the Turán numbers of even cycles is a central problem in extremal graph theory and remains open in general. For $C_6$, the best previous upper bound was due to Füredi, Naor, and Verstraëte [Advances in Mathematics, 2006], who proved that, for sufficiently large positive integer $n$, $$ \operatorname{ex}(n,C_6) \leq \lambda n^{4/3}+O(n)<0.6272 n^{4/3}, $$ where $\lambda$ is the real root of $ 16\lambda^3-4\lambda^2+\lambda-3=0$. We improve this bound by showing that, for sufficiently large positive integer $n$, $$ \operatorname{ex}(n,C_6) \leq \alpha n^{4/3}+O(n)<0.6144 n^{4/3}, $$ where $\alpha$ is the unique real root of $ 4 \alpha^{3} (3/2)^{1-1/(2\alpha)} =1$ in the interval $(1/2,2/3)$.
Read the full abstract

All authors Sandip Das, Sk Samim Islam, Aashirwad Mohapatra, Saumya Sen

Combinatorics

Oriented paths with two blocks in bipartite oriented graphs

Stein conjectured that for any integer $k\geq 2$, every oriented graph with minimum semidegree greater than $k/2$ contains every orientation of a path with $k$ edges. Recently, Chen, Hou and Zhou proved this conjecture to be true for any oriented path with two blocks, where a block of an oriented path is a maximal directed subpath within it. In this paper, we prove that every bipartite oriented graph with minimum semidegree at least $3k/8+2$ contains every oriented path with two blocks of length $k$ for $k\ge 2$. Moreover, in contrast to the general oriented setting, we highlight that the minimum semidegree threshold in the bipartite setting is closely related to the number of blocks.
Read the full abstract

All authors Bin Chen, Meishuang Chen, Xinmin Hou, Xinyu Zhou