Combinatorics
See recent articles
Showing new listings for Friday, 17 April 2026
- [1] arXiv:2604.14195 [pdf, html, other]
-
Title: $RD_α$-Spectra of Joined Union Graphs with Applications to Power Graphs of Finite GroupsComments: 19 pagesSubjects: Combinatorics (math.CO); Spectral Theory (math.SP)
The \emph{generalized reciprocal distance matrix} of a graph $\mathscr{G}$, denoted by $RD_\alpha(\mathscr{G})$, is defined as $RD_\alpha(\mathscr{G})=\alpha\,RT_r(\mathscr{G})+(1-\alpha)\,RD(\mathscr{G}), \, \alpha\in[0,1],$ where $RT_r(\mathscr{G})$ represents the diagonal matrix of reciprocal vertex transmissions, and $RD(\mathscr{G})$ is the Harary (reciprocal distance) matrix of $\mathscr{G}$. In this paper, we investigate the $RD_\alpha$-spectrum of graphs obtained through the joined union operation. We derive explicit formulas for the characteristic polynomial of $RD_\alpha(\mathscr{G})$ when $\mathscr{G}$ is formed as a joined union of regular graphs. These results provide closed-form expressions for the corresponding spectra of several important graph classes. Moreover, we show that the power graphs of the dihedral group $D_{2n}$ and the generalized quaternion group $Q_{4n}$ admit representations as joined union graphs. Using this structural characterization, we determine the $RD_\alpha$-spectra of power graphs arising from various classes of finite groups, including cyclic groups $\mathbb{Z}_n$, dihedral groups $D_{2n}$, generalized quaternion groups $Q_{4n}$, elementary abelian $p$-groups, and certain non-abelian groups of order $pq$.
- [2] arXiv:2604.14255 [pdf, other]
-
Title: Enumerative Combinatorics of Homogeneous Linear OrderingsComments: 16 PagesSubjects: Combinatorics (math.CO)
We count the number of countable homogeneous colored linear orderings in $k$ colors. Relatedly, we count the number of countable $C_{n,m}$-homogeneous linear orderings. $C_{n,m}$-homogeneity is a strong homogeneity notion that approximates $sp-$homogeneity, a notion recently uncovered in [2] to have important computability theoretic properties. Explicit formulas are derived for both of the quantities in question, along with asymptotic bounds. The objects being counted are generally infinite, and it is not obvious that there are even only finitely many. This fact, along with the more precise counting, is demonstrated by corresponding the linear orderings with finite objects.
- [3] arXiv:2604.14383 [pdf, html, other]
-
Title: The Geometry of Rectangular MultisetsComments: 15 pages, 10 figuresSubjects: Combinatorics (math.CO); Group Theory (math.GR); Geometric Topology (math.GT)
This article describes a natural piecewise Euclidean bi-simplicial cell structure for the space of $n$-element multisets in a fixed Euclidean rectangle. In particular, we highlight some connections with spaces of complex polynomials and permutahedra.
- [4] arXiv:2604.14391 [pdf, html, other]
-
Title: Log-Concavity and Infinite Log-Concavity of Linear Recurrent Sequences with Linear Coefficients via Companion Matrix MethodsComments: 15 pagesSubjects: Combinatorics (math.CO); Number Theory (math.NT)
We study log-concavity properties of real sequences $(a_n)_{n \ge 0}$ satisfying a $d$-th order linear recurrence whose coefficients are linear functions of $n$; the so-called P-recursive (or holonomic) sequences. Writing the recurrence in companion-matrix form $\mathbf{v}_{n+1} = M_n\,\mathbf{v}_n$ with $M_n = nA + B$, we show that the log-concave operator value $\mathcal{L}(a_n) = b_n \coloneqq a_n^2 - a_{n+1}a_{n-1}$ is a quadratic form in the state vector $\mathbf{v}_n$, and identify the matrix $Q_n = Q^{(0)} + nQ^{(1)}$ whose positive semi-definiteness gives a sufficient condition for log-concavity. For the class of second-order recurrences with constant coefficients, we prove a tight (necessary and sufficient) criterion for the sequence to be $\infty$-log-concave, a consequence of the fact that $\mathcal{L}(a_n)$ is itself a geometric sequence so that $\mathcal{L}^2(a_n) = 0$ identically. We obtain analogous tight criteria for sequences fixed by $\mathcal{L}$, and for P-recursive sequences satisfying a dominant-root asymptotic behaviour. We leave some further insight in case this criteria break down in full generality.
- [5] arXiv:2604.14405 [pdf, html, other]
-
Title: Infinite graphs with finite metric dimensionSubjects: Combinatorics (math.CO)
We study the metric dimension (strong and weak) of infinite graphs. In particular, our main interest is characterizing infinite graphs with finite dimension. Our main results: (1) graphs with more than one end have infinite strong dimension; (2) for graphs with a finite number of cycles, the weak dimension is finite if and only if the graph has finitely many vertices of degree three, and the strong dimension is finite if and only if the graph has one end and finitely many vertices of degree three.
- [6] arXiv:2604.14416 [pdf, html, other]
-
Title: Transfer Operators and Independence Polynomials for Strong Powers of Circulant GraphsComments: Initial version, please contact with any commentsSubjects: Combinatorics (math.CO); Information Theory (cs.IT)
We study independent sets in strong powers of circulant graphs using a transfer matrix formulation. The compatibility constraints separate into intra-layer and inter-layer components, yielding a transfer operator that is equivariant under the dihedral group action. The characteristic polynomial of the transfer operator factors into an \emph{anomalous} component (arising from the trivial isotypic component, with rational coefficients) and a \emph{cyclotomic} component (arising from nontrivial Fourier modes, splitting over the maximal real cyclotomic subfield). We show that the spectral radius is attained in the trivial isotypic component, so the dominant exponential growth is governed by a low-dimensional orbit-compressed operator. The independence polynomial is computed exactly for strong cylinders and tori, with the cyclotomic sector contributing a sparse correction confined to high-weight coefficients. All results are verified for $C_7$.
- [7] arXiv:2604.14458 [pdf, html, other]
-
Title: Noncrossing Partitions From Hull ConfigurationsComments: 14 pages, 9 figuresSubjects: Combinatorics (math.CO)
Each finite configuration of points in the plane determines a corresponding lattice of noncrossing partitions. When these points form the vertex set of a convex polygon, the associated lattice is the classical noncrossing partition lattice (introduced by Kreweras in 1972), which makes many appearances in combinatorics and geometric group theory. If, on the other hand, all points of the configuration lie on a common line segment, the result is a Boolean lattice. In this article, we examine the more general class of hull configurations, which we define to be those which lie either on a line segment or on the boundary of a convex polygon. We prove that the corresponding lattices of noncrossing partitions are unions of maximal Boolean subposets and, under certain circumstances, have symmetric chain decompositions.
- [8] arXiv:2604.14462 [pdf, html, other]
-
Title: Noncrossing Partitions From Cones and SemicirclesMichael Dougherty, Kaiyi Fang, Yunting Jiang, Edgar Lin, Lucas Lindenmuth, Eleanor Pokras, Gina RootComments: 17 pages, 5 figures. Final versionJournal-ref: Discrete Mathematics (2026) 349-2Subjects: Combinatorics (math.CO)
For each finite configuration of distinct points in the plane, there is an associated lattice of noncrossing partitions. When these points form the vertices of a convex polygon, the result is the classical noncrossing partition lattice, which is enumerated by the Catalan numbers and satisfies many other useful properties. In this article, we examine three variations of this lattice which arise when the starting configuration is allowed to have points on the sides of a convex polygon rather than just the vertex set.
- [9] arXiv:2604.14628 [pdf, html, other]
-
Title: Orbits and incidence matrices for points, planes and lines regarding the twisted cubic in PG(3,q), q = 2, 3, 4Comments: 30 pagesSubjects: Combinatorics (math.CO)
In the three-dimensional projective space PG(3,q) over the finite field F_q with q elements, we consider the normal rational curve known as a twisted cubic and the projectivity group G_q that fixes it. For q = 2, 3, 4, we solve the open problems of classifying the orbits of points, planes, and lines under G_q and of determining the corresponding incidence matrices between points, planes, and lines partitioned into these orbits.
- [10] arXiv:2604.14639 [pdf, html, other]
-
Title: Unimodality and log-concavity of generalized Glasby-Paseman sequencesComments: 15 pages, 2 tables, comments welcome!Subjects: Combinatorics (math.CO)
In this paper, we consider a two-parameter ($l$ and $a$) generalization of a sequence that Glasby and Paseman considered. Based on computer experiments, we conjecture its unimodality, log-concavity, peak positions, and the asymptotic behavior of the maximum values. Then we prove this conjecture for the case where $l=2$ and $a=1$. We finish the paper by making some comments about the conjecture on the generalized sequence.
- [11] arXiv:2604.14670 [pdf, html, other]
-
Title: New results on proper orientation number of graphsSubjects: Combinatorics (math.CO)
A proper orientation $D$ of an undirected graph $G$ is an orientation of $G$ such that $d_D^+(u)\not=d_D^+(v)$ for any edge $uv\in E(G)$. Denote the proper orientation number $\vec{\chi}(G)$ of an undirected graph $G$ as the minimum $\Delta^+(D)$ among all proper orientations $D$ of $G$. Chen, Mohar and Wu (JCTB, 2023) proved that if $G$ is a $r$-partite graph, then $\vec{\chi}(G) \leq \frac{1}{2} \text{Mad}(G)+O(\frac{r\log{r}}{\log{\log{r}}})$, where $\text{Mad}(G)$ is the maximum average degree of $G$. Moreover, if $G$ is a bipartite graph, then $ \vec{\chi}(G) \leq \lceil \frac{1}{2} \text{Mad}(G)\rceil +3$, and this bound is tight. They also asked whether $\vec{\chi}(G)-\lceil \frac{1}{2} \text{Mad}(G)\rceil$ can be bounded by a linear function of $r$. In this paper, we prove that $ \vec{\chi}(G) \leq\lceil \frac{1}{2} \text{Mad}(G)\rceil +7$ for every 3-partite graph $G$. As a corollary, we also improve Chen, Mohar and Wu's bounds for the 3-colorable planar graphs and the outerplanar graphs. Our proof use the notion of potential out-degree and weighted matching lemma with special weighted functions. We also construct a class of $r$-partite graphs with $\vec{\chi}(G)\geq\lceil \frac{1}{2} \text{Mad}(G)\rceil +r+1$ to be the possible extremal graphs.
- [12] arXiv:2604.14671 [pdf, html, other]
-
Title: On the independence number of de Bruijn graphsComments: 33 pagesSubjects: Combinatorics (math.CO); Information Theory (cs.IT)
We derive the asymptotic formula $\alpha(k,q)=\lambda_{k-1}q^k+o(q^k)$, where $\alpha(k,q)$ is the independence number of the de Bruijn graph $B(k,q)$, and $\lambda_{k-1}$ is a constant arising from a variational problem on the unit $(k-1)$-dimensional cube. When $k=4$, we show the bounds $91/240\le \lambda_3\le 11/28$. For odd prime $k$, we analyse the binary case $q=2$ via a phase reduction on rotation orbits. For $k=11$ and $k=13$ this yields certified optimal constructions, which combined with a lifting theorem by Lichiardopol give exact formulas for $\alpha(11,q)$ and $\alpha(13,q)$ for all $q\ge2$, extending the known cases $k=3,5,7$.
- [13] arXiv:2604.14673 [pdf, html, other]
-
Title: Unbalanced signed bipartite graphs containing no negative $C_4$ with maximum spectral radiusSubjects: Combinatorics (math.CO)
A signed graph $(G,\sigma)$ is a graph $G$ together with an assignment $\sigma$ of either a positive sign or a negative sign to each edge. A signed graph is unbalanced if it contains a cycle with odd number of negative edges. The spectral radius of a signed graph is the spectral radius of its adjacency matrix, in which for vertices $u,v$, the $(u,v)$-entry is $0$, $-1$, or $1$ depending on whether $uv$ represents no edge, a negative edge, or a positive edge, respectively. Recently, Conde, Dratman and Grippo [Discrete Math. 349 (2026) 114942] proved that there is only one unbalanced signed bipartite graph with maximum spectral radius, up to switching isomorphism. In this paper, we establish a spectral Turán type results for signed bipartite graphs. More precisely, we determine the unique graphs containing no negative cycles of length four with maximum spectral radius, up to switching isomorphism, among unbalanced signed bipartite graphs with fixed bipartite sizes and order, respectively.
- [14] arXiv:2604.14686 [pdf, html, other]
-
Title: Locally Equienergetic GraphsComments: This paper is published in MATCH Communications in Mathematical and in Computer Chemistry JournalJournal-ref: MATCH Commun Math Comput Chem 93 (2025) 759-766Subjects: Combinatorics (math.CO); Spectral Theory (math.SP)
For a given graph \( G \), let \( G^{(j)} \) denote the graph obtained by the deletion of vertex \( v_j \) from \( G \). The difference \( \mathscr{E}(G) - \mathscr{E}(G^{(j)}) \) quantifies the change in the energy of \( G \) upon the removal of \( v_j \), termed as the local energy of \( G \) at vertex $v_j$, as defined by Espinal and Rada in 2024. The local energy of $G$ at vertex $v$ is denoted by \(\mathscr{E}_G(v)\). The local energy of the graph \( G \), therefore, is the summation of these vertex-specific local energies across all vertices in \( V(G) \), expressed by \( e(G) = \sum \mathscr{E}_G(v) \). Two graphs of the same order are defined as locally equienergetic if they have identical local energy. In this paper, we have investigated several pairs of locally equienergetic graphs.
- [15] arXiv:2604.14763 [pdf, html, other]
-
Title: Tight spectral conditions for the Hamiltonicity of $K_{1,r}$-free split graphsSubjects: Combinatorics (math.CO)
The Hamiltonicity and related subjects of split graphs, and in particular $K_{1,r}$-free split graphs with $r\ge 3$ received much attention. Dai et al. [Discrete Math. 345 (2022) 112826] conjectured that every $(r-1)$-connected $K_{1,r}$-free split graph is Hamiltonian. They proved the case when $r=4$, and earlier Renjith and Sadagopan [Int. J. Found. Comput. Sci. 33 (2022) 1--32] proved the case when $r=3$. Recently, Liu, Song, Zhang and Lai [Discrete Math. 346 (2023) 113402] proved that a split graph is Hamiltonian if and only if it is fully cycle extendable. So for $r=3,4$ every $(r-1)$-connected $K_{1,r}$-free split graph is fully cycle extendable. We give tight spectral sufficient conditions for a $K_{1,r}$-free split graph to be Hamiltonian for $r=3,4$.
- [16] arXiv:2604.14978 [pdf, html, other]
-
Title: Counting tight Hamilton cycles in Dirac hypergraphsComments: 23 pages + 9 pages appendix for general l-cyclesSubjects: Combinatorics (math.CO)
Suppose $G$ is a $k$-uniform hypergraph on $n$ vertices such that every $(k-1)$-subset $S$ of $V(G)$ belongs to at least $\delta n$ edges, where $\delta> 1/2$. Let $\Psi(G)$ denote the number of tight Hamilton cycles in $G$, that is, cyclic orderings of $V(G)$ in which every $k$ consecutive vertices form an edge. We prove that $\log\Psi(G)\ge kh(G)-n\log{n\choose k-1}+n\log n-n\log e-o(n)$, where $h(G)$ is the hypergraph entropy of $G$, defined via perfect fractional matchings. This bound is tight, for example, for all (nearly) regular hypergraphs, in particular for the binomial random hypergraph. It also implies a conjecture by Ferber, Hardiman and Mond, stating that $\Psi(G)\ge (\delta-o(1))^n n!$.
- [17] arXiv:2604.15005 [pdf, html, other]
-
Title: Gorenstein Simplices and Even Binary Self-Complementary CodesComments: 19 pagesSubjects: Combinatorics (math.CO)
It is known that if a Gorenstein simplex of dimension \(d\) and degree \(s\) is not a lattice pyramid, then \(d \leq 2s-1\). In this paper, we study the extremal case \(d=2s-1\). More precisely, we characterize Gorenstein simplices of dimension \(2s-1\) and degree \(s\) which are not lattice pyramids in terms of even binary self-complementary codes. As an application, combining this characterization with existing classification results on reflexive simplices, we classify Gorenstein simplices of degree \(3\) and \(4\).
- [18] arXiv:2604.15031 [pdf, html, other]
-
Title: A Hypergraph Container Method on Spread SAT: Approximation and SpeedupComments: 24 pages, 2 figuresSubjects: Combinatorics (math.CO); Computational Complexity (cs.CC)
We develop a hypergraph container method for the Boolean Satisfiability Problem (SAT) via the newly developed container results [Campos and Samotij (2024)]. This provides an explicit connection between the extent of spread of clauses and the efficiency of container-based algorithms. Informally, the more evenly the clauses are distributed, the stronger the shrinking effect of the containers, which leads to faster algorithms for SAT.
To quantify the extent of spread, we use a weighted point of view, in which a clause of size $s$ receives weight $p^s$ for some $0<p\le 1$.In this way, we introduce the notion of $(\lambda,p)_k$-structure for SAT formulas, where $\lambda$ is the spread parameter and $k$ is the maximum size of clauses. By the almost-independence property of containers, we prove that for formulas with $(\lambda,p)_k$-structures, one can distinguish between ``unsatisfiable formulas'' and ``formulas satisfying at least a $(1-\delta)$-fraction of clauses'' in sub-exponential time. This shows that sufficiently spread formulas are not worst-case instances for Gap-ETH. Moreover, we show that the speedup is directly controlled by the spread parameter $\lambda$, yielding faster exact algorithms for SAT formulas containing a $(\lambda,p)_k$-structure. This result extends previous work [Zamir (STOC 2023)] to the non-uniform case. - [19] arXiv:2604.15138 [pdf, other]
-
Title: The 1-2-3 conjecture for polygonal tilingsComments: 32 pagesSubjects: Combinatorics (math.CO)
The 1-2-3 conjecture has been solved positively in 2024 for finite graphs and by extension for infinite graphs which are locally finite. The solution is non-constructive, and finding explicit solutions for large (or infinite) graphs is very hard. By exploiting the extra structure present in many non-periodic tilings, we find explicit solutions for the Chair (all three vertex placements), Non-Pinwheel, Pinwheel, Half-hex, Ammann-Beenker (two versions), Penrose Rhomb, and the Domino tilings. We prove that for any fully periodic tiling of the plane there exists a fully periodic solution, and provide an algorithm for finding such a solution. We give solutions for the fully periodic square, triangle and hexagonal lattices.
- [20] arXiv:2604.15172 [pdf, html, other]
-
Title: Evaluations of some series via the WZ methodComments: 21Subjects: Combinatorics (math.CO); Number Theory (math.NT)
In this paper, we evaluate some series via the WZ method, and confirm several previous conjectures. For example, we prove the following two identities conjectured by the second author: $$\sum_{k=0}^{\infty} \frac{(28k^2 + 10k + 1) \binom{2k}{k}^5}{(6k + 1)(-64)^k \binom{3k}{k} \binom{6k}{3k}} = \frac{3}{\pi}$$ and $$\sum_{k=1}^\infty \frac{d^4}{dk^4}\left(\frac{(21k-8)\Gamma(k+1)^2}{k^3\Gamma(2k+1)}\right)=\frac{1959}2\zeta(6)-432\zeta(3)^2. $$
- [21] arXiv:2604.15205 [pdf, html, other]
-
Title: On the m-point convexityComments: 12 pages, 4 figuresSubjects: Combinatorics (math.CO)
Let $S\subset \mathbb{R}^d$ $(d\geq 2)$. A set $S$ is said to be $m$-point convex, if for every $m$ distinct points in $S$, at least one of the line-segments determined by them lies in $S$. We also say that $S$ has property $P_m$. Let ${x,y,z}\in \mathbb{R}^{d}$. If $\mathrm{conv}\{x,y,z\}$ is a right triangle, then $\{x,y,z\}$ is called a {\it right triple}. A set $S$ is said to have the right-$3$-point property,if, for every right triple of $S$, at least one of the line-segments determined by them belongs to $S$. In particular, it has the double right-$3$-point property, if, for every right triple in $S$, at least two of the line-segments determined by them belong to $S$. In this paper, we further investigate $m$-point convex sets and establish the relationship between the sets with the double right-$3$-point property and convex sets in $\mathbb{R}^d$.
- [22] arXiv:2604.15253 [pdf, html, other]
-
Title: A matroidal twist on a formula of BrionComments: 24 pages, 7 figures, comments welcomeSubjects: Combinatorics (math.CO)
Brion's Formula realizes the Laurent polynomial of lattice points in a lattice polytope P as the sum of rational functions associated to the vertices of P. In this paper, we consider the special case where P is a generalized permutohedron. We introduce a modification of the rational functions associated to the vertices of P depending on a given matroid M. Upon summing these rational functions, we show that the resulting Laurent polynomial Q_M(P) behaves in certain ways like the lattice points of P, exhibiting natural recursive and reciprocity behaviors. Furthermore, upon evaluating Q_M(P) at 1, we recover the matroid Euler characteristic of Larson, Li, Payne, and Proudfoot, thereby providing a refined approach to studying these quantities.
- [23] arXiv:2604.15305 [pdf, html, other]
-
Title: Erdős's diameter conjecture for separated distances fails in high dimensionsComments: 6 pagesSubjects: Combinatorics (math.CO); Metric Geometry (math.MG)
Erdős asked whether every $n$-point set in Euclidean space whose $\binom{n}{2}$ pairwise distances are mutually at least $1$ apart must have diameter at least $(1+o(1))n^2$. We disprove this statement by constructing for every prime power $q$ a set $\mathcal X_q\subset \mathbb R^{q^2+q}$ of $n=q+1$ points such that all pairwise distances in $\mathcal X_q$ are mutually at least $1$ apart, while $$\operatorname{diam}(\mathcal X_q)\le\Bigl(1-\frac{1}{\pi^2}+o(1)\Bigr)n^2.$$ The proof is fully formalized in Lean 4.
New submissions (showing 23 of 23 entries)
- [24] arXiv:2604.14211 (cross-list from math.DG) [pdf, html, other]
-
Title: Ollivier-Ricci Curvature of Riemannian Manifolds and Directed Graphs with Applications to Graph Neural NetworksSubjects: Differential Geometry (math.DG); Artificial Intelligence (cs.AI); Social and Information Networks (cs.SI); Combinatorics (math.CO)
This thesis is an exposition of Ollivier-Ricci Curvature of metric spaces as introduced by Yann Ollivier, which is based upon the 1-Wasserstein Distance and optimal transport theory. We present some of the major results and proofs that connect Ollivier-Ricci curvature with classical Ricci curvature of Riemannian manifolds, including extensions of various theoretical bounds and theorems such as Bonnet-Myers and Levy-Gromov. Then we shift to results introduced by Lin-Lu-Yau on an extension of Ollivier-Ricci curvature on graphs, as well as the work of Jost-Liu on proving various combinatorial bounds for graph Ollivier-Ricci curvature. At the end of this thesis we present novel ideas and proofs regarding extensions of these results to directed graphs, and finally applications of graph-based Ollivier-Ricci curvature to various algorithms in network science and graph machine learning.
- [25] arXiv:2604.14381 (cross-list from quant-ph) [pdf, html, other]
-
Title: Learning Cut Distributions with Quantum OptimizationComments: 29 pages, 6 figures, 2 tablesSubjects: Quantum Physics (quant-ph); Combinatorics (math.CO)
Many combinatorial optimization problems admit a maximin fairness variant, where the aim is to find a distribution over possible solutions which maximizes an expected worst-case outcome. However, the support for an optimal distribution may be exponential, which can be intractable to represent in the worst case. To this end, we propose a quantum based approach to solving distribution optimization problems. Expanding on work analyzing the Dynamical Lie Algebras of the Quantum Approximate Optimization Algorithm (QAOA), we show that with a finite number of layers, a QAOA ansatz can be constructed to capture any distribution over bitstrings. We show that the resulting circuit is able to effectively solve the Fair Cut Cover, a fair interpretation of the classical Fractional Cut Cover Problem. In addition, we show that our algorithm is provably better than classical approximations on certain graph structures and empirically outperforms these classical algorithms on tested instances.
- [26] arXiv:2604.14542 (cross-list from math-ph) [pdf, html, other]
-
Title: The $n$-Point Function of $t$-Core Partitions and Topological VertexComments: 35 pagesSubjects: Mathematical Physics (math-ph); Combinatorics (math.CO); Quantum Algebra (math.QA); Representation Theory (math.RT)
In this paper, we study the $n$-point function of $t$-core partitions. The main tool is the topological vertex, originally developed to study the topological string theory for toric Calabi--Yau 3-folds. By virtue of the topological vertex, we introduce the $q$-deformed $n$-point function that generalizes both the ordinary $n$-point function of all integer partitions studied by Bloch--Okounkov and $t$-core partition case treated here. As a consequence, we provide a closed formula for the $n$-point function of $t$-core partitions in terms of theta functions, and prove that the corresponding correlation functions are quasimodular forms.
- [27] arXiv:2604.14979 (cross-list from math.FA) [pdf, html, other]
-
Title: Graphs at infinity: Liouville theorems, Recurrence and Characterization of Dirichlet formsSubjects: Functional Analysis (math.FA); Combinatorics (math.CO); Metric Geometry (math.MG)
We survey recent results on graphs and their Laplacians related to the behavior of the graph at large. In particular, we focus on Liouville theorems, recurrence and characterizations of Dirichlet forms via boundary terms.
- [28] arXiv:2604.15007 (cross-list from math.PR) [pdf, html, other]
-
Title: A counter-example to persistence in generalised preferential attachment treesSubjects: Probability (math.PR); Combinatorics (math.CO)
Consider a generalised preferential attachment tree with attachment function $f$, that is a random tree, where at each time-step a node connects to an existing node $v$ with probability proportional to $f(\mathrm{deg}(v))$, where $\mathrm{deg}(v)$ denotes the degree of the node in the existing tree. We provide a counter-example to a conjecture of the author asserting that under the assumption $\sum_{j=1}^{\infty} \frac{1}{f(j)^2} < \infty$ there is a persistent hub in the model, that is, a single node that has the maximal degree for all but finitely many time-steps. The counter-example is a minor modification of a related counter-example due to Galganov and Ilienko.
- [29] arXiv:2604.15123 (cross-list from math.SP) [pdf, html, other]
-
Title: Spectral Effects Of Heavy-Tailed Vertex Noise In Geometric GraphsSubjects: Spectral Theory (math.SP); Combinatorics (math.CO)
We characterize which local matrix structures saturate Weyl's eigenvalue perturbation bound for graph Laplacians under geometrically constrained vertex displacements. Geometric graphs with heavy-tailed vertex noise arise across sensor networks, biological imaging, and spatial omics, yet tractable predictions for noise-induced spectral error remain limited. We study geometric graphs abstracted from biophysical systems, incorporating clearance, planarity, and identifiability constraints that govern physically realizable embeddings. Within this constrained setting, we identify witness motifs, small subgraphs in maximally noise-sensitive geometric configurations, that dominate weighted-degree and graph Laplacian spectral perturbations under tempered power-law vertex displacements. This motif decomposition reduces global spectral sensitivity to a finite catalog of local extremal structures and identifies configurations that attain Weyl-tight bounds. We then lift these constrained-graph results to general straight-line embedded graphs in arbitrary dimension via local repair operations producing a constrained surrogate graph that preserves sensitivity-relevant structure. To quantify noise-induced spectral variation in both strong-oracle and weak-oracle regimes, we introduce stochastic co-spectrality (SC) and the stochastic spectral separation index (S3I), which characterize when observed spectral distances are noise-driven and when noise parameters are separable. Together, these results provide a principled pathway from local geometric noise to global spectral error in graph Laplacian matrices, enabling estimation of spectral fragility from graph structure without exhaustive eigenvalue computation or restrictive distributional assumptions beyond moment bounds.
Cross submissions (showing 6 of 6 entries)
- [30] arXiv:2502.06520 (replaced) [pdf, other]
-
Title: Cancellation of a critical pair in discrete Morse theory and its effect on (co)boundary operatorsComments: 20 pages, 7 figures, 1 appendix, 1 tableSubjects: Combinatorics (math.CO); Algebraic Topology (math.AT); Rings and Algebras (math.RA)
Discrete Morse theory helps us compute the homology groups of simplicial complexes in an efficient manner. A "good" gradient vector field reduces the number of critical simplices, simplifying the homology calculations by reducing them to the computation of homology groups of a simpler chain complex. This homology computation hinges on an efficient enumeration of gradient trajectories. The technique of cancelling pairs of critical simplices reduces the number of critical simplices, though it also perturbs the gradient trajectories. In this article, in a purely combinatorial manner, we derive an explicit formula for computing the modified boundary operators after cancelling a critical pair, in terms of the original boundary operators. The same formula can be obtained through a sequence of elementary row operations on the original boundary operators. Thus, it eliminates the need of enumeration of the new gradient trajectories. We also obtain a similar result for coboundary operators.
- [31] arXiv:2506.12933 (replaced) [pdf, html, other]
-
Title: Locating-dominating partitions for some classes of graphsJournal-ref: Discrete Mathematics 349 (2026) 114886Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
A dominating set of a graph $G$ is a set $D \subseteq V(G)$ such that every vertex in $V(G) \setminus D$ is adjacent to at least one vertex in $D$. A set $L\subseteq V(G)$ is a locating set of $G$ if every vertex in $V(G) \setminus L$ has pairwise distinct open neighborhoods in $L$. A set $D\subseteq V(G)$ is a locating-dominating set of $G$ if $D$ is a dominating set and a locating set of $G$. The location-domination number of $G$, denoted by $\gamma_{LD}(G)$, is the minimum cardinality among all locating-dominating sets of $G$. A well-known conjecture in the study of locating-dominating sets is that if $G$ is an isolate-free and twin-free graph of order $n$, then $\gamma_{LD}(G)\le \frac{n}{2}$. Recently, Bousquet et al. [Discrete Math. 348 (2025), 114297] proved that if $G$ is an isolate-free and twin-free graph of order $n$, then $\gamma_{LD}(G)\le \lceil\frac{5n}{8}\rceil$ and posed the question whether the vertex set of such a graph can be partitioned into two locating sets. We answer this question affirmatively for twin-free distance-hereditary graphs, maximal outerplanar graphs, split graphs, and co-bipartite graphs. In fact, we prove a stronger result that for any graph $G$ without isolated vertices and twin vertices, if $G$ is a distance-hereditary graph or a maximal outerplanar graph or a split graph or a co-bipartite graph, then the vertex set of $G$ can be partitioned into two locating-dominating sets. Consequently, this also confirms the original conjecture for these graph classes.
- [32] arXiv:2506.18782 (replaced) [pdf, html, other]
-
Title: Triangle-free subsets of the $r$-distance graph of the HypercubeComments: 10 pagesSubjects: Combinatorics (math.CO)
Given the $r$-distance graph on the hypercube $\mathbb{F}_2^n$, where two vertices are adjacent if their Hamming distance is exactly $r$, we study the maximum size $T(n,r)$ of a triangle-free set of vertices. For even $r\le n/2$, we prove \[T(n,r)=O\!\left(\frac{r2^n}{n+1}\right).\] We also obtain lower bounds in various regimes of $r$ as a function of $n$.
- [33] arXiv:2506.23054 (replaced) [pdf, html, other]
-
Title: Edge-colouring and orientations: applications to degree- and $χ$-boundednessSubjects: Combinatorics (math.CO)
We prove a new generalisation of Ramsey's theorem by showing that every $2$-edge-coloured graph with sufficiently large minimum degree contains a monochromatic induced subgraph whose minimum degree remains large. From this, we also derive that every orientation of a graph with large minimum degree contains either a large transitive tournament or an induced antidirected digraph whose minimum degree is still large.
As a consequence, we obtain two general tools showing that certain extensions of degree-bounded graph classes preserve degree-boundedness. A hereditary class $\mathcal{G}$ is {\it degree-bounded} if, for every integer $s$, there exists $d=d(s)$ such that every graph $G\in \mathcal{G}$ either contains $K_{s,s}$ or has minimum degree at most $d$. With these tools, we obtain for instance that odd-signable graphs and Burling graphs are degree-bounded. We also characterise exactly the oriented graphs $F$ such that the graphs admitting an orientation without any induced copy of $F$ are degree-bounded. - [34] arXiv:2510.19242 (replaced) [pdf, html, other]
-
Title: Congruences modulo powers of $3$ for generalized Frobenius partitions $CΨ_{6,0}$Comments: 8 pagesSubjects: Combinatorics (math.CO); Number Theory (math.NT)
In 1984, Andrews introduced the family of partition functions \(c\phi_k(n)\), which counts the number of generalized Frobenius partitions of \(n\) with \(k\) colors. In previous work, we proved a conjecture on congruences for \(c\phi_6(n)\) modulo powers of 3. In this paper, we consider the \((6,0)\)-colored Frobenius partition functions \(c\psi_{6,0}(n)\). We establish a connection between the generating functions of \(c\psi_{6,3}(n)\) and \(c\psi_{6,0}(n)\) via an Atkin-Lehner involution, and prove congruences modulo powers of 3 for \(c\psi_{6,0}(n)\).
- [35] arXiv:2511.16656 (replaced) [pdf, html, other]
-
Title: The multicolour size Ramsey number of a pathComments: 11+3 pages. Exposition streamlinedSubjects: Combinatorics (math.CO)
In this paper, we determine the $r$-colour size Ramsey number of the path $P_k$, up to constants. In particular, for every fixed $r \geq 2$ and $k \geq 100\log r$, we have
\[ \widehat{R}_r(P_k)=\Theta((r^2 \log r) \, k).\] Perhaps surprisingly, we do this by improving the lower bound on $\widehat{R}_r(P_k)$. - [36] arXiv:2604.10779 (replaced) [pdf, html, other]
-
Title: Polynomial Time Enumeration of t-Stack-Sortable Permutations Ending in Their Least EntryComments: 15 pages, 1 figureSubjects: Combinatorics (math.CO)
We study the behavior of West's stack-sorting map $s$ on permutations whose last entry is also their least. Let $S_{n}':=\{\pi0\mid \pi\in S_n\}$ where $\pi0$ denotes the concatenation of $\pi$ and $0$. For each permutation $\pi\in S_n'$, we introduce a new combinatorial object known as the stack-sorting tableau $T_{\pi}$, which ultimately serves as the key ingredient in the first polynomial time algorithm for counting the number of $t$-stack-sortable permutations in $S_n'$. We then establish a precise relationship between the behavior of $s$ on $S_{n}'$ and on $S_{n}$.
- [37] arXiv:2212.09528 (replaced) [pdf, other]
-
Title: Polarizations of Artin monomial idealsComments: Minor improvements, 51 pagesSubjects: Commutative Algebra (math.AC); Combinatorics (math.CO)
We show that any polarization of an Artin monomial ideal defines a triangulated ball. This proves a conjecture of this http URL, this http URL and the first author.
Geometrically, polarizations of ideals containing $(x_1^{a_1}, \ldots, x_n^{a_n})$ define full-dimensional triangulated balls on the sphere which is the join of boundaries of simplices of dimensions $a_1-1, \cdots, a_n-1$. We prove that every full-dimensional Cohen-Macaulay sub-complex of this joined sphere is of this kind, and these balls are constructible.
Such a triangulated ball has a dual cell complex which is a sub-complex of the product of simplices of dimensions $a_1-1, \cdots a_n-1$. We prove that this cell complex gives cellular minimal free resolution of this of the Alexander dual ideal of the triangulated ball. When the product of simplices is a hypercube, using these dual cell complexes we classify in a range examples all polarizations of the Artin monomial ideal.
We also show that the squeezed balls of this http URL \cite{Ka} derive from polarizations of Artin monomial ideals. - [38] arXiv:2511.22736 (replaced) [pdf, html, other]
-
Title: Bounds on the sequence length sufficient to reconstruct binary level-$1$ phylogenetic networks under the CFN modelSubjects: Populations and Evolution (q-bio.PE); Combinatorics (math.CO)
Phylogenetic trees and networks are graphs used to model evolutionary relationships, with trees representing strictly branching histories and networks allowing for events in which lineages merge, called reticulation events. While the question of data sufficiency has been studied extensively in the context of trees, it remains largely unexplored for networks. In this work we take a first step in this direction by establishing bounds on the amount of genomic data required to reconstruct binary level-$1$ semi-directed phylogenetic networks, which are binary networks in which reticulation events are indicated by directed edges, all other edges are undirected, and cycles are vertex-disjoint. For this class, methods have been developed recently that are statistically consistent. Roughly speaking, such methods are guaranteed to reconstruct the correct network assuming infinitely long genomic sequences. Here we consider the question whether networks from this class can be uniquely and correctly reconstructed from finite sequences. Specifically, we present an inference algorithm that takes as input genetic sequence data, and demonstrate that the sequence length sufficient to reconstruct the correct network with high probability, under the CFN model of evolution, scales logarithmically, polynomially, or polylogarithmically with the number of taxa, depending on the parameter regime. As part of our contribution, we also present novel inference rules for quartet data in the semi-directed phylogenetic network setting.
- [39] arXiv:2602.14957 (replaced) [pdf, other]
-
Title: Tropical cluster varieties, phylogenetic trees, and generalized associahedraComments: FPSAC 2026 extended abstractSubjects: Algebraic Geometry (math.AG); Combinatorics (math.CO)
We explicitly describe the tropicalization of a type C cluster variety by identifying it with the space of axially symmetric phylogenetic trees. We also study the signed tropicalizations of this cluster variety, realizing them as subfans of the tropicalization that are dual to either associahedra or cyclohedra.
- [40] arXiv:2603.18550 (replaced) [pdf, html, other]
-
Title: Borsuk-Ulam type theorem for Stiefel manifolds and orthogonal mass partitionsComments: 19 pagesSubjects: Algebraic Topology (math.AT); Combinatorics (math.CO); Metric Geometry (math.MG)
A generalization of the Borsuk-Ulam theorem to Stiefel manifolds is considered. This theorem is applied to derive bounds on $d$ that guarantee-for a given set of $m$ measures in $\mathbb{R}^d$-the existence of $k$ mutually orthogonal hyperplanes, any $n$ of which partition each of the measures into $2^n$ equal parts. If $n=k$, the result corresponds to the bound obtained in [11], but with the stronger conclusion that the hyperplanes are mutually orthogonal.