Papers

We introduce three homology theories for hypergraphs, namely $\Gamma$-homology, $\Box$-homology, and $\times$-homology, and show that they are pairwise non-isomorphic and distinct from the embedded homology of hypergraphs. We further introduce a notion of homotopy for hypergraphs that extends the discrete homotopy theory of graphs. Among the homology theories considered, we prove that $\Box$-homology is invariant under this homotopy, whereas $\Gamma$-homology and $\times$-homology fail to satisfy homotopy invariance. Based on excision, we also identify a distinctive structural behavior exhibited by $\Gamma$-homology that further differentiates it from $\Box$-homology.

The Worley-Sagan insertion and Haiman's mixed insertion are insertion algorithms for shifted Young tableaux, and each of them gives a Robinson-Schensted-type correspondence between the symmetric group of degree $n$ and a set consisting of certain pairs of same-shape shifted Young tableaux with $n$ cells. It is a known fact that these two insertions are dual to each other. Our purpose is to give an extension of these two insertions without losing the duality relationship. The extended ones will be insertions producing pairs of shifted tableaux from colored permutations. Our extension of the Worley-Sagan insertion is different from the restriction of Sagan's own "Knuth version" to colored permutations. In proving the duality between our extended insertions, we "embed" them into Shimozono and White's doubly mixed insertion for unshifted tableaux by "doubling" shifted tableaux and use the self-duality of the doubly mixed insertion shown by Shimozono and White.

We give a general principle that converts fixed-uniformity bounds for forbidden traces into bounds with polynomial dependence on the uniformity. More precisely, let $H$ be a fixed set system on $h\ge1$ vertices, and suppose that, for some $\alpha\ge0$, $\operatorname{ex}_j(m,\operatorname{Tr}(H))=O_{H,j}(m^\alpha)$ for every fixed integer $j\ge1$. Then, for every $\varepsilon>0$, there is a constant $C_{H,\alpha,\varepsilon}$ such that \[ \operatorname{ex}_r(m,\operatorname{Tr}(H)) \le C_{H,\alpha,\varepsilon} r^{h-1-\alpha+\varepsilon}m^\alpha \] for all $m\ge r\ge2$. In particular, for trace-$C_4$-free hypergraphs and every $\varepsilon>0$ there is a constant $C_\varepsilon$ such that \[ \operatorname{ex}_r(m,\operatorname{Tr}(C_4)) \le C_\varepsilon r^{3/2+\varepsilon}m^{3/2} \] for all $m\ge r\ge2$. We also construct trace-$C_4$-free $r$-graphs showing that \[ \operatorname{ex}_r(m,\operatorname{Tr}(C_4)) \ge c r^{1/2}m^{3/2} \] for an absolute constant $c>0$, for every fixed $r\ge3$ and all sufficiently large $m$ (depending on $r$).

In this paper, we study the existence problem of completely independent spanning trees (CIST) in chordal graphs through appropriate hypergraph representations and their panchromatic and bipanchromatic colorings. First, we disprove a conjecture stating an exact relationship between the panchromatic number, the bipanchromatic number, and the minimum number of unique colors in an optimal panchromatic coloring of a hypergraph. Then, by relating CIST to panchromatic and bipanchromatic colorings of the associated hypergraphs, we derive structural conditions for their existence in chordal graphs and specifically strictly chordal graphs.

We study the complementary version of Hedetniemi's problem for infinite graphs. We prove that if a graph $G$ and its complement $\overline{G}$ are both uncountably chromatic while their categorical product is countably chromatic, then $|V(G)|=\omega_1$. Assuming $\diamondsuit$, we construct a graph $G$ on $\omega_1$ such that $\chi(G)=\chi(\overline{G})=\omega_1$ and $\chi(G\times\overline{G})=\omega$; the construction uses two suitably chosen minimal Countryman lines. We also define a c.c.c. forcing of cardinality $\omega_1$ that adds a graph with the same properties. It remains open whether ZFC alone proves the existence of such a graph.

We study the integer sequence that enumerates cokernel-closed, idempotent split, full, additive subcategories of the category of finite dimensional complex representations of a uniformly oriented $A_n$ quiver. Using a combinatorial model, we describe a non-obvious connection of this sequence to Catalan numbers and derive an implicit recurrence. We also describe some basic properties of the lattice underlying the sequences, in particular, we give an explicit description of the meet irreducible elements of that lattice.

The stylic monoid $\mathrm{Styl}_n$, introduced by Abram and Reutenauer, is the quotient of the plactic monoid by the relations $x^2=x$, and its elements are represented by $N$-tableaux. Volkov showed that the Catalan monoid $\mathrm{Cat}_n$ of order-preserving, order-decreasing self-maps of $\{0,1,\ldots,n\}$ is a quotient of $\mathrm{Styl}_n$. However, the quotient map is defined on generators, and it is not apparent how to see, from an $N$-tableau, the map in $\mathrm{Cat}_n$ it corresponds to. In this paper we give a simple visual way to read off this map, and some of its main properties, from the $N$-tableau. The new ingredient is that we do not insist on drawing an $N$-tableau as a classical Young tableau: we allow the entries of each row to be shifted relative to the row below, as long as each entry stays above a smaller one. We call this a positioning, and prove that the column word read from any positioning is plactically equivalent to the usual column word; so every positioning can be used to compute the quotient map. We work with the tight positioning, in which each entry is pushed as far right as possible, and define the full core of an $N$-tableau: the part of each column that climbs by consecutive values from the bottom row. We call an $N$-tableau full if it equals its full core. We prove that passing to the full core does not change the image in $\mathrm{Cat}_n$, that full $N$-tableaux are in bijection with $\mathrm{Cat}_n$, and we show how to read the corresponding map directly off a full $N$-tableau.

We give an independent computer-assisted proof of the k=4 case of the Chen-Raspaud conjecture. We prove that every graph G with odd-girth(G) >= 9 and mad(G) < 9/4 admits a homomorphism to the Kneser graph K(9,4). The proof combines a minimal-counterexample argument with a rooted star replacement, exact finite computations in K(9,4), and a final charging argument. After all reducible local types are removed, the unique positive local type is (3,3,4). Its unit excess is transferred through its 4-thread to a relative with sufficient negative capacity. The computer-assisted statements used in the proof are certified by exact C++ bitset verifiers, and a separate Python implementation provides an independent cross-check; the complete source code and raw certificates accompany the manuscript.

We study the diagonal Specht ideals $I_\lambda\subseteq\mathcal{R}_{m,n}:=\mathbb{C}[\mathbf{x}_1,\dots,\mathbf{x}_m]$, $\mathbf{x}_r=(x_{r,1},\dots,x_{r,n})$, generated by the $\lambda$-isotypic component of $\mathcal{R}_{m,n}$ for the diagonal action of $S_n$. We characterize the set of zeros of $I_\lambda$ as $V_\lambda=\bigcup_{\mu\not\trianglelefteq\lambda}H_\mu$ and prove that $\lambda\mapsto V_\lambda$ is an isomorphism of posets from $(\mathcal{P}_n,\trianglelefteq)$ to $(\{V_\lambda:\lambda\in \mathcal{P}_n\},\supseteq)$ for all $m$, while $\lambda\mapsto I_\lambda$ is an isomorphism of posets from $(\mathcal{P}_n,\trianglelefteq)$ to $(\{I_\lambda:\lambda\in \mathcal{P}_n\},\subseteq)$ if and only if $m=1$ or $n\leq3$. Unlike the case $m=1$, where Specht ideals are always radical, radicality in the diagonal setting depends on $\lambda$ and $m$. We prove radicality for hook partitions of length at most three by providing explicit Gröbner bases, and we develop three criteria for non-radicality via content, multidegree, and total degree, showing in particular that $I_\lambda$ is not radical for any non-hook partition $\lambda$ when $m\geq\operatorname{len}(\lambda)$. Using the $\operatorname{GL}_m(\mathbb{C})$-action on $\mathcal{R}_{m,n}$, we show that $I_\lambda$ is radical for all $m$ if and only if it is radical for $m=n$. Finally, for $m\geq2$, we prove that $\mathcal{R}_{m,n}/I_\lambda$ is Cohen-Macaulay if and only if $\lambda=(n)$ or $\lambda=(n-1,1)$, and the same is true for $\mathcal{R}_{m,n}/\operatorname{rad}(I_\lambda)$.

For a finite forest $F$ let $i_k(F)$ be the number of independent sets of $F$ with $k$ vertices. Zhang and Li proved that the sequence $i_0(F),i_1(F),\dots,i_{\alpha(F)}(F)$ is unimodal for every finite forest $F$, which answers Erdős Problem 993. We give a second proof. It starts from their decomposition relative to a fixed independent set and from the bounds of Zhang and Li and of Fang, Lu, Nevo, Yao and Zheng that confine a valley of the sequence to an explicit window of ranks. For a forest with at least $25$ vertices, one moment argument excludes a valley at every rank of the window: at the activity where the hard-core mean equals the rank, the size of a random independent set is a mixture of binomial laws over an independent set of maximum weight, a valley is a moment inequality for this mixture, and it is excluded by duality given three bounds that hold for every forest, on the variance of the number of free vertices and on its Laplace transforms, and on the variance ratio. The variance bound is proved by hand up to finitely many interval checks and the other two bounds are verified by computer on finite interval-arithmetic coverings; on the resulting parameter domain a valley is excluded by exact tests on finitely many rational boxes while the mean number of free vertices is below an explicit starting mean between $19$ and $50$, and above it by one inequality, with explicit constants, for the fibers of a weighted valley kernel, proved by hand up to a finite list of explicit checks and averaged over the mixture. Forests with at most $24$ vertices are treated by exact counting, by hand except for exact rational evaluations of two explicit formulas at $43$ parameter triples. No forest is enumerated. A formal proof of the theorem in Lean 4 accompanies the paper.

Let $h_n$ denote the complete homogeneous symmetric function of degree $n$, $s_\nu$ the Schur function indexed by a partition $\nu$, and $\langle\cdot,\cdot\rangle$ the Hall inner product. The plethysm coefficient $\langle h_n[h_m], s_\nu\rangle$ is the multiplicity of the Weyl module $W_\nu(\mathbb{C}^N)$ in $\mathrm{Sym}^n(\mathrm{Sym}^m(\mathbb{C}^N))$ whenever $\nu$ has at most $N$ parts. For a partition $\lambda$, let $\lambda[mn]=(mn-|\lambda|,\lambda_1,\lambda_2,\dots)$. Bowman and Paget proved that $\langle h_n[h_m], s_{\lambda[mn]}\rangle$ is independent of $m$ and $n$ once $m,n\ge|\lambda|$. We prove that this coefficient is already constant for $m\ge\lambda_1$ and $n\ge\lfloor(|\lambda|+\lambda_1)/2\rfloor$, and that its stable value equals $\langle s_\lambda, H[H-1-h_1]\rangle$, where $H=\sum_{i\ge0}h_i$; the proof uses the skewing operators adjoint to multiplication by complete homogeneous symmetric functions. We give a short new proof of the Bowman-Paget theorem based on stability of vector-partition functions, which count the ways of writing a vector of non-negative integers as an unordered sum of non-zero such vectors (its parts). Using a Vandermonde-type determinantal identity, we deduce that the stable value is a signed sum of numbers of vector partitions all of whose parts have entries summing to at least 2. The same method gives a short proof of Brion's stability theorem. We show that the stable value equals the multiplicity of $W_\lambda(\mathbb{C}^k)$, where $k=\lfloor|\lambda|/2\rfloor$, in an explicit representation of $GL_k(\mathbb{C})$ independent of $m$ and $n$, obtained by modifying the polynomial induction of Narayanan, Paul, Prasad and Srivastava. Finally, we prove an explicit positive formula for the stable value, which counts the number of lattice points in a polytope, when $\lambda_1\le 4$.

Two graphs $G$ and $H$ are homomorphism indistinguishable over a graph class $\mathcal{F}$ if, for every graph $F \in \mathcal{F}$, the number of homomorphisms from $F$ to $G$ is equal to the number of homomorphisms from $F$ to $H$. Lovász (Acta Mathematica Academiae Scientiarum Hungarica, 1967) showed that two graphs are isomorphic if, and only if, they are homomorphism indistinguishable over all graphs. Subsequently, homomorphism indistinguishability relations of a long list of natural graph classes have been equated with natural graph isomorphism relaxations. Given the wealth of such results, Atserias, Kolaitis, & Wu (LICS 2021) asked for an axiomatic characterisation of homomorphism indistinguishability relations. By exhibiting topological and geometric structure associated with homomorphism indistinguishability, we derive such an axiomatic characterisation. Here, a central ingredient is a novel characterisation of graph parameters of the form $\hom(F, \star)$ for some graph $F$ alternative to a previous result of Lovász & Schrijver (JCTA 2010). Moreover, we investigate the topology of homomorphism indistinguishability and discuss repercussions for the Ulam–Kelly Reconstruction Conjecture.

A graph is beautiful if each of its induced subgraphs is the intersection graph of all maximal nonempty 1-rectangles of a binary matrix, with adjacency defined by a common cell. Beautiful graphs were introduced as a hereditary class of Berge graphs, but a complete forbidden-induced-subgraph characterization was not obtained. We prove that a finite graph is beautiful if and only if it has no induced $C_4$, gem, net, watch, or odd hole. More precisely, these graphs are exactly the $C_4$-free comparability graphs admitting a partial order in which every interval is a chain. The proof constructs such an order from inclusion-maximal closed neighbourhoods: their representatives induce a bipartite graph whose domination regions admit compatible orientations. One order matrix then represents the graph and, through its principal submatrices, every induced subgraph. The representation step is formulated using classical double-bound graphs and the established correspondence between maximal bicliques and interval-intersection-closed posets. Consequences include polynomial-time recognition, the exact minimal obstruction families, and a corrected characterization in the $K_4$-free case.

Let $K$ be a finite field of characteristic two with $|K| = 2^{n}$, let $\gcd(k,n) = 1$, let $d_{k} = 4^{k} - 2^{k} + 1$ be the Kasami exponent, and let $\Delta_{k} = \{(b+1)^{d_{k}} + b^{d_{k}} + 1 : b \in K\}$ be the image of the normalised derivative of the Kasami monomial in the direction $1$. We show that, for all distinct nonzero $v_{1},v_{2} \in K$, \[ \bigl|\{(x,y,z) \in \Delta_{k}^{3} : v_{1}x + v_{2}y + (v_{1}+v_{2})z = 0\}\bigr| = 2^{2n-3}. \] This establishes the cyclic-additive difference-set condition introduced by Carlet and later posed for the Kasami functions at NSUCRYPTO~2019. Starting from the known half-size property of the derivative image, we express the Fourier correction as twisted root counts and prove their required nonnegativity by an incidence argument on the Fermat cubic. An exact average over the slopes then forces equality pointwise. The argument covers every admissible pair $(n,k)$ and has been formalised and machine-checked in Lean~4 with Mathlib.

Phylogenetic networks generalize phylogenetic trees as models of evolutionary history, allowing lineages to merge as well as to diverge. For many types of genetic data the root position of such a network cannot be recovered, so that only a semi-directed network can be inferred: a mixed graph in which only the edges entering a reticulation vertex are directed. A common strategy for inferring such a network is to first infer the subnetwork it induces on each set of $k\geq 3$ of its leaves, called a $k$-net, and then to assemble these pieces. This can only succeed if the $k$-nets determine the network, in which case that network is said to be encoded by its $k$-nets. Semi-directed networks of level-1 and 2, those whose biconnected components contain at most one, respectively two, reticulations, are known to be encoded by their $4$-nets, or quarnets, whereas level-3 networks are not. Even so, in this paper we show that level-3 semi-directed networks are encoded by their $5$-nets, or quinnets, and we characterize the limitation of quarnets exactly: we show that a single previously reported counterexample captures the only obstruction, every other level-3 network being encoded by its quarnets. Our proofs rest on a collection of encoding results for individual structural features of a network, which we establish for networks of arbitrary level and which are of independent interest.

In the 1960s, Erdős and Gallai conjectured that the edges of every $n$-vertex graph can be decomposed into $O(n)$ cycles and edges. We prove this conjecture. Equivalently, every Eulerian graph on $n$ vertices can be decomposed into $O(n)$ cycles, which confirms Hajós' conjecture up to a constant factor.

Experiments on binary run-length differentiability lead to sharp computer-assisted criteria for shuffle squares. Every $C^3$-word of length greater than $16$ is a shuffle square exactly when both letter multiplicities are even. All $34$ nonempty even-Parikh exceptions are smooth and persist in every higher differentiability class. For $C^2$ the sharp threshold is $48$, with $212$ nonempty exceptions. At level $C^1$ no global parity threshold exists, but every even-Parikh non-shuffle-square of length at least $36$ has proper nonempty shuffle-square prefixes and suffixes. Exactly $230$ nonempty even-Parikh $C^1$-words have no nonempty shuffle-square prefix. The full tree avoiding such prefixes eventually consists of $422$ periodic rays. Consequently, a nonempty Kolakoski prefix is a shuffle square exactly when both multiplicities are even, apart from lengths $4$ and $8$. We also characterize classes of morphisms reflecting shuffle squares. For doubly binary words, we determine the exact deletion distance and largest twins, and prove sharp bounds for single local repairs. Exact recurrences, residual-state checks, and separate Python programs make the finite computations reproducible.

We introduce complementary determinantal edge ideals. For a graph $G$ on $n$ vertices, the complementary determinantal edge ideal $J_{c}(G)$ is generated by the maximal minors of a generic $(n-2)\times n$ matrix obtained by deleting the two columns indexed by each edge of $G$. We completely characterize the graphs for which $J_{c}(G)$ is Cartwright–Sturmfels with respect to the grading by columns. We prove that this property is equivalent to the existence of a multilinear universal Gröbner basis and characterize the graphs satisfying these equivalent conditions. In particular, the ideals satisfying these equivalent conditions are radical.

Let $\textit{spex}_{\mathcal{P}_1}(n,F)$ be the maximum spectral radius among all $n$-vertex $F$-free $1$-planar graphs. Define $F_t$ as the friendship graph formed by $t$ triangles sharing exactly one common vertex. Tait and Tobin (2017)~\cite{Tait2017} used the fundamental structure of spectral extremal graphs to determine the unique planar graph with maximum spectral radius for sufficiently large order. Subsequently, Zhang, Wang and Wang (2024)~\cite{Zhang2024} characterized the corresponding extremal graph in the class of $1$-planar graphs. In this paper, we focus on $F_t$-free $1$-planar graphs and establish a structural theorem for their spectral extremal graphs for all $t\geq1$ and sufficiently large $n$. More precisely, every extremal graph is connected and contains a copy of $K_{2,n-2}$, and for $t\geq2$ the two distinguished vertices are adjacent and the subgraph induced by the remaining vertices is a bipartite graph. Based on this structure result together with the drawing properties of $K_{3,6}$, we determine $\textit{spex}_{\mathcal{P}_1}(n,F_t)$ and characterize its unique extremal graph.

We prove a sharp quantitative form of the van der Corput property for squares. For all sufficiently large $N$, we construct a real trigonometric polynomial $P(\theta)=a_0+\sum_{1\le n\le\sqrt N}a_n\cos(2\pi n^2\theta)$ satisfying \begin{equation}\tag{1}\label{eq:abstract-vdc} P(\theta)\ge0\quad(\theta\in\mathbb{R}/\mathbb{Z}),\qquad P(0)=1, \end{equation} with \[0\le a_0\le\exp(-c\sqrt{\log N\log\log N}),\] where $c>0$ is an absolute constant. As a consequence, if $A\subseteq\mathbb{N}\cap[1,N]$ has no nonzero square difference, then \[|A|\le N\exp(-c\sqrt{\log N\log\log N}),\] improving upon a recent result of Green and Sawhney. Our construction builds on previous work of Slijepčević, Slijepčević–Ninčević, and Fan–Lott, and the proof of the upper bound is elementary and self-contained. We also show that every real trigonometric polynomial of the above form satisfying \eqref{eq:abstract-vdc} has \[a_0\ge\exp(-C\sqrt{\log N\log\log N})\] for an absolute constant $C>0$. Thus the van der Corput property cannot be used to obtain a power-saving bound for the Furstenberg–Sárközy theorem.

For even $n$, let $P_n$ be the probability that independent uniform strict preference lists on $n$ participants admit a stable perfect matching. We prove \[ P_n\sim\frac{e\,2^{1/4}\Gamma(3/4)}{\sqrt\pi}\,n^{-1/4}. \] This establishes Mertens's conjectured exponent of decay, with a leading constant different from his original numerical prediction. The proof starts from Mertens's exact alternating sum over stable permutations. To preserve its cancellation, we construct a common approximation for all cycle structures with the same number of vertices in cycles longer than two. By symmetry, the integrated first-order correction is the same for every such cycle structure, and the remaining errors can be summed in absolute value. The enumeration then reduces the probability to a one-dimensional sum with positive terms.

A connected graph with at least two vertices is matching covered if each of its edges is contained in a perfect matching. A matching covered graph is solid if every separating cut in it is a tight cut. A matching covered graph which is free of nontrivial tight cuts is a brick if it is nonbipartite. Every bipartite matching covered graph is solid. Lucchesi and Murty conjectured that there exists a positive integer $N$ such that, for every integer $n\ge N$, the maximum number of edges in a simple solid matching covered graph on $2n$ vertices is $n^2$. In this paper, we disprove this Conjecture, and show that the maximum number of edges of a simple solid matching covered graph on $2n$ ($n\ge2$) vertices is $n^2+2$. Moreover, we characterize the graphs attaining this bound. In addition, we prove that every simple solid brick of order $2n$ has at most $n^2$ edges for $n\ge4$.

For a Dirac operator $D$ on a finite weighted graph, let $d^D$ denote the associated noncommutative (Connes) distance. We show that deleting an edge can actually decrease the noncommutative distance between two vertices in the graph. The smallest example of this phenomenon comes from a weighted 4-cycle, and the case of deleting an edge from a weighted 4-cycle is determined completely: if $d^{D'}$ denotes the noncommutative distance in the graph after edge deletion, we prove that $\sup d^D/d^{D'} = 2/\sqrt{3}$ for the $4$-cycle, and further that this upper bound holds for all graphs. On the other hand, we show that deleting an edge can decrease the noncommutative distance between two vertices of an $n$-cycle precisely when $n$ is divisible by $4$. In cases when a deleted edge decreases the noncommutative distance between two vertices $x$ and $y$, we show that the deleted edge need not be incident to either of the vertices $x$ or $y$, and in fact the deleted edge can be arbitrarily far from both in the graph-theoretic (number of edges) distance and in the weighted (geodesic) distance. Moreover, deletion of a single vertex arbitrarily far from both $x$ and $y$ in either the graph-theoretic or weighted distance can change $d^D(x,y)$ by an arbitrarily large factor.

Let $U_X(t)$ be the transition matrix of a quantum walk on a graph $X$ relative to its adjacency matrix $A$ or the Laplacian matrix $L$. This paper investigates the behavior of quantum walks under Cartesian products, joins, and graph complements. We have two main goals. First, we characterize the conditions such that peak state transfer and pretty good state transfer are preserved under these operations, allowing us to construct new families of graphs admitting these properties. Our second goal is to analyze the relationship between the quantum walks on a graph and its complement. We provide bounds for $f_{u,v}(t)=\big|U_{X^c}(t)_{u,v}-e^{it\delta}U_X(-t)_{u,v}\big|$ and $g_{u,v}(t)=\big||U_X(t)_{u,v}|-|U_{X^c}(t)_{u,v}|\big|$, where $\delta=-1$ when dealing with $A$ and $\delta=n$ otherwise. Note that $f_{u,v}(t)$ and $g_{u,v}(t)$ both measure the difference between the behavior of quantum state transfer between vertices $u$ and $v$ in a graph and its complement. If $X$ is regular or $M=L$, then $f_{u,v}(t)$ is bounded above by $\frac{2}{|V(X)|}$. If $X$ is non-regular and $M=A$, then we utilize the main eigenvalues of a graph to obtain an upper bound for $f_{u,v}(t)$ which depends only on $A$. We also use the bounding matrix of the graph to give bounds for the Nordhaus-Gaddum type relations $|U_X(t)_{u,v}|+|U_{X^c}(t)_{u,v}|$ and $|U_X(t)_{u,v}|\cdot |U_{X^c}(t)_{u,v}|$. Finally, we demonstrate that most of our bounds are sharp for certain families of graphs.

We study the total and average area of $(sn,n)$-Dyck paths: lattice paths from $(0,0)$ to $(sn,n)$ that stay weakly below the line $x=sy$, counted by the Fuss-Catalan numbers. Generalizing a result of Merlini, Sprugnoli, and Verri for the case $s=1$, we derive an exact formula for the total area over all such paths. From this we obtain explicit upper and lower bounds for both the total and the average area, together with the corresponding asymptotics: for fixed $s$, the average area is asymptotic to $\sqrt{\pi s(s+1)/8} \cdot n^{3/2}$, while for fixed $n$ it is asymptotic to $sn \cdot Q(n)/2$ as $s$ grows large, where $Q(n)$ denotes Ramanujan's $Q$-function. Along the way, we confirm a conjecture of Kotesovec on the asymptotics of a binomial sum that also arises in several other enumeration problems.

We construct a polytopal simplicial sphere that admits a mod 2 characteristic map but no mod 3 characteristic map, and hence no integral one. This shows that the Buchstaber number of a polytopal sphere can be strictly smaller than its real Buchstaber number, and gives a negative answer to the toric lifting problem.

The basic hypergeometric series ${}_{n+1}\phi_{n}$ whose upper and lower parameters are non-negative integer powers of $q$ satisfying a certain constraint can be, after a normalisation, computed as a positive polynomial. We derive three formulas for this polynomial. The first formula is a generalisation of the MacMahon identity in which an infinite binomial series is identified with a normalised generating function of des and maj statistics of multiset permutations. The second formula is a generating function of multiset permutations for the inversion statistic and a generalisation of the statistic mstc. The third formula is a finite sum containing $2n$ $q$-binomial coefficients.

An $(s,p)$-edge-coloring of a graph $G$ is an edge coloring using $s$ colors such that exactly $p$ colors appear at each vertex. To generalize the notion of proper edge-coloring, these colorings are defined to be equitable: the numbers of edges of each color incident to a vertex are fairly distributed. We find the necessary and sufficient conditions for embedding an equitable $(s_1,p_1)$-edge-coloring of $K_{n_1}$ into an equitable $(s_2,p_2)$-edge-coloring of $K_{n_2}$. We focus on the values of $n_1$, $p_1$, $n_2$, and $p_2$ where $s_1$ is necessarily larger than $p_1$ and $s_2$ is necessarily larger than $p_2$.

Consider a finite planar graph with positive real edge weights and designated boundary vertices, called nodes. Such a graph is called a circular planar electrical network. A grove is a spanning forest in which every component contains at least one node. The connected components of a grove determine a partition of the nodes. We relate weighted grove counts to invariant theory for the symplectic group. To a planar electrical network $G$, we associate an $\mathrm{Sp}(2n)$-invariant tensor $Z_G$. For $\mathrm{Sp}(2)=\mathrm{SL}(2)$, we expand $Z_G$ in the Temperley–Lieb basis indexed by noncrossing matchings and relate its coefficients to the Kenyon–Wilson grove formulas. For $\mathrm{Sp}(4)$, we give reduction rules for superpositions of two groves and prove that the tensors indexed by $3$-noncrossing matchings form a basis of the space of $\mathrm{Sp}(4)$-invariant tensors. The coefficients of $Z_G$ in this basis are weighted counts of reduced double groves, up to normalization.

This paper contributes to the long line of research on the distribution of mesh patterns in permutations. We extend these studies to separable permutations and carry out a comprehensive analysis of mesh patterns of length at most~2. For mesh patterns of length~1, we determine the distributions for all six equivalence classes. In addition, we obtain the joint distribution for the patterns in the class containing the well-known permutation statistic known as the strict fixed point. Furthermore, computer experiments suggest that at most 124 pairs of mesh patterns of type 12 and 21 with identical shading are equidistributed. Using symmetry operations, we partition these pairs into 38 equivalence classes with respect to distribution. By explicitly determining 24 of these distributions (in many cases, in fact, joint equidistributions of the respective pairs), we reduce the number of equivalence classes to~31, which turns out to be the true number of equivalence classes. Enumerating 14 of these classes is left as an open problem.