Papers

We study the FiboLaplace and LucasLaplace sequences obtained by applying the Laplace transform to generalized Fibonacci-type and Lucas-type polynomials. We relate these families and show that, for each fixed transform parameter, the FiboLaplace sequence is holonomic. We give a combinatorial interpretation in terms of weighted colored tilings, leading to recurrence relations, identities, and a triangular refinement by the number of dominoes. We also derive two continued-fraction expansions and obtain a second combinatorial interpretation in terms of generalized Motzkin paths. These results extend earlier work of Givens and Moll.

A pattern is a fundamental object used in the proof of Duron, Mählmann and Toruńczyk to show that hereditary 2-wqo graph classes have bounded clique-width. We answer a question in that paper by exhibiting a pattern-free hereditary graph class that is not 2-wqo.

For an oriented graph $G$ the oriented chromatic number of $G$, written $\chi_o(G)$, is the least integer $t$ such that $G$ has a homomorphism to a tournament on $t$ vertices. The oriented chromatic number of a simple graph $H$ is the maximum oriented chromatic number over all orientations of $H$. Borodin, Kostochka, Nešetřil, Raspaud, and Sopena proved in 1999 that for all $\epsilon>0$, graphs with maximum average degree less than $4-\epsilon$ have bounded oriented chromatic number. This is in some sense optimal, because $1$-subdivisions of cliques demonstrate that there exists graphs with maximum average degree strictly less than $4$ and oriented chromatic number $\Omega(\sqrt{n})$. We prove that for every positive integer $d$, every $d$-degenerate graph $G$ with sufficiently large order satisfies $\chi_o(G) \leq 6(1+\frac{9d^2}{4})^{\frac{1}{2}}d 8^{d}\sqrt{n}$. This implies for a fixed $r\geq 4$, the optimal bound for the oriented chromatic number of graphs with maximum average degree less than $r$ is $\Theta(\sqrt{n})$. This complements a bound of Wood, who showed that for all $n$ vertex graphs $\chi_o \leq 2\Delta\sqrt{n-1}$ where $\Delta$ is the maximum degree.

We show that the tadpole Nahm sum is essentially a specialization of a series studied by Bartlett and Warnaar. This overlooked connection was first discovered by the internal model mathvision-harness-0.3 at MathVision AI. We then use Macdonald-type identities for the Bartlett-Warnaar series to express the principal tadpole Nahm sum and its twisted version in terms of a Wronskian of generalized theta series. The principal case confirms a conjecture of Milas and Wang.

Akbari, Elphick, Kumar, Pragada and Tang [Discrete Math. 349 (2026) 114953] conjectured that for every connected graph G, the line graph of G has at most one more positive than negative adjacency eigenvalue; equivalently, the signature of a connected line graph is at most 1. We refute the conjecture with two independently found counterexamples: a 14-vertex cactus consisting of two pentagons attached by bridges to adjacent vertices of a square, whose line graph has inertia (9,0,7) by an exact characteristic-polynomial certificate, and a 48-vertex triangle-free graph found by simulated annealing and verified in exact rational arithmetic. Indeed, chaining copies of the 14-vertex graph yields connected graphs on 14k vertices whose line graphs have signature k+1 for every k >= 1. The signature of connected line graphs is therefore unbounded, and no constant-bound repair of the conjecture is possible.

Let $F(n)$ be the largest size of a subset of $\{0,1,\ldots,n-1\}^2$ containing no nondegenerate isosceles right triangle. We give a modified Salem–Spencer-type construction over the Gaussian integers showing that $F(n)=\Omega(n^{1.3})$. The best known upper bound is $F(n)\ll n^2/(\log n)^{1+c}$ for some absolute constant $c>0$, so there is still a large gap between the bounds.

Let \(P_\eps\) be the fence poset associated with an orientation \(\eps\in\{+,-\}^{n-1}\) of a path. We define a greedy right-to-left record statistic \(\rec_\eps\) on \(S_n\) and prove \[ \sum_{\pi\in S_n}t^{\rec_\eps(\pi)}=n!\Omega(P_\eps;t), \] by a Bernstein-basis transfer between a continuous threshold recurrence and endpoint-refined order-preserving maps. Under reflection, this statistic agrees pointwise with Kahane's independently obtained greedy block statistic; the alternating specialization gives the zig-zag case posed by Ferroni, Morales, and Panova. A finite form of the transfer yields a direct recursive bijection for \(m\le n\), extended algorithmically to arbitrary alphabets. Refining by record set, direction, and terminal value identifies fixed fibers with decorated endpoint paths and pointed linear extensions of posets whose cover graphs are caterpillars. We also define cyclic records for every nonconstant orientation \(\eta\) of a cycle and prove \[ \sum_{\pi\in S_n}t^{\operatorname{crec}_\eta(\pi)} =n!\Omega(C_\eta;t). \] When the Hasse diagram is a cycle, reflection identifies these records with Kahane's circular blocks and establishes his circular-fence conjecture.

We give counterexamples to Rota's 1970 conjecture that the sequence counting flats of varying rank in a matroid is unimodal. More specifically, inspired by Larson's recent disproof of the stronger log-concavity conjecture of Mason, we explain a mechanism which turns failures of log-concavity for flats into failures of unimodality under suitable conditions.

The spherical random geometric graph $G(n,d,p)$ is obtained by sampling $n$ independent points uniformly on the unit sphere $\mathbb{S}^{d-1}\subseteq\mathbb{R}^d$ and joining pairs of points which are sufficiently close, where the threshold is chosen so that the edge probability is $p$. The central question related to this model, and to a broad class of other models, is the following: when does the underlying geometry affect the resulting graph in a way which makes it distinguishable from the Erdős–Rényi random graph $G(n,p)$, as measured in total variation distance? The precise answer to this question was conjectured by Bubeck, Ding, Eldan, and Rácz, who predicted that $G(n,d,p)$ and $G(n,p)$ are indistinguishable precisely when $d \gg n^3p^3(\log p^{-1})^3$, and provided a test for distinguishing these models in the low-dimensional regime. Although this conjecture attracted considerable attention from researchers in probability, theoretical computer science, and high-dimensional statistics, it was previously fully proved only in the constant-density case. In this paper, we resolve the distinguishability conjecture in the broad range $1/3 \geq p \geq n^{-1/5} \text{polylog}(n)$. The key ingredient of our proof is a stronger statement which gives a precise asymptotic formula for the probability that $G(n,d,p)$ realizes a prescribed graph $H$: above the conjectured threshold, this probability is at most $(1+o(1))$ times the corresponding probability for $G(n,p)$, with the signed triangle count of $H$ appearing as the leading correction term.

Let $G = (X, Y; E)$ be a bipartite graph with parts $X$ and $Y$ where $|X|=m$ and $|Y|=n$. We show that every bipartite graph with more than $mn - D(m,n)$ edges has positive Lin–Lu–Yau curvature, where $D(m,n)=m-2+\lceil{\frac {n}{2}\rceil} \text{ if $n\geq 2m$}, \mbox{and} \ n-1 \text{ if $m\leq n< 2m$}.$ We also show that every bipartite graph of order $m+n$ with $m \geq n$ and minimum degree at least $\min\{n, \lfloor{\frac{m+n}{3}\rfloor}+1\}$ has positive Lin–Lu–Yau curvature. Both bounds are sharp. Meanwhile probabilistically we can relax the edge density conditions in above results. It is shown that relatively dense random bipartite graph is positively curved. All of our proofs are based on a new formula for Lin–Lu–Yau curvature of bipartite graphs.

In 1976, George Spencer-Brown announced a proof of the four color theorem, using operations on Tait colorings for trivalent plane graphs. In subsequent work he formulated these operations in terms of an algorithm that he called a parity-pass and claimed that when the parity pass algorithm is performed on a non-polar pentagon region, it necessarily terminates in an edge coloring that is extendable to the entire graph. We provide here a counterexample to show that this claim is false. We then raise questions related to the existence of this sort of counterexample.

The principle of maximum entropy provides a fundamental framework for characterizing typical structures of large random networks subject to observable constraints. In their pioneering numerical experiments \cite{radin2014asymptotics}, Radin, Ren, and Sadun conjectured that entropy-maximizing graphons satisfying subgraph density constraints are stochastic block models a conjecture we term the RRS conjecture. While several special cases have been proven for single-relation graphs with specific constraint families, the general problem has remained open, particularly for multi-relational networks. We resolve the RRS conjecture for constrained multi-relational graphons in the non-extremal regime, proving that entropy-maximizing solutions are step functions with finitely many blocks under the condition the subgraph density constraints are analytically independent and for almost all feasible combinations of sufficient statistics. Our proof employs a differential geometric technique to study solutions of constrained optimization problems in function space via functions with a finite parametrization (step functions). The two cornerstones of this work are: the generalization of subgraph density notion to $h$-subgraph density and the proof that manifolds that define the constrained region for the solutions maintain topological stability without developing new connected components under refinement. Together, these enable proving that no new global optima emerge in higher-dimensional spaces.

We present results around an isoperimetric problem built on polyforms: What is the biggest enclosed area one can build using polyforms in each of the three plane tessellations? We give challenges to the readers and present Shimauchi's proof of the biggest area a fence made of pentominoes can enclose. A translation of the instance using integer linear programming is also given. A companion web app is available to test some of the challenges we propose and for activities, and we included extra pages with a cutout handout of the board and pieces of the puzzles, so that you can print and cut them to read this paper hands on.

In 2011/12, Ruskey, Sawada, Stevens and Williams showed that a binary cut-down de Bruijn sequence can be constructed containing all $n$-tuples of Hamming weight either $r$ or $r+1$ for every possible $r$, and no others. In this paper we examine extensions of this result that require choosing a weight-like function applying to $n$-tuples with symbols taken from an alphabet of arbitrary (finite) size. We consider three possible such weight functions, and in each case establish an analogous result to that of Ruskey et al.

We introduce a stochastic model for the papal conclave in which $n$ cardinals vote repeatedly among themselves until one cardinal receives all the votes. In each round, the probability that a cardinal votes for a given candidate is proportional to the $\alpha$-th power of that candidate's vote count in the preceding round. For $\alpha=1$, the model reduces to the Wright-Fisher model and is dual to Kingman's n-coalescent. We reveal a sharp transition in the absorption time $\mathcal{T}$ at $\alpha=1$. It was known that when $\alpha=1$, $\mathcal{T}$ is typically of order $n$. We prove that for $\alpha>1$, it drops to order $\textit{loglog n.}$ In contrast, for $\alpha<1$, $\mathcal{T}$ is typically at least $\exp(\Omega(n))$. We also prove a sharp phase transition in the identity of the winner when $\alpha>1$. For every positive integer $k$, if $2^{1/k}<\alpha<2^{1/(k-1)}$ (where we write $2^{1/0} = +\infty$), with probability tending to 1 as $n\to\infty$, the eventual winner is the unique leader after round $k$. These results show that reinforced voting processes reach consensus remarkably quickly even for large electorates.

We prove uniqueness of $q$-rational numbers up to conjugacy, using character varieties. Despite the uniqueness, we exhibit a two-parameter family of deformations of rationals with a modular symmetry. We prove that there are exactly two deformations which deliver the usual $q$-integers: the original $q$-rationals defined by Morier-Genoud and Ovsienko, and another new one. Although the new family can be obtained by conjugacy from the old one, new positivity properties appear. In addition, this new family provides a direct computation of the Jones polynomial of rational knots.

For partitions lambda, mu, nu the Littlewood-Richardson coefficient stretches to a function P(t) = c(t*nu; t*lambda, t*mu) which, by a theorem of Derksen and Weyman, is a polynomial in t. King, Tollu and Toumazet conjectured that P has no negative coefficient. The conjecture is known only for c <= 2 and is otherwise open. We prove it for all triples whose parts number at most five. For at most four parts the proof is structural: a period-one dilation transfers the Berline-Vergne local Ehrhart formula from an integral dilate back to the rational hive polytope, and every two-dimensional transverse cone spanned by rank-four rhombus normals has positive weight (minimum 1/9). Five parts need two further ingredients. A closed-chamber transfer lemma, resting on Rassart's polynomiality of the coefficients on the closed cones of a chamber complex, reduces positivity for a fixed number of parts to full-dimensional hives. For full-dimensional five-part hives all coefficients but the linear one were already known to be positive; the linear one is where pointwise positivity of the local weights fails – an edge cone of weight -347/109824 occurs on an actual hive – and its nonnegativity is proved by an exact global certificate: a rational correction supported on 6,903 two-face types, balanced by the Minkowski closure of each two-face polygon, which makes every one of the 87,127 closed edge cones adjacent to them nonnegative. The same local method yields a rank-uniform consequence: for every full-dimensional hive polytope of any rank the top four Ehrhart coefficients are positive. We close by recording the exact general frontier and the obstructions that rule out the standard shortcuts. All finite verifications are exact and accompanied by independent replay scripts.

Let $L$ be a fixed set of positive integers. A family $\mathcal{F}\subseteq 2^{[n]}$ is called $L$-differencing if $\lvert A\setminus B\rvert\in L$ for every ordered pair of distinct members $A,B\in\mathcal{F}$. A longstanding conjecture of Frankl, proposed in 1985, asserts that every $L$-differencing family has size at most $\binom{n}{|L|}$. We resolve this conjecture asymptotically for every fixed $L$, and obtain the exact answer in the only case in which the conjectured bound could be tight. (1) If $L\ne [s]$ and $n$ is large, then every $L$-differencing family satisfies $\lvert \mathcal{F}\rvert \le \left(\frac{s}{s+1}+o_L(1)\right)\binom{n}{s}$. (2) If $L=[s]$ and $n\ge 2s-1$, then $\lvert \mathcal{F}\rvert\le\binom{n}{s}$, with equality only for $\binom{[n]}{s}$ and $\binom{[n]}{n-s}$. The first result follows by reducing directed differences to restricted Hamming distances. For the exact result, we develop a new homogeneous polynomial method, which might be of independent interest.

An additive $(n,k,d)_{q^m/q}$-code is a $\mathrm{GF}(q)$-linear subspace of $\mathrm{GF}(q^m)^n$ of $\mathrm{GF}(q)$-dimension $km$ with minimum Hamming distance $d$. We first extend the Alderson–Bruen–Silverman (ABS) model of linear codes to the additive setting: a code of length $n$ with $q^{km}$ words over an alphabet of size $q^m$ admits an ABS model if and only if it is equivalent to a nondegenerate additive code. We then ask whether an additive code that admits an extension must admit an additive extension. For linear codes ($m=1$) this is a theorem of Alderson and Gács. We characterize the additive codes admitting no additive extension as those whose associated projective system of flats is complete, and we prove that the answer to the question above is again affirmative for $(n,2,d)_{9/3}$-, $(n,2,d)_{4/2}$-, and $(n,3,d)_{4/2}$-codes. In contrast with the linear case, we show that the answer is negative in general. Scattered linear sets yield, for each square $q$, extendable additive $(n,2,d)_{q^2/q}$-codes admitting no additive extension. Further, a different method yields an extendable additive $(30,2,24)_{8/2}$-code with no additive extension. Consequently, for properly additive codes, completeness of the associated projective system does not imply maximality of the code. We conjecture that extendable $(n,2,d)_{p^2/p}$-codes, $p$ prime, always admit additive extensions.

Tutte's $4$-flow conjecture asserts that every finite bridgeless graph with no Petersen minor admits a nowhere-zero $4$-flow. Let $P$ be the Petersen graph and let $e\in E(P)$. We prove that every finite bridgeless $(P/e)$-minor-free multigraph admits a nowhere-zero $4$-flow. Since $P-e$ and $P/e$ are the two maximal proper minors of $P$, combining our result with the theorem of Thomas and Thomson for $(P-e)$-minor-free graphs shows that, for every proper minor $R$ of $P$, every finite bridgeless $R$-minor-free graph admits a nowhere-zero $4$-flow. Equivalently, every finite bridgeless graph without such a flow contains every proper minor of $P$. The proof builds on the girth-five structural framework of Thomas and Thomson together with the nonplanar extension theorem of Norin and Thomas.

In this paper we construct a recursive bijection between $4$-valent maps endowed with a Eulerian orientation – also known as the ice model – and a family of unary-binary trees. This answers a question of Bousquet-Mélou and Elvey Price, who established that both these families have the same generating function in arXiv:2503.15046 .

We study the Mersenne representation of nonnegative integers and its decomposition into the binary and nonbinary sides. The nonbinary values form A055938, and their successor structure gives a direct proof of the relation between A055938 and A080578 that is recorded as conjectural in the OEIS entry for A080578. The binary-side counting function is identified with a shifted Conolly sequence. We then develop the parent map, truncation blocks, truncation remainders, and the Mersenne tau function associated with this representation. The parent map is conjugate to deletion of the lowest digit. Differences of the Mersenne tau rows recover the parent iterates and the counting function, and they give formulas for digit reconstruction and for a diagonal tau defect. Finally, we revisit a known finite-depth one-soliton family of the finite-field BBS. The Mersenne combinatorics is used directly to reconstruct a global integer-valued traveling-wave profile and to prove an integer window-counting theorem. Reduction modulo 3 yields the corresponding finite-field traveling-wave solutions. We also construct an integer-valued traveling-wave tau function whose front values are given by the Mersenne tau rows. The resulting construction shows how the combinatorics of a number representation can enter directly into the reconstruction of solutions of an integrable system.

In 2024, Cisto et al. introduced polyocollections and polyocollection ideals, which generalize the notions of collections of cells and inner $2$-minors ideals, respectively. In this paper, we naturally extend the notions and results about zig-zag walk, zero-sum condition, rook number, and switching polynomial from collections of cells to polyocollections, and we define a class of polyocollections, called natural polyocollections, whose structure is similar to that of collections of cells. We focus on natural polyocollections whose polyocollection ideals admit quadratic Gröbner bases with respect to lexicographic order induced by some specific orders on vertices. Using the zero-sum condition, we prove the primality of this class of polyocollections, which shows that the zig-zag conjecture proposed by Mascia et al. holds true for collections of cells satisfying the aforementioned properties. Moreover, we show that $h$-polynomials and regularities of the coordinate rings of this class of polyocollections are equal to their switching rook polynomials and rook numbers, respectively. These results give positive answers to the switching rook polynomial conjecture proposed by Jahangir and Navarra, and the rook number open problem proposed by Rinaldo and Romeo for collections of cells satisfying the aforementioned properties.

Grouping species according to their phylogenetic relationships often results in different groups than grouping them according to their shared traits. Monophyletic groups play an important role in this regard, as they are groups of species sharing the same trait and being uniquely defined by a joint phylogenetic subtree. This immediately leads to the question of how to identify possible monophyletic groups in characters, which assign each present-day species a certain trait and which are typically used for phylogenetic tree reconstruction. In our manuscript, we provide a general formula to quantify how many different characters are monophyletic on any given tree and provide simple formulae for binary characters and for certain tree shapes. We also investigate relations between monophyly and the well-known phylogenetic tree reconstruction criterion maximum parsimony by providing a linear-time algorithm which determines the parsimony score together with the monophyly type of a character on a tree.

For an oriented graph $D$, let $\vec{\alpha}(D)$ be the maximum order of an induced acyclic subdigraph, $\vec{\chi}(D)$ its dichromatic number, and $\mathrm{fas}(D)$ the minimum number of arcs whose deletion makes $D$ acyclic. We prove that for every fixed $\zeta \in (0, 1/2)$, there are triangle-free graphs $G_n$ on $n$ vertices such that a uniformly random orientation $D_n$ satisfies, $$ \left( \frac{1}{2} - \zeta \right) e(G_n[U]) < \mathrm{fas}(D_n[U]) \leq \frac{1}{2} e(G_n[U]) $$ with probability at least $1-\exp\!\left[-\Omega_\zeta\!\left(\sqrt n\,(\log n)^{3/2}\right)\right]$ simultaneously for every vertex set $U$ of size at least $C_\zeta\sqrt{n\log n}$. The upper bound is universal, so the feedback-arc ratio can be made arbitrarily close to the largest possible value, uniformly over all sufficiently large induced subdigraphs. In particular, $\vec{\alpha}(D_n) = O(\sqrt{n \log n})$, and every linear-size induced subdigraph has dichromatic number $\Omega(\sqrt{n/\log n})$. This yields $\vec{\alpha}(n) = \Theta(\sqrt{n \log n})$ and $\vec{t}(n) = \Theta\left(\sqrt{\frac{n}{\log n}}\right)$, where $\vec{\alpha}(n)$ and $\vec{t}(n)$ denote, respectively, the minimum of $\vec{\alpha}(D)$ and the maximum of $\vec{\chi}(D)$ over all oriented triangle-free graphs $D$ of order $n$. This confirms two conjectures of Aboulker, Havet, Pirot, and Schabanel.

We prove that for every fixed $\lambda>0$ and all sufficiently large $n$, any $z_1,\dots,z_n\in\C$ with $|z_j|\geq1$ satisfy $\max_{2\leq k\leq n+1}|\sum_j z_j^k|>e^{-\lambda n}$. Consequently, the $n$th root of the optimal maximum tends to $1$, so no constant $C>1$ in Erdős 973 can exist. The proof combines a truncated exponential factorization with overconvergence on an open set outside the unit disk and a normal-family obstruction for Cauchy transforms.

We study block polytopes whose variables are divided into equal-size blocks and whose local inequalities bound the total contribution of adjacent blocks. For blocks arranged along a path, we develop a transfer-matrix enumeration in the length direction. We also carry out an Ehrhart-theoretic analysis in the dilation direction. The original transfer matrix admits a compression to a weighted height matrix, and the numerator and denominator of the length generating function are described by explicit recurrences and determinant formulas. We also study the cyclic analogue, where the length generating function is governed by the logarithmic derivative of the same determinant. On the Ehrhart side, the path polytopes with at least two blocks and the even cyclic polytopes are stable-set polytopes of perfect graphs; consequently they are Gorenstein of codegree $2a + 1$ (independent of the number of blocks $m \ge 2$), satisfy an explicit Ehrhart–Macdonald reciprocity, and have palindromic unimodal $h^*$-polynomials of degree $a(m-2)$. Odd cyclic polytopes have denominator exactly two, and their lattice-point enumerators are Ehrhart quasipolynomials of period dividing two. Further combinatorial interpretations and open problems are discussed.

Erdős and Gyárfás conjectured in 1995 that, in every red–blue edge-coloring of a complete graph $K_n$, the vertex set can be covered by at most $\sqrt n$ monochromatic paths, all of the same color. Pokrovskiy, Versteegen and Williams (JCT-B, 2026) proved the conjecture for all sufficiently large $n$. In this paper, by using minimal counterexample method, we confirm the conjecture completely.

We introduce regularized bivariate affine $q$-Krawtchouk polynomials and show that they give the first eigenmatrix of a translation association scheme on $\operatorname{Mat}_{d\times n}(\operatorname{GR}(p^2,r))$. The relations are defined by Smith type, and the corresponding eigenvalues are written as character sums over Smith type classes. The proof is based on recurrence relations obtained from the transition numbers describing how Smith types change when one row and one column are added to a matrix. These recurrences identify the character sums with the regularized bivariate affine $q$-Krawtchouk polynomials.

Let $P_4^r$ denote the $r$-uniform expansion of the graph path with four edges. We prove that every $n$-vertex linear $r$-uniform $P_4^r$-free hypergraph has at most $(r+1)n/r$ edges, resolving a conjecture of Adak and Verma for every $r \geq 2$. Equality holds precisely for vertex-disjoint unions of Steiner systems $S(2,r,r^2)$. The main ingredient is a sharp incidence-rank inequality. If $N(H)$ is the edge-vertex incidence matrix of a linear $r$-uniform hypergraph whose line graph is a cograph, then $(r+1)\operatorname{rank}_{\mathbb{R}} N(H) \geq r|E(H)|$. Equality holds exactly when every edge-containing component is an $S(2,r,r^2)$. The proof follows the union-join decomposition of cographs. At a join node, the row-difference spaces of the co-components are mutually orthogonal, and the possible rank defect is determined by balanced co-components. Perron-Frobenius theory identifies the smallest balanced pieces as parallel classes of $r$ disjoint $r$-sets, while an orthogonality argument bounds their number by $r+1$. The equality case then reconstructs the Steiner system. The linear Turán bound follows from $\operatorname{rank}_{\mathbb{R}} N(H) \leq |V(H)|$.