Papers

We pin down the largest entries possible in positive integral friezes of types $D_n$ for $n\geq 4$ and $B_n$ for $n\geq 2$, addressing a conjecture of Robin Zhang. For type $D_n$, the sharp upper bound is $F_nF_{n+1}-1$, and for type $B_n$, it is $F_{n+1}F_{n+2}-1$, where $F_k$ are the Virahanka–Fibonacci numbers.

On a network with a fixed set of verified sources, discounted averaging induces an equilibrium support $h_i^S=\mathbb{E}_i[\lambda^{T_S}]$, the discounted probability that a random walk reaches $S$ before attenuation. We define the discounted hitting domination number $\delta_{\lambda,\tau}(G)$ as the minimum number of sources required to guarantee $h_i^S\ge\tau$ at every vertex. Although this potential is known through penalized and group hitting probabilities, the associated minimum-cardinality uniform-coverage problem appears to be new. Aggregate support is monotone submodular, while the uniform-floor problem is an exact submodular-cover problem. Moreover, if $\lambda^{r+1}<\tau\le\left(\frac{\lambda}{\Delta}\right)^r$, then $\delta_{\lambda,\tau}(G)$ equals the distance-$r$ domination number. This yields NP-completeness and APX-completeness at $(\lambda,\tau)=(1/4,1/14)$ on graphs of maximum degree three. For spiders, we obtain an exact finite-state characterization and a polynomial-time algorithm for every fixed rational pair $(\lambda,\tau)$, and show that the branching vertex need not belong to a minimum source set. Finally, an exact mixed-integer linear formulation certifies optimal placements on a real network and a synthetic graph and demonstrates substantial differences from degree, closeness, and classical domination.

The classical ADE classification implies that $E_8$ is the unique irreducible unimodular Euclidean lattice generated by vectors of norm $2$. In sharp contrast, for every positive integer $m$, we construct an irreducible odd unimodular lattice of rank $24m$ and minimum norm $3$ that is generated by its minimal vectors.

We show that there exists a constant $\epsilon > 0$ such that if $C$ is a conjugacy class in $A_n$ of size at least $|A_n|^{1-\epsilon}$, then $A_n \setminus \{1\} \subseteq C^2$. This proves the robust version of Thompson's conjecture for the alternating group, conjectured by Shalev (Annals of Math., 2009). Our proof combines character bounds and combinatorial cancellation techniques with the recent theory of hypercontractivity for functions over symmetric groups.

We study the order dimension of Cartesian products of finite posets. Kelly and Trotter conjectured in 1982 that $\dim(P\times Q)\ge\dim P+\dim Q-2$ for all finite posets $P$ and $Q$. For $m\ge3$, let $R_m$ denote the incidence poset of the complete graph on $m$ vertices. We prove that there is a constant $C$ such that, for all sufficiently large $m$, $\dim(R_m\times R_m)\le\left(1+\frac{2}{\log_2 6}\right)\dim R_m+C$. Since $1+2/\log_2 6<2$, this disproves the Kelly–Trotter conjecture and shows that $2\dim R_m-2-\dim(R_m\times R_m)$ can grow linearly with $\dim R_m$. For every integer $d\ge8$, we construct an incidence poset $Q_d$ such that $\dim Q_d=d$ and $Q_d$ has the $(3,d)$-covering property. Consequently, $\dim(P\times Q_d)\le\dim P+d-3$ for every poset $P$ with $\dim P\ge3$. Thus, for every integer $d\ge8$, the poset $Q_d$ violates the Kelly–Trotter conjecture with every poset of dimension at least $3$. Finally, we prove that a poset $Q$ has an $(r,s)$-covering if and only if $\dim(Q\times C^r)\le s$ for every finite chain $C$ with at least two elements.

This paper explores variations of vertex-coloring problems defined on graph visibility properties. It introduces and studies the dual, outer, and total mutual-visibility chromatic numbers, which partition the vertex set of a graph into color classes that preserve specific mutual-visibility conditions called dual, outer or total. The work provides structural conditions under which these chromatic parameters are finite or infinite, and establishes that deciding whether a graph admits a dual, outer, or total mutual-visibility coloring using a given number of colors is NP-complete, even when restricted to two colors. Exact formulas and tight bounds for these chromatic parameters are established across several fundamental graph classes. For block graphs, complete characterizations are provided for the outer and dual mutual-visibility chromatic numbers based on structural invariants such as cut vertices and specific forbidden subgraph structures. On Hamming graphs, the dual and total mutual-visibility chromatic numbers are shown to equal the smaller dimension of the factors, while the outer mutual-visibility chromatic number is proven to equal the star arboricity of a corresponding complete bipartite graph. Finally, the paper examines strong grid graphs, determining exact values for their total, outer, and dual mutual-visibility chromatic numbers. These results demonstrate how the parameter behaviors range from finite constants to infinity depending on the grid dimensions.

Let $p>3$ be a prime, and let $b,c$ be integers with $p\nmid b+2c$. We obtain an explicit congruence modulo $p^2$ for the sum of $\binom{2k}{k}T_{2k}(b,c^2)/(4^k(k+1)(b+2c)^{2k})$ from $k=0$ to $(p-1)/2$, where $T_n(b,c)$ denotes the generalized central trinomial coefficient. This gives a parametric formula for the sum considered in a question of Wang and Cui. The proof uses a constant term representation and a logarithmic generating function to reduce the sum to two coefficients of an algebraic generating function. A differential identity and a coefficientwise polynomial congruence then yield the desired evaluation. The formula also applies when $p$ divides $b$ or $b-2c$.

The number of unlabeled regular graphs can be expressed as an average of fixed-point counts over vertex permutations, but evaluating each fixed-point count still requires the degree constraints to be enforced. We give an exact recurrence that processes one complete permutation cycle at a time and records the remaining cycles only by their lengths and residual degrees. The recurrence combines internal edge orbits with orbits joining distinct cycles, while binomial and multinomial coefficients retain the multiplicities of choices that lead to the same remaining state. We prove that this state description is sufficient under complete-cycle elimination and derive bounds on the number of states and transitions. For every fixed degree, the resulting algorithm has an $\exp(O(\sqrt n))$ upper bound in the number of vertices, including integer-arithmetic costs. The quartic case requires only four positive residual-degree classes for each cycle length. Small-instance comparisons with a separately implemented, vertex-indexed edge-orbit calculation verify both regular and nonuniform residual-degree inputs. The quartic calculation gives unrestricted and connected counts through order 50, including 22 orders beyond the corresponding reference tables through order 28. Connected counts are recovered by the inverse Euler transform, and all 22 identity-permutation contributions for orders 29–50 agree with the published labeled counts. The nonidentity fixed-point terms at these orders have not been independently recomputed.

We show that for every $n$ unit vectors $v_1, \dots, v_n$ in the $d$-dimensional Euclidean space, there exist signs $\varepsilon_1, \dots, \varepsilon_n \in \{\pm 1\}$ such that $\lVert \varepsilon_1 v_1 + \dots + \varepsilon_n v_n \rVert \ge \sqrt{2n - d}$, and we characterize the equality cases.

Motivated by Brouwer's conjecture, Ashraf, Omidi and Tayfeh-Rezaie proposed the following Brouwer-type conjecture that for every graph $G$ on $n$ vertices with $m$ edges, the sum $S_k^+(G)$ of its $k$ largest signless Laplacian eigenvalues satisfies $S_k^+(G)\le m+\binom{k+1}{2}$ for $k=1, \ldots, n$. In this paper, we prove that the above conjecture holds. Moreover, the equality holds if and only if $k=1$ and $G$ is either star $K_{1,a}$ or triangle $K_3$ with adding some isolated vertices. For split graphs, properties of block signless Laplacian matrices based on clique and independent set are adapted. While for non-split graphs, some spectral graph substructure are used to control the sum of signless Laplacian eigenvalues.

Place a queen in each successive column of an infinite $\mathbb{N}\times\mathbb{N}$ chessboard, always choosing the lowest row such that no two queens may attack one another. We prove that the row $q_n$ occupied by the queen in the $n$th column satisfies $q_n=n\phi+O(1)$ or $q_n=n/\phi+O(1)$, where $\phi=(1+\sqrt5)/2$ is the golden ratio.

A packing of $n$ congruent balls in $\mathbb{R}^3$ is a family of interior-disjoint Euclidean balls all having the same radius. The contact number of a packing is the number of touching pairs of balls. In this paper we investigate the problem of determining the maximum contact number, $c(n)$, of a packing of $n$ congruent balls in $\mathbb{R}^3$. We first show that all packings of $n$ congruent balls that have a contact number of $c(n)$ are minimally rigid. Furthermore, we show that $c(n)=3n-6$ for $n=6,7,8,$ and $9$. These two results resolve a conjecture of K. Bezdek and Khan. During the proof of the latter result, we also enumerate the contact structures of all packings of $n$ congruent balls with contact number $c(n)$ for $n=6,7,$ and $8$. Additionally, we provide a lower bound construction which shows $c(n)> 6n-6\sqrt[3]{2}n^\frac{2}{3}$ when $n=16k^3-33k^2+24k-6$ where $k\in \mathbb{N}$. We also look at the restricted problem where each ball is centered on the face-centered cubic lattice $A_3$. In this case let $c_{A}(n)$ denote the maximum contact number. We show that $c_{A}(n)\leq 6n-\frac{6}{\sqrt[6]{2}}n^\frac{2}{3}$ for all $n$, and determine the asymptotics of $c_{A}(n)$ to be $c_{A}(n)=6n-(1+o(1))6\sqrt[3]{2}n^\frac{2}{3}$.

We study hyperedge partial duals of finite hypermaps in a purely combinatorial framework, without assuming orientability. A hypermap is represented by three fixed-point-free involutions $(\tau_0,\tau_1,\tau_2)$ on its flag set. We first give an explicit construction of the medial map from this model: $02$-orbits become the medial vertex discs, while $\tau_1$-transpositions become the medial bands; a local orientation system and its twist data then provide a signed rotation description of the medial map. We next prove that the state circles associated with a chosen set of hyperedges are in natural bijection with the vertex orbits of the corresponding partial dual, yielding a crossing-total characterization of all Eulerian hyperedge partial duals. For bipartiteness, the twist data lead to a modified medial map in which inserted bars record the obstruction to a global orientation. We prove that a partial dual is bipartite if and only if its dualized hyperedge set is exactly the set of $c$-type hyperedges identified by an all-crossing orientation of this modified medial map. When the hypermap is orientable, these constructions specialize to the known orientable-hypermap results; when every hyperedge has valence two, they specialize to the ribbon-graph results.

The harmonic centrality of a vertex $v$ in a graph $G = (V,E)$ is the sum of reciprocals of distances of vertices of $G$ from $v$. The vertices of $G$ which have the maximum (minimum) harmonic centrality form the harmonic center (or periphery, resp.) of $G$. We study harmonic centers of graphs and their localization in graph blocks, presenting sufficient conditions for graphs (in terms of diameter or number of edges) to have those centers contained in a single block; in addition, we show that each connected graph is the harmonic center as well as harmonic periphery of some graphs.

For distinct integers $a$ and $b$, an $\{a,b\}$-edge-weighting assigns $a$ or $b$ to each edge and labels each vertex by the sum of its incident weights. Such a weighting is proper if adjacent vertices receive distinct labels. We prove that, for every fixed pair of distinct integers, deciding whether a proper weighting exists is NP-complete even for simple cubic planar graphs. On planar multigraphs with $m$ edges, we give an exact $2^{O(\sqrt m)}$-time algorithm and, assuming the Exponential Time Hypothesis (ETH), exclude $2^{o(\sqrt m)}$-time algorithms even for simple cubic planar graphs. As a consequence, locally irregular $2$-edge-coloring is NP-complete on simple cubic planar graphs, admits a deterministic $2^{O(\sqrt n)}$-time algorithm on $n$-vertex graphs in this class, and admits no $2^{o(\sqrt n)}$-time algorithm under ETH. For maximizing the number of edges joining vertices with distinct labels, we give a deterministic efficient polynomial-time approximation scheme (EPTAS) on planar multigraphs, a polynomial-time $1/2$-approximation on multigraphs, and APX-completeness even on simple cubic graphs. Extending a partial $\{a,b\}$-edge-weighting to a proper one is NP-complete for every fixed pair even on simple cubic planar bipartite graphs, while it is polynomial-time solvable on trees. The hardness persists even when the prescribed edges form disjoint paths of length $6$ and all edges of each path have the same prescribed weight.

Andrews and Newman \cite{AN19, AN20} defined the minimal excludant or mex of a partition. The mex of a partition is the smallest positive integer which is absent from the partition. Baruah, Bhoria, Eyyunni and Maji \cite{BBEM} studied the sum of mex split according to parity, together with its $\ell$-th moments. Ballantine and Merca \cite{BM20} generalized mex to the least $s$-gap, which is the smallest natural number that does not occur minimum $s$ times in the partition. Baruah and Talukdar \cite{BT} conjectured a corresponding asymptotic equivalence between the sums of odd and even least $s$-gaps for every $s>1$, generalizing a theorem of Barman and Singh \cite{BS} for the classical mex. In this article, we derive exact formulas for the $\ell$-th moments of $\smex(\pi)$ for every fixed $\ell\ge 1$, in terms of partition functions. We give a complete proof of the conjecture of Baruah and Talukdar \cite{BT} for every natural number $s>1$. We also generalize an identity of Hopkins, Sellers and Stanton \cite{HSS} to the least $s$-gap setting.

We introduce Boolean trusses, that is, trusses in which every element is idempotent. Every Boolean truss admits a decomposition into a truss arising from a Boolean ring and a rectangular truss. Furthermore, we classify all Boolean trusses up to isomorphism.

We classify the real characters of the Grossman-Larson Hopf algebra that are nonnegative on the rooted-tree basis. They vanish on trees with branching away from the root, and the normalized characters are parametrized by Kingman paintboxes. Two-sided Pieri states are mixtures of the normalized characters, with unique mixing measures. The corresponding laws form a proper exposed Bauer face of the simplex of central measures on the Hoffman rooted-tree graph. For the path-forest subgraph, the full and minimal Martin boundaries coincide and are homeomorphic to the Kingman simplex. The limiting ranked root-branch frequencies generate the completed central tail.

The study of preordered semirings is motivated by applications in computer science, graph theory, and information theory, and provides tools for understanding the asymptotic preorder, which compares large powers of a pair of elements. This paper studies sequences which behave approximately as sequences of powers, but are not necessarily equivalent to geometric sequences. Our main result is that preordered semirings admit completions where such sequences, that we call approximately geometric, become equivalent to geometric sequences, and that existing characterizations of the asymptotic preorder extend to the completion. We provide several classes of examples of approximately geometric sequences in the semiring of tensors, and in the semiring of graphs. As a concrete application, we determine the strong converse exponent for binary hypothesis testing with composite Markov hypotheses.

A connected graph $G$ with at least two vertices is matching covered if each of its edges lies in a perfect matching. A matching covered graph is minimal if the removal of any edge results in a graph that is no longer matching covered. Lovász and Plummer [J. Combin. Theory, Ser. B 23 (1977) 127–138] proved by ear decompositions that every minimal matching covered bipartite graph $G$ different from $K_2$ has at most $(3|V(G)|-6)/2$ edges, and this bound is sharp for all $|V(G)|\ge4$. In this paper, we prove that every minimal matching covered nonbipartite graph $G$ with at least 6 vertices has at most $5(|V(G)|-2)/2$ edges, and this bound is sharp for all $|V(G)|\ge6$.

We prove that every water transport problem on an $n$-vertex graph has an optimal strategy of length at most $n^{(2+o(1))n}$. More strongly, the convex hull of all strategy operators stabilizes within the same bound. We also give a five-vertex instance in which every optimal strategy repeats a nontrivial connected averaging set.

Let $k\ge3$ and $1\le \ell\le k-1$. We study balanced $k$-partitions of a graph for which the union of any $\ell$ parts induces few edges. We show that every graph $G$ with $n$ vertices and $m$ edges admits a balanced partition $V_1,\ldots,V_k$ such that \begin{equation*} \max_{\substack{A\in\binom{[k]}{\ell}}}e_G\left(\bigcup_{i\in A}V_i\right)\le\frac{\ell^2}{k^2}m+\frac{\ell^2(k-\ell)}{k^2}(n-1)+\frac{\ell(k-\ell)}{k(k-1)}\sqrt{\left(\binom{k}{\ell}-1\right)m}. \end{equation*} In the case $\ell=2$, our result confirms a conjecture of Bollobás and Scott in a stronger form.

Odd Cycle Transversal is a classic $\mathsf{NP}$-hard graph optimization problem asking for a minimum-weight set of vertices whose deletion makes the input graph bipartite, or equivalently, a maximum-weight induced bipartite subgraph. We show that Odd Cycle Transversal is quasi-polynomial-time solvable on $kP_4$-free graphs, for every fixed $k \in \mathbb{N}$. In fact, we provide an $n^{O_k(\log n)}$-time algorithm for the more general \textsc{Max-Weight List $2$-Colorable Induced Subgraph}, where the notation $O_{k}(\cdot)$ hides factors depending on $k$. Paired with known results from the literature, this allows us to obtain a complete complexity dichotomy for these two problems on $H$-free graphs into cases solvable in quasi-polynomial time and cases which are $\mathsf{NP}$-hard, in particular resolving an open problem of Agrawal, Lima, Lokshtanov, Saurabh, and Sharma [SODA 2024]. Our algorithms are based on a new structural tool that may be of independent interest. We introduce the notion of $H$-amiable family and show that, for every fixed graph $H$ without isolated vertices and every fixed $k\ge2$, every $kH$-free graph admits an $H$-amiable family of quasi-polynomial size that can be constructed in quasi-polynomial time. Besides yielding the aforementioned algorithms, this result gives, for every fixed connected graph $H$ and every fixed $k\ge2$, a reduction from Max-Weight Independent Set on $kH$-free graphs to the same problem on $H$-free graphs with $n^{O_{H,k}(\log n)}$ overhead. In this setting, it improves the $n^{O_{H,k}(\log^3 n)}$ overhead obtained by specializing the general reduction of Gartland and Lokshtanov [FOCS 2020].

Let $\mathbb{P}(x\prec y)$ be the probability that $x$ precedes $y$ in a uniformly random linear extension of an $n$-element poset $P$, and define the balancing coefficient to be $\delta(x,y)=\min(\mathbb{P}(x\prec y),\mathbb{P}(y\prec x))$ with $\delta(P)=\max_{x,y}\delta(x,y)$. We prove (Theorem 1) that sufficiently large width forces $\delta(P)$ to be arbitrarily close to $1/2$, answering a long-standing conjecture of Kahn and Saks. In fact, we prove the stronger result (Theorem 2) that large width forces one of two configurations in our poset: either a nearly uniform order on $k$ vertices, or an almost fixed order on $t$ vertices with one further vertex inserted uniformly among the $t+1$ slots. We also show that, for fixed $k$, the first possibility must occur within any antichain $X$ of size $\Omega(n^{2/3})$.

We combine two coloring aspects that work in opposite directions. One can 2-color the vertices of a cubic graph such that each monochromatic component is very small. One can also 2-color the vertices of a cubic graph such that each monochromatic component has degree at least 1. As an intended tool for solving a special case of Wegner's conjecture, Thomassen formulated a conjecture that combined the two previous properties. This led to the concept of a crumby coloring. However it turned out that there are cubic graphs without such coloring. Here we try to see what natural relaxations of the original concept might hold for each cubic graph. We show there exists a constant $c$ such that every cubic graph has a vertex 2-coloring such that every monochromatic component has at least 2 and at most $c$ vertices. We also prove an unbalanced version, which is the natural relaxation of the crumby coloring.

The balance constant is a poset parameter measuring how well random linear extensions can be split according to their relative order on two elements. We give an $\varepsilon$-improvement for the balance constant over the bound by Brightwell, Felsner and Trotter (1995), for some small $\varepsilon>0$. This is the first general result towards the $\frac{1}{3}$–$\frac{2}{3}$ conjecture in over 30 years.

Every finite nonempty incomplete uniquely decipherable code with maximum word length $k$ has an uncompletable word of length at most $4k^2-3k$. The bound is independent of the number of codewords and their total length. Deleting a complete codeword cycle gives a finite path-counting identity; Kraft equality then supplies a short word of deficient compressed mass. Cyclic averaging and padding turn it into an uncompletable word. Conditional expectation makes the construction polynomial-time and also decides completeness. First-return words extend the bound to mortal families of nonnegative integer $n\times n$ matrices with joint spectral radius at most one, provided every strongly connected component has a vertex meeting every cycle. Such a family has a zero product of length at most $4n^2-3n$. A binary partial deterministic family with $2k-1$ states has shortest zero product of length $k^2+k-1$, establishing the optimal quadratic order. The bounds and the explicit-code algorithm, including its polynomial work bound, are proved in Lean.

We give explicit algorithms that factor elements of the standard diagram monoids into their usual generators. These algorithms generalize sorting from permutations to partial matchings and set partitions. In every case the worst-case complexity is $n^2$, which is optimal for algorithms that explicitly list the factors. We also determine the average complexity of our algorithms.

For $a$ in $\mathbb{R}$, a subset $V$ contained in $\mathbb{R}^{n}$ is said to be $a$-convex if $x, y \in V \Longrightarrow a x + (1-a) y \in V$. According to Pinch [Math. Proc. Cambridge Philos. Soc., 1985], the $a$-convex hull of $V$ is the intersection of all of the $a$-convex subsets of $\mathbb{R}^{n}$ that contain $V$, and Pinch also defines $D(a)$ as the $a$-convex hull of $\{ 0, 1 \}$ in $\mathbb{R}^{1}$. Pinch conjectured that if $a$ is a totally real algebraic integer and $D(a)$ has no limit points, then every algebraic conjugate of $a$ other than $a$ is in $(0, 1)$. We succeed in proving this conjecture, which seems to have remained open.

We proved a log-star comparison between the expectation threshold $q(\mathcal F)$ and the fractional expectation threshold $q_f(\mathcal F)$ for any nontrivial increasing family $\mathcal F$ on a finite ground set $V$ of size $|V|=N$. Specifically, we show that $$q_f(\mathcal F)\le64\log_2^*(N+2)\,q(\mathcal F),$$ where $\log_2^* x$ is the iterated logarithm of base-2. Using similiar methods, one can extend this result to the following stronger form: there exists a universal constant $C>0$ such that \[ q_f(\mathcal F)\le Cq(\mathcal F)\log_2^*(l(\mathcal F)),\quad q_f(\mathcal F)\le Cq(\mathcal F)\log_2^*(\operatorname{VC}(\min\mathcal F)), \] where $l(\mathcal F):=\max\{2,\max_{S\in\min\mathcal F}|S|\}$ and $\operatorname{VC}(\min\mathcal F)$ denotes the VC-dimension of $\min\mathcal F$. On October 7, 2026, OpenAI released a result proving the equivalence of fractional and integral thresholds, which supersedes the findings in this note. The authors are keeping this note for historical reference.