Papers

The ARE (Action, Rectification, and Structure) method is presented as a framework for reorganizing the Leibniz expansion of the determinant through the action of the cyclic group C_n on S_n. This action partitions the permutations into orbital classes and naturally leads to a finite Fourier decomposition of the determinant structure. The central object of the work is the vector determinant, whose components are Fourier modes associated with orbital sums of Leibniz terms. The classical determinant appears exactly as the fundamental mode G_0(A)=det(A), while the remaining modes are multilinear spectral observables associated with the orbital organization of the expansion. The manuscript establishes the fundamental properties of this formalism, including exact determinant recovery through a linear readout functional, multilinearity, Hermitian symmetry for real matrices, vector Jacobi and Laplace formulas, orbital Parseval identities, a vector Hadamard inequality, and finite trigonometric interpolation. The framework extends naturally to continuous frequencies through an associated orbital polynomial. It does not reduce the factorial complexity of determinant computation, but reveals an orbital-Fourier structure not visible in the classical scalar determinant. The work also clarifies the relation between orbital modes and circulant structures, proving that the crude orbital modes cannot generally coincide with circulant eigenvalues because of polynomial-degree incompatibility.

We study the second law in the context of combinatorial processes, focusing on the mechanisms that give rise to irreversible behavior from an underlying deterministic, invertible, and reversible dynamics.

A $P_4$ is a chordless path on four vertices. A diamond is a graph obtained from a clique of size four by removing one edge of the clique. A paw is a graph obtained from a clique of size four by removing two adjacent edges of the clique. We prove that for a graph $H$, the class of graphs with no induced subdivision of $H$ has bounded clique-width if and only if $H$ is an induced subgraph of $P_4$, the paw, or the diamond. This answers a~question of Dabrowski, Johnson, and Paulusma.

We study decreasing binary trees in which every vertex with two children is colored red or blue. We construct two bijections. The first, to ordered set partitions into odd-sized blocks each arranged as an alternating permutation, shows that the exponential generating function of these trees is $1/(1-\tan z)$. The second, to nonplane decreasing 1-2 trees paired with a binary label on each non-root vertex, proves combinatorially that the count equals $2^{n-1}$ times the~$n$th Euler number. Refining by the number of right edges yields the Boolean–Eulerian polynomials, which are an explicit algebraic transform of the classical Eulerian polynomials. The Foata–Strehl orbit decomposition, recast in the decreasing-binary-tree model, gives a direct combinatorial proof of gamma-positivity, and the algebraic transform carries real-rootedness and interlacing of zeros from the Eulerian polynomials to the Boolean–Eulerian polynomials.

We study tropical rational functions on the tropical projective line with three zeros and three poles in the torus, counted with multiplicity, modulo target automorphisms. The principal divisor identifies their moduli space with unordered pairs of disjoint effective divisors of degree three. We classify its \(53\) cells and prove that it is six-dimensional with ten contractible connected components. Source–target automorphism groups are trivial or of order two, and reflection loci are defined by linear gap equations. Allowing common support and points at infinity gives a divisor-pair compactification. Over an algebraically closed non-Archimedean field with value group \(\mathbb{R}\), root–pole tropicalization is surjective from valuation-separated cubic rational functions modulo the target torus normalizer. Explicit counterexamples show that the valuation of the conjugacy invariant \(J^2/I^3\) does not descend to this tropical moduli space. Generic functions admit minimal six-unit shallow ReLU representations with three positive and three negative unit output weights.

This document is an extended abstract for two articles in preparation. Recently, framing lattices were introduced to generalize many classical lattices such as the Tamari lattice and the weak order on the symmetric group. We define bricks and brick cliques as a combinatorial model for join-irreducible elements and canonical join representations in all framing lattices, generalizing noncrossing arc diagrams of (Reading, 2015) for the weak order on the symmetric group. Our model captures the natural bijection between join and meet canonical representations, as well as duality upon reflections of the framed graph. The proof is bijective, with an explicit reconstruction algorithm in two steps. A useful intermediate construction in our bijective proof is our new definition of cornered cliques. These enable us to define cubical coordinates on a framing lattice, generalizing bracket vectors for the Tamari lattice and providing an efficient comparison criterion.

We show that for $m, r \in \mathbb{N}$ and $N > (2m+1)^r (r!)^{1/m}$, every $r$-coloring of the integers in the interval $[N]$ contains a monochromatic solution to the equation \[ x_1 + \dots + \dots x_{m+1} = y_1 + \dots + y_m. \] This generalizes and improves recent results of Koścuiszko. We also show that if $N \geq 2^{r}$, then every $r$-coloring of the integers in $[N]$ must always determine a monochromatic solution to the above equation for some $m \geq 1$. The latter estimate is optimal.

The theory of log concave polynomials has recently been developed to study objects and problems in combinatorics and other subfields in mathematics. Particular classes of log concave polynomials called Lorentzian polynomials and denormalized and dually Lorentzian polynomials have been used to prove log concavity statements for various combinatorial sequences. This includes the strongest form of Mason's log concavity conjecture on the independent sets of matroids and the log concavity of sequences of Kostka numbers. In this paper, we develop an analogous class of power series called denormalized Lorentzian (DL) Laurent series. This class is the natural generalization of DL polynomials to homogeneous power series with the benefit of capturing a number of combinatorial generating series including the Kostant partition function for integer flows of directed graphs. We then analyze specific DL Laurent series to obtain new bounds for integral flows on general directed acyclic graphs and new bounds for the dimensions of weight spaces of parabolic $\mathfrak{sl}_{n+1}(\mathbb{C})$ Verma modules.

For each integer $n \geq 3$, the wheel graph $W_n$ is defined as the graph obtained by connecting a single vertex to all vertices of a cycle of length $n$. In particular, $W_6$ can be uniquely obtained from the Petersen graph by contracting three edges incident to a common vertex. Gubser provided a characterization of all 3-connected planar $W_6$-minor-free graphs. In this paper, we complete the characterization of $W_6$-minor-free graphs by determining the 3-connected nonplanar cases.

For $k\ge 3$, the $(k-2)$-uniform Turán density $\pi_{k-2}(F)$ of a $k$-graph $F$ is the supremum of $d$ for which there are arbitrarily large $F$-free $k$-graphs that are uniformly $d$-dense with respect to the $k$-vertex cliques of every $(k-2)$-graph on the same vertex set. We develop a palette framework for this density. For every family $\mathcal F$ of $k$-graphs, we prove that $\pi_{k-2}(\mathcal F)$ equals the corresponding palette Turán density. We further establish palette classification tools for the existence of $k$-graphs satisfying prescribed palette colorability constraints. Those together allow us to reduce exact density computations to a palette-homomorphism framework without relying on the hypergraph regularity method. As applications, for all $k\ge 3$ and $r\ge 2$, we establish the following values \[ \frac{r-1}{r},\quad \frac{(r-1)^2}{r^2},\quad \frac{r-1}{2r},\quad \frac{(k-1)^k}{k^k},\quad \frac{4(k-2)^{k-2}}{k^k},\quad \frac{4(k-2)^{k-2}}{3k^k} \] as $(k-2)$-uniform Turán densities of single $k$-graphs. Finally, for every $k\ge3$, we show that there exist $k$-graphs $F_1,F_2$ such that \[ \pi_{k-2}(\{F_1,F_2\})< \min\{\pi_{k-2}(F_1),\pi_{k-2}(F_2)\}, \] which provides the first examples of non-principal families for this density.

In graph bootstrap percolation, edges of an Erdős-Rényi random graph ${\mathcal G}_{n,p}$ are initially active, and activation spreads to other edges of $K_n$ via the combinatorics of a fixed graph $H$: an edge becomes active whenever it is the unique inactive edge in a copy of $H$. The process $H$-percolates if all edges of $K_n$ are eventually activated. While classical cases such as $H=K_3$ (connectivity) and $H=K_4$ (related to $2$-neighbor bootstrap percolation) have been studied extensively, general graphs $H$ can exhibit wildly different behaviors. In this work, we determine the critical $H$-percolation threshold $p_c(n,H)$ for every graph $H$, fully resolving a longstanding open question of Balogh, Bollobás, and Morris. The location of $p_c(n,H)$ is governed by a new, universal parameter $\rho(H)$, which measures the maximal efficiency of witness graphs that activate an edge. To achieve this, we introduce a novel framework based on the unfolding and refolding of witness graphs. While previous works were restricted to specific families of $H$, our approach provides a unified strategy for all $H$. Inspired by algebraic topology, we lift witness graphs to covering graphs and algorithmically embed folded versions into ${\mathcal G}_{n,p}$ via a sequence of extensions. Crucially, this allows us to incorporate highly efficient witness graphs of unbounded size, which are potentially far larger than ${\mathcal G}_{n,p}$ itself. Beyond resolving $p_c(n,H)$, our framework recovers and strengthens several existing bounds in the literature. Finally, we initiate the study of the universal density parameter $\rho(H)$ and pose central open questions regarding its computability and its exact correspondence with the sharpness of the $H$-percolation threshold.

We study the distribution of the order of a random permutation of $[n]$ through the lens of Rényi entropy. In particular, we obtain an asymptotic for the Rényi $q$-entropy of the order in the full range $1 \leq q \leq \infty$. For $q > 1$, our results are quantitatively optimal and reveal a tight connection between the asymptotic behaviour of the Rényi $q$-entropy and arithmetic properties of $n$. Of particular interest are the cases $q = \infty$ and $q = 2$, which correspond to the maximum probability of achieving a particular order and the probability that two independent random permutations have equal orders, respectively. In the former case, we show that the probability in question is asymptotic to $1/n$ and additionally characterise the maximiser for sufficiently large $n$. In the latter case, we determine a minimal and maximal order for the probability as a function of $n$, of respective forms $c/n^2$ and $\log^*n/n^2$. Our results provide an essentially complete answer to a set of questions raised by Acan, Burnette, Eberhard, Schmutz and Thomas, some of which go back to work of Erdős and Turán from the 1960s.

We derive a graded character formula for the action of any finite group on the Artinian reduction of the Stanley–Reisner ring of any complete simplicial fan, which is given by an equivariant version of the classical h-polynomial. This gives the graded character formula for the representation of the group on the cohomology of the associated toric variety when the fan is rational. As an application, we use a navel tool, which we called hybrid fan, to compute the Poincaré polynomial of the invariants of the Artinian reduction of the Stanley–Reisner ring of any complete simplicial fan under a finite reflection group action. This implies that the Poincaré polynomial of the quotient of a compact toric orbifold by any finite reflection group is equal to the Poincaré polynomial of the compact toric orbifold associated to the hybrid fan.

We say that a $d$-regular graph is a $\gamma$-expander if for every not too large set of vertices $S$, there are at least $\gamma d |S|$ edges leaving $S$, and we say that a graph $G$ is $\gamma$-far from bipartite if at least $\gamma e(G)$ edges need to be removed to make it bipartite. We prove that there exists an absolute constant $K$ such that any $n$-vertex $d$-regular $\gamma$-expander with $d \ge (\gamma^{-1} \log n)^K$ is Hamiltonian, provided that it is bipartite or $\gamma$-far from bipartite. As applications, we obtain highly robust versions of recent important results on the Hamiltonicity of Cayley graphs and Kneser graphs. As part of our proof, we prove a random connecting lemma for sublinear expanders which might be of independent interest.

For each integer $n\geq 3$, let $W_n$ denote the wheel graph obtained by connecting a single vertex to all vertices of a cycle of length $n$. In particular, $W_6$ is obtained from the Petersen graph by contracting three edges incident with a common vertex. In this paper, we determine all $4$-connected graphs that do not contain $W_6$ as a minor.

In this note, we establish the periodicity of chains of affine standard Lyndon words in all types and determine tight bounds on that periodicity, greatly generalizing the $A$-type results of arXiv:2305.16299. Our approach crucially utilizes the convexity and monotonicity of arXiv:2505.15432 together with the new idea to consider the polarization of the root system given by increasing and decreasing chains.

For a graph $G$ and $e\in [0,1]$, denote by $I_G(e)$ the supremum of induced density of $G$ over $n$-vertex graphs with edge density $e$ as $n$ goes to infinity. Liu, Mubayi and Reiher asked if there exists a graph $G$, where $I_G(e)$ has a non-trivial local maximum. In this paper, we answer this problem affirmatively. We first show that $I_{K_{2,2,1}}(e)$ has at least two local maxima in $(0,1)$. Part of this proof is using flag algebras. Additionally, we determine $I_{K_{2,2,1}}(e)$, when $e=(k-1)/k$ for every integer $k\ge 3.$ We also prove that $I_{K_t^-}(e)$ has a non-global local maximum for every $t\in\{5,8,11,\ldots,$ $74\}$. The proof combines a symmetrization theorem of Schelp and Thomason with Reiher's clique density theorem.

A connected undirected graph $G = (V,E)$ is lower conformally rigid if uniform edge weights maximize the second smallest Laplacian eigenvalue $\lambda_2(w)$ over all normalized edge weights $w$, and upper conformally rigid if uniform edge weights minimize the largest eigenvalue $\lambda_n(w)$ over all normalized edge weights; $G$ is conformally rigid if it is lower or upper conformally rigid. This paper establishes a new framework for conformal rigidity through the language of subdifferentials, unifying the variational perspective on eigenvalue optimization with the geometry of edge-isometric spectral embeddings, which are known to characterize conformal rigidity. This subdifferential framework lends itself naturally to techniques of symmetry reduction that motivate the notion of an orbit-isometric embedding - a weaker condition than edge-isometry that accounts for the symmetries of $G$ while remaining sufficient for conformal rigidity. The notion opens the door to tools from representation theory: for a large class of graphs, including all vertex-transitive ones, we show that conformal rigidity is certified by a single eigenvector, resolving an open question and explaining the conformal rigidity of previously unexplained graphs. This extra structure enables a new, algebraically exact certification method for conformal rigidity, bypassing the numerical difficulties of prior approaches. In many cases, the problem reduces to a check of linear feasibility, and in general, to solving a system of quadratic equations via Gröbner bases.

We prove that the maximum eigenvalue of the (both signed and unsigned) Laplacian of level $k$ Kikuchi graph of any graph $G$ with $m$ edges is at most $m+k$. This confirms four recent conjectures of Apte, Parekh, and Sud. As applications, we obtain that tensor products of one and two qubit product states achieve an approximation ratio of $5/8$ for Quantum Max Cut and $5/7$ for the XY Hamiltonian. Moreover, combining our bounds with the algorithms analyzed by Apte, Parekh, and Sud, yields efficient algorithms achieving an approximation ratio of $0.614$ for Quantum Max Cut and $0.674$ for the XY Hamiltonian. Finally, we also make modest progress on Brouwer's conjecture and improve Lew's bound on the sum of the top-$k$ eigenvalues of a Graph Laplacian.

Let $w$ be a finite word of length $n$. In this paper, we study the maximum possible number of distinct rational power factors in a finite word. A rational power is a word of the form $u=p^kp'$, where $p$ is a nonempty finite word, $k$ is an integer larger than $1$, $p^k$ is a concatenation of $k$ copies of $p$ and $p'$ is a prefix of $p$. The rational powers can be recognized as a generalization of $k$-powers, and it is proved in [Li,Pachocki,Radoszewski 24] that, the number $C_k(w)$ of distinct $k$-powers in $w$ satisfies $C_k(w) \leq \frac{n-1}{k-1}$. However, the number of rational powers has not been studied in the literature. In this article, we prove that the number $\mathrm{RP}(w)$ of distinct rational power factors of $w$ satisfies $\mathrm{RP}(w)\le\frac18n^2+O(n)$. We also illustrate a novel approach to study pattern-counting problems: using a graph-theoretic representation of words and a few word equations, we transform the traditional pattern-counting problems into a constrained extremal problem.

For an integer $q\ge 2$ and a graph $F$ with $q\mid e(F)$, let $R(F,\Z_q)$ be the least integer $n$ such that every edge-labeling $w\colon E(K_n)\to \Z_q$ contains a copy of $F$ whose edge-label sum is zero in $\Z_q$. Write $C_{qk}$ for the cycle on $qk$ vertices. We prove that $R(C_{qk},\Z_q)\le \max\{R(C_{2q},\Z_q),qk+q-1\}$ via an insertion argument rooted in the classic Erdős-Ginzburg-Ziv theorem. Combined with Pikhurko's result, we obtain $R(C_{qk},\Z_q)\le \max\{35q^2,qk+q-1\}$ for every $q\ge 3$. We also show that $R(C_{qk},\Z_q)\ge qk+q-1$ for odd $q\ge 3$. Hence, for every fixed odd $q\ge 3$ and every $k\ge 35q$, we obtain the exact value $R(C_{qk},\Z_q)=qk+q-1$. For even $q\ge 4$, the same method gives $qk+\frac q2-1\le R(C_{qk},\Z_q)\le \max\{35q^2,qk+q-1\}$, leaving an additive gap of order $q/2$ when $k$ is large. Moreover, for the case $q=3$, we prove that \(R(C_{3k}, \mathbb{Z}_3) = 3k + 2\) for all \(k \ge 2\). Extending our techniques beyond cycles, we also resolve the zero-sum Ramsey number for wheel graphs \(W_m = C_m + K_1\), proving that \(R(W_{3k}, \mathbb{Z}_3) = 3k + 1\) for all \(k \ge 2\).

We answer a question of Simental by providing a combinatorial interpretation of a formula which generalizes rational Catalan numbers and which appears in the study of Springer fibers. We provide an interpretation in terms of binary necklaces as well as anchored Dyck paths.

Circulant graphs are a widely studied family of graphs whose members possess varying amounts of symmetry. Although considerable progress has been made in finding the automorphism groups of circulant graphs under certain restrictions, a complete classification is elusive. In general, the structure of the automorphism group of a graph with twins can be simplified by separating the effect of automorphisms that permute mutually twin vertices and those that operate on the twin quotient graph. Further simplification can be achieved in twin-free, vertex-transitive graphs that have co-twins, which we define to be vertices whose neighborhoods are complementary. In this paper, we demonstrate how the these simplifications can be used provide insight into the automorphism groups and symmetry parameters of vertex-transitive graphs in general and circulant graphs in particular.

The Graph Minors Series of Robertson and Seymour forms the foundation of algorithmic structural graph theory, yielding fixed-parameter algorithms for problems such as Disjoint Paths, Rooted Minor Checking, and Folio. A key ingredient behind the fixed-parameter tractability of the $k$-Disjoint Paths problem is the irrelevant-vertex technique. This machinery is governed by the Vital Linkage Theorem and the so-called Linkage Function $\ell$. However, despite its foundational role, the best known bounds on the Linkage Function are enormous and are only implicitly understood. The quantitative bounds behind these results have traditionally been so large that the resulting algorithms are regarded as "galactic". Our main result is a general irrelevant-vertex theorem for a common generalisation of $k$-Disjoint Paths and Rooted Minor Checking for graphs of size at most $d,$ commonly called the $(k,d)$-Folio problem. Specifically, we show that for any graph $G$ in which the $k$ terminals are chosen from some set $R,$ if the treewidth of $G$ exceeds $\beta(k,b,d)\in$ $2^{{\bf poly}(b + d)}$ $\cdot {\bf poly}(k)$ then we can locate an irrelevant vertex for the $(k,d)$-Folio problem. Here, the quantity $b$ is the bidimensionality of $R,$ that is, the largest $b$ for which a $(b\times b)$-grid minor in $G$ can be rooted on $R$. Thus, the exponential component of the irrelevant-vertex threshold is driven by the bound on the bidimensionality, rather than by the number of terminals, and we argue that this dependence is essentially optimal up to polynomial factors. As a consequence, the Linkage Function satisfies $\ell(k) \in 2^{{\bf poly}(k)}$. Beyond its structural significance, our result yields improved parameter dependencies for algorithms for Disjoint Paths and Rooted Minor Checking}, and provides a quantitative improvement for a broad range of graph-minor-based algorithmic frameworks.

In this paper, we investigate generalized bent functions (GBFs) from $\mathbb{Z}_3^n$ to $\mathbb{Z}_m$. We show that GBFs exist whenever $3$ divides $m$, while several nonexistence results are obtained when $3\nmid m$. In particular, we prove that no GBFs exist for $n=1,2$ when $m$ is odd and not divisible by $3$. For the case $n=3$, we establish the nonexistence of GBFs $f:\mathbb{Z}_3^3 \rightarrow \mathbb{Z}_{5\cdot11^r}$ for all nonnegative integers $r$. Finally, we show that no GBF exists from $\mathbb{Z}_3$ to $\mathbb{Z}_{2m'}$ and $\mathbb{Z}_3^2$ to $\mathbb{Z}_{2m'}$, where $m'$ is odd and not divisible by $3$.

The largest matching root of a $k$-graph is the largest real root of its matching polynomial, which is equal to the maximum modulus of all the zeros of the matching polynomial. In this paper, we investigate the perturbation of the largest matching root of $k$-graphs. We determine all $k$-graphs whose largest matching root attains the maximum among all $k$-cacti and linear $k$-cacti with a given number of cycles and edges, where a $k$-cactus is a $k$-graph in which every two distinct cycles have at most one vertex in common. To achieve this, we prove that the celebrated shifting operation of $k$-graphs, introduced by Erdős, Ko and Rado, does not decrease the largest matching root. This result extends a classical result by Csikvári (Electron. J. Combin. 18 (2011) $\#$P182) stating that the Kelmans transformation does not decrease the largest matching root of graphs.

A cycle system of order $n$ is a decomposition of the edges of the complete graph $K_n$ into cycles of a fixed length. A cycle system is said to be $k$-colourable if we can assign $k$ colours to its vertices so that no cycle is monochromatic. A $k$-colourable cycle system is uniquely $k$-colourable if its colouring is unique up to the permutation of colour classes. In this paper, we construct uniquely $2$-colourable $4$-cycle systems of order $n$ for all admissible $n\geq 49$, and also uniquely $2$-colourable $4$-cycle decompositions of $K_n - I$, for all admissible $n \geq 50$. These constructions contribute to the broader study of uniquely colourable cycle systems and open new directions for future research.

For an $r$-uniform hypergraph $G$, let $\lambda^{(p)}(G)$ denote its $p$-spectral radius, defined as the maximum of the polyform of $G$ over the unit sphere in the $\ell_p$-norm. Let $Q_k^r(n)$ be the complete $k$-chromatic $r$-graph on $n$ vertices with color classes as equal as possible. Kang–Nikiforov–Yuan conjectured that, for every $p\ge1$ and $n>(r-1)k$, the $r$-graph $Q_k^r(n)$ is the unique maximizer of $\lambda^{(p)}$ among all $k$-chromatic $r$-graphs of order $n$. They also conjectured the corresponding explicit bound \[ \lambda^{(p)}(G) \le r!\left(\tbinom nr-k\tbinom{n/k}{r}\right)n^{-r/p}, \] with equality only in the divisible extremal case. The case $r=3$ was established in their work. This paper resolves the remaining cases $r\ge4$, and hence settles both conjectures for all $r\ge3$. As a consequence, the same threshold gives an anti-Wilf-type spectral certificate: any $r$-graph of order $n$ whose $p$-spectral radius exceeds the displayed bound has chromatic number at least $k+1$.

The Burning Number Problem (BNP) models the spread of information or contagion in a network through a discrete-time process on a graph. At each step, one new vertex is selected as a burning source, while fire simultaneously spreads from previously burned vertices to their neighbors. The burning number of a graph is the minimum number of steps required to burn all vertices. The decision version asks whether the burning number is at most a given integer $k$. BNP is known to be NP-complete even on restricted graph classes such as path forests. We study BNP on connected regular graphs, a natural and previously unexplored graph class. We prove that BNP is NP-complete on connected cubic graphs, and moreover APX-hard under this restriction. We further show that BNP remains APX-hard on connected $d$-regular graphs for every fixed $d \geq 4$.

We prove equidistribution of two pairs of statistics on boxed plane partitions: (volume, trace) and (corner-hook volume, number of corners). The proof relies on different 3d visualizations of the corresponding non-intersecting path systems. In particular, we obtain a new visual proof for a volume generating function of plane partitions. We also introduce a new statistic called the cohook area on ordinary partitions, and prove that it is equidistributed with the area of partitions.