Papers

Graphs with a simple spectrum admit cubic-time isomorphism testing, yet we prove that for every natural number $k$, the $k$-Weisfeiler-Leman ($k$-WL) test cannot distinguish all non-isomorphic graphs with a simple spectrum. As the WL hierarchy upper-bounds the distinguishing power of widely-used Graph Neural Networks (GNNs), this incompleteness applies to all such GNNs, ruling out completeness for every $k$-WL-aligned GNN family. To close this gap, we introduce PRiSM (Partition, Refine, Solve, Match), the first provably complete canonicalization of simple-spectrum eigendecompositions. PRiSM obtains the completeness guarantee that prior canonicalizations provably lack, and resolves the open problem of achieving complete expressivity on simple-spectrum graphs. When composed with DeepSets or a Transformer, PRiSM achieves universal approximation on simple-spectrum graphs, justifying the use of canonicalized Laplacian positional encodings. Empirically, PRiSM performs comparably to or outperforms existing spectral canonicalizations on graph regression, classification, and expressivity

Building on an earlier result of the author together with Elsholtz, Führer, Füredi, Pach, Simon and Velich, we present an improved construction for a line-free set in $\mathbb{F}_p^3$, showing that $r_p(\mathbb{F}_p^3)\ge (p-1)^3+\frac18 p^{3/2} - O(p)$ as $p\to \infty$. This results in the first superlinear-term improvement over the standard hypercube construction $\{0,1,\ldots,p-2\}^3$. Via complementation, a line-free set in $\mathbb{F}_p^3$ corresponds to a $2$-blocking set in the affine geometry $AG(3,p)$, hence we also obtain an upper bound of $3p^2-\frac18p^{3/2}+O(p)$ on the smallest size of such a $2$-blocking set.

We study cosmological polytopes induced by Erdős–Rényi random graphs in a high-dimensional regime. These graph-based lattice polytopes form a natural model of random lattice polytopes in which geometric features are determined by the structure of the underlying random graph. Focusing on the number of polytope edges and on the number of edges in unimodular triangulations, we derive asymptotic formulas for expectations and variances and prove quantitative central limit theorems in the relevant parameter regime. The analysis relies on explicit graph-theoretic descriptions of the corresponding edge sets and on the discrete Malliavin–Stein method for normal approximation.

An influential theorem of Nikiforov states that if an $N$-vertex graph $G$ contains at least $\gamma N^h$ copies of some fixed $h$-vertex graph $H$, then $G$ contains an $H$-blowup of order $c_H(\gamma)\log N$. We provide a new proof of this theorem, which in particular improves the best known bound on the constant $c_H(\gamma)$. In contrast to previous proofs, our proof is iterative, finding the blowup one vertex at a time.

Let $M$ be a matroid on a finite ground set $E$, and suppose that the automorphism group of $M$ acts transitively on $E$. We show the following: if $X_1,\ldots,X_K$ are sampled independently from a distribution $p$ on $E$, then the probability that the samples are distinct and that $\{X_1,\ldots,X_K\}$ is an independent set in $M$ is quasi-concave in $p$ and maximized when $p$ is uniform. As a corollary, for a random $K\times N$ matrix over a finite field whose rows are sampled independently from an arbitrary distribution on nonzero projective row classes, the uniform distribution on projective space maximizes the probability of full row rank. In this particular case we also establish the uniqueness of the maximizer and global quadratic stability, while a simple example illustrates that uniqueness and stability need not hold for arbitrary transitive matroids.

The aim of this paper is to develop a $(q,m)$-polymatroidal approach to higher supports and higher rank-weight enumerators of rank-metric codes. In this framework, we establish analogs of several fundamental results known for matroids and linear codes, including the description of minimal supports in terms of cocircuits of truncations and a Greene-type identity relating higher rank-weight enumerators to rank generating functions. We also show that the associated $(q,m)$-polymatroid and the higher support distributions determine each other. As a further application, we derive MacWilliams-type identities for higher rank-weight enumerators.

For a connected graph \(G\), let $q(G)$ denote the $Q$-index of $G$, i.e., the largest eigenvalue of its signless Laplacian matrix. Abreu and Nikiforov (2013) showed that \[ q(G) \leq 2n\left(1-\frac{1}{\omega(G)}\right), \] where $\omega(G)$ denotes the clique number of $G$. We first give a short algebraic proof of this result. For a vertex $v\in V(G)$, let \(c(v)\) denote the order of the largest clique of \(G\) containing \(v\). Our main result is the following vertex localized bound that refines the result of Abreu and Nikiforov: \[ q(G) \leq 2\sum_{v\in V(G)}\left(1-\frac{1}{c(v)}\right). \] Equality holds precisely for complete bipartite graphs when \(\omega(G)=2\), and for regular complete \(\omega(G)\)-partite graphs when \(\omega(G)\geq 3\). As a consequence, we also obtain an analogous localized inequality for the $A_\alpha$-matrix of $G$. Finally, we generalize the above localized inequality to vertex-weighted signed graphs. This contributes to the localization program for spectral Turán-type results.

We study the functional code $C_d(\mathcal{X})$, introduced by G. Lachaud in 1996, in the case where $\mathcal{X}$ is a rank $n$ degenerate Hermitian variety $P\mathcal{U}_{n-1}$ in $\mathbb{P}^n(\mathbb{F}_{q^2})$ and $d\leq q$. We establish an upper bound for the maximum number of $\mathbb{F}_{q^2}$-rational points in the intersection of $P\mathcal{U}_{n-1}$ with an $\mathbb{F}_{q^2}$-hypersurface of degree at most $q$ in $\mathbb{P}^n$. Using this bound, we determine the parameters of the codes $C_d(P\mathcal{U}_{n-1})$ in the cases $n=2,3,4$. We also characterize the hypersurfaces that correspond to the minimum distance of these codes in the cases $n=2,3,4$.

We present three versions of the classic two-pile game one-or-one-or-one-of-both generalized to the multi-pile context. In each case, we explore the resulting $\mathcal{P}$-positions. In the first version, there is a simple pattern. In the other two versions, we find partial solutions in each case through two experimental routes. First by limiting the number of piles, then by limiting the number of tokens per pile.

In this work, we establish a relationship between the sum of irreducible character degrees and the number of twisted involutions associated with the automorphisms of a finite group. We develop algorithmic frameworks for evaluating these quantities in the context of inner automorphisms and the symmetric group $\mathfrak{S}_n$. As an application, we provide a criterion for identifying groups that possess complex (non-real) irreducible representations and explore the structural consequences arising from these results.

A graph-theoretic analogue of Iwasawa theory, initiated by Gonet and Vallières, has attracted considerable interest in the study of Iwasawa invariants. On the other hand, for a pair of prime numbers $(r,\ell)$, one obtains a graph, called the supersingular $\ell$-isogeny graph (SIG), whose adjacency matrix has eigenvalues given by the $\ell$-th Fourier coefficients of the weight 2 Eisenstein series and newforms of level $r$. In this paper, we fix prime numbers $r$ and $p$, and let $\ell$ vary over infinitely many primes. We then investigate the distribution of the Iwasawa $\lambda$-invariants of the constant $\mathbf{Z}_p$-towers over the SIGs, thereby revealing connections among graph theory, Iwasawa theory, elliptic curves, and the Galois representations attached to newforms. At the end of this paper, we propose a conjecture concerning the Galois orbits of newforms.

The Permutation Equivalence Problem (PEP) for linear complementary dual (LCD) codes reduces to Graph Isomorphism (GI) through the orthogonal projector onto the code, but this requires a trivial hull. We ask whether the reduction extends when the standard inner product is replaced by a nondegenerate symmetric bilinear form \(M\). We make precise what it means for \(M\) to yield a valid reduction to GI and prove that, for length \(n \geq 3\) and every field size, this holds if and only if \(M\) is permutation-invariant. The reduction then reaches, beyond LCD codes, a class of codes with one-dimensional hull: exactly those whose hull is spanned by a vector with nonzero coordinate sum. We count these codes exactly; for odd \(q\), asymptotically the method covers a fraction \(\prod_{i \geq 2}(1+q^{-i})^{-1}\) of all codes, \(1 + q^{-1}\) times the fraction of LCD codes. A polynomial-time reduction algorithm is given.

We study the exact enumeration of maximal cliques in graph classes defined by excluded clique minors and excluded clique immersions. For n-vertex K_t-minor-free graphs, we give an algorithm that lists all maximal cliques in n * 4^(2t/5+o(t)) time, significantly improving the previous n * 2^O(t log log t) bound of Eppstein, Löffler, and Strash. For n-vertex K_t-immersion-free graphs, we establish the first exact enumeration algorithm parameterized by immersion number, achieving a running time of n * 3^(t/3+o(t)). While both algorithms employ a common degeneracy-based root-assignment scheme, their analyses require distinct structural mechanisms. Crucially, rather than applying generic sparsity bounds, our algorithms deeply integrate the specific structural obstructions – local density thresholds for minors and minimum-degree branchings for immersions – directly into the enumeration logic. We also prove matching output-size lower bounds, up to sub-exponential factors in t, using specialized constructions. Consequently, the exponential bases 4^(2/5) and 3^(1/3) are asymptotically optimal.

We study matching-removability under the degree/connectivity regime of Halin's theorem, which asserts that every $k$-connected graph $G$ with minimum degree $\delta(G)\ge k+1$ contains an edge $e$ such that $G-e$ remains $k$-connected. For $k,\ell\ge 1$, an $\ell$-matching is a matching of size $\ell$. A matching $M$ in a $k$-connected graph $G$ is {\it $k$-removable} if $G-M$ remains $k$-connected. We improve Halin's result by proving that every $k$-connected graph $G$ with $\delta(G)\ge k+1$ contains a $k$-removable $2$-matching, except when $k=1$ and $G$ is a cycle. For small $k$ we obtain stronger bounds: (i) $k=1$: a 1-removable $\min\{\lfloor n/2\rfloor,\delta(G)\}$-matching; (ii) $k=2$: a 2-removable $\lceil(\delta(G)+1)/2\rceil$-matching, with a unique tight exception when $\delta(G)$ is even and $G\cong K_{\delta(G)+1}$; and (iii) $k=3$: for $\delta(G)\ge 5$, a $3$-removable $\lceil(\delta(G)+1)/2\rceil$-matching. All these bounds are optimal with respect to removable matching size and minimum degree. We also show that for every $n\ge 2\delta$, there exists a $k$-connected $n$-vertex graph $G$ with minimum degree $\delta$ that does not contain a $k$-removable matching of size at least $\delta(G)+1$. Moreover, for $k\le 2$ there exists a $k$-removable $(\delta(G)-c)$-matching for some $c\le 3$, which is optimal up to the additive constant.

Let $p_1,...,p_L\in Z[x_1,...,x_d]$ be non-constant polynomials with zero constant term. The ergodic theoretical proofs of the polynomial and the IP-polynomial Szemeredi theorems as well as some of the ergodic-theoretical and combinatorial consequences of the Density Polynomial Hales-Jewett conjecture (DPHJ) naturally lead to the study of sets of large returns which are defined as $$ R_\epsilon^{p_1,...,p_L}(A):=\{n\in Z^d\,|\,\mu(A\cap T_1^{-p_1( n)}A\cap\cdots\cap T_L^{-p_L(n)}A)>\mu^{L+1}(A)-\epsilon\}, $$ where the $T_j$'s are commuting and invertible $\mu$-preserving transformations, $A$ is measurable, and $\epsilon>0$. We obtain new results dealing with the sets of the form $R_\epsilon^{p_1,...,p_L}(A)$. Among other things, we show that every set of the form $R_\epsilon^{p_1,...,p_L}(A)$ is syndetic if and only if $p_1,...,p_L$ are linearly independent, answering a question asked by Frantzikinakis-Kuca. Moreover, the linear independence of $p_1,...,p_L$ implies that every set of the form $R_\epsilon^{p_1,...,p_L}(A)$ has the A-IP$^*$ property (="almost" IP$^*$ property), which is stronger than syndeticity. The following is one of the new combinatorial results obtained in this paper. Suppose that $p_1,...,p_L$ are linearly independent. For any set $E\subseteq Z^D$ with upper Banach density $d^*(E)>0$, any non-zero $v_1,..., v_L\in Z^D$, and any $\epsilon>0$, the set $$ S_\epsilon^{p_1,...,p_L}(E):=\{ n\in Z^d\,|\,d^*(E\cap (E-p_1(n)v_1)\cap \cdots\cap (E-p_L(n)v_L))>(d^*(E))^{L+1}-\epsilon\} $$ is A-IP$^*$. Furthermore, we prove that when $D>L>1$, this result is sharp: the A-IP$^*$ property cannot be upgraded to IP$^*$. The techniques developed in this paper lead to some additional applications. For example, we show that an amplified form of the IP-polynomial Szemeredi theorem conjectured by Bergelson- McCutcheon follows from the DPHJ.

Steinerberger introduced the Buffon discrepancy problem, asking how accurately a one-dimensional set of length $L$ in a convex body can match the Crofton-predicted line-intersection counts, and proved an $O\left(L^{1/3}\right)$ upper bound via a Steinhaus longimeter construction. Using the Aistleitner–Bilyk–Nikolov arbitrary-measure star-discrepancy theorem we demonstrate the existence of full-chord constructions with discrepancy $O\left((\log L)^{3/2}\right)$ for every fixed compact convex body with finite piecewise $C^2$ boundary. In the disk, we prove that every full-chord construction has discrepancy at least $\Omega\left(\log L\right)$, using Schmidt's two-dimensional rectangle discrepancy lower bound.

We study a concrete family of symmetric integral $Z$-matrices attached to weighted star trees. The arms are ordinary type-$A$ chains and the central diagonal entry is an arbitrary positive integer $k$ rather than being fixed to the Cartan value $2$. This gives a matrix-theoretic and graph-theoretic version of the so called Berger construction: it extends the simply laced affine Dynkin stars while remaining accessible through elementary linear algebra. For a star with arm lengths $r_1,\ldots,r_m$ we compute the determinant, the inertia, the positive-definite and affine regimes, and the primitive positive null vector in the affine case. The affine condition is exactly the unit-fraction equation \[ \sum_{i=1}^m \frac{1}{r_i+1}=m-k, \] so the classification of these affine weighted trees reduces to a finite Egyptian-fraction enumeration for each fixed pair $(m,k)$. The classical affine diagrams $D_4^{(1)}$, $E_6^{(1)}$, $E_7^{(1)}$ and $E_8^{(1)}$ appear as small subfamilies, while higher-arm cases give new integral positive-semidefinite star matrices with explicit Coxeter labels.

We derive explicit formulae for the subalgebra zeta functions of all higher Heisenberg Lie algebras over an arbitrary compact discrete valuation ring $\mathfrak{o}$. To this end, we develop Hecke-theoretic techniques for the enumeration, by two distinct invariants, of sublattices of an $\mathfrak{o}$-lattice of finite rank endowed with a non-degenerate symplectic form.

In the paper, in light of the generating function of the complete Bell polynomials and other techniques, the author presents concise and elegant proofs of three formulas for the complete Bell polynomials.

A function $F:\mathbb{F}_{2}^{n}\to \mathbb{F}_{2}^{m}$ is called $k$th-order sum-free if the sum of its values over any $k$-dimensional affine subspace of $\mathbb{F}_2^n$ is non-zero. Carlet recently introduced this notion and constructed such functions for every $2\le k\le n$. We prove that, for $2\le k\le n-2$ and $m \leq n$, the existence of a (non-degenerate) $\mathbb{F}_{2}^{m}$-valued $k$th-order sum-free function on $\mathbb{F}_{2}^{n}$ is equivalent to the existence of a codimension $m$ linear subcode of the Reed-Muller code $\mathrm{RM}(n-k,n)$ with minimum distance $3\cdot 2^{k-1}$. In particular, this yields a new family of Reed-Muller subcodes that avoid all minimum weight codewords of $\mathrm{RM}(n-k,n)$, and thus have minimum distance $3/2$ times that of $\mathrm{RM}(n-k,n)$. We also derive new necessary conditions for the existence of $k$th-order sum-free functions and present the first nontrivial lower bound on $m$. Finally, we observe that $k$th-order sum-free functions lead to a partition of the Grassmannian of all $k$-dimensional (linear) subspaces of $\mathbb{F}_2^n$ into constant-dimension subspace codes. Under the assumption that functions exist that are $k$th-order sum-free for multiple values of $k$, we obtain an improved partitioning result and a stronger upper bound on the chromatic number of the Grassmann graphs.

For a graph $G$ on $[n]$, the $k$-cut complex $\Delta_k(G)$ has facets $[n]\setminus T$, where $T$ ranges over the $k$-subsets that induce disconnected subgraphs of $G$. Bayer, Denker, Jelić Milutinović, Sundaram, and Xue proved that $\Delta_k(P_n^2)$ is shellable for $n\ge k+3$ and conjectured a finite-difference recurrence for its top reduced Betti number along each diagonal $n-k=r$. We prove the exact formula \[ \beta(k,n)=\binom{n-1}{k-1} -\sum_{j=0}^{\min\{k-1,n-k\}}\binom{k-1}{j}(n-k-j+1)+(n-k) \] for $k\ge2$ and $n\ge k+3$. The proof rests on a complete classification of complements of cardinality at least $k$ that contain no disconnected $k$-subset: every such complement has size $k$ or $k+1$ and is, respectively, a connected $k$-subset of $P_n^2$ or an interval of $k+1$ consecutive vertices. For fixed $r\ge3$, the formula is the restriction of a polynomial in $k$ of degree exactly $r-1$. Hence its $r$th backward difference vanishes identically and its $(r-1)$st backward difference is the constant $r-2$. On the topologically defined sequence, these identities hold for $k\ge r+2$ and $k\ge r+1$, respectively. We also obtain the conjectured closed forms for $k=4,5$, the complete face enumerator, and the associated $h$-polynomial and Stanley–Reisner Hilbert series.

We define the grove polynomials, a set-valued extension of forest polynomials. We show that they are $K$-theoretically dual to the quasisymmetric Schubert cells which pave the quasisymmetric flag variety, in the same way that Grothendieck polynomials are dual to Schubert cells in the complete flag variety. As a consequence, the finite truncations of the multi-fundamental quasisymmetric functions of Lam-Pylyavskyy acquire a geometric interpretation as $K$-theoretic representatives of quasisymmetric Schubert cells.

We develop a first and second fundamental theorem for $n$–tuples of bosonic and fermionic matrices, by developing graded analogues of the classical case.

Let $G$ be a simple connected graph on $n$ vertices, and let $\lambda_1(G),\lambda_2(G),\ldots,\lambda_n(G)$ be the eigenvalues of its adjacency matrix $A(G)$. For $p>0$, define the $p$-energy of $G$ by $\mathcal E_p(G)=\sum_{i=1}^n |\lambda_i(G)|^p$. We prove that, for every real number $p\ge 2$ and every simple connected graph $G$ on $n$ vertices, $$ \mathcal E_p(G)\ge \mathcal E_p(P_n), $$ where $P_n$ denotes the path on $n$ vertices. Moreover, for each fixed $p>2$, equality holds if and only if $G\cong P_n$. Together with the previously known star-minimality results, this completes the solution of two questions of Nikiforov. The proof combines two different comparison principles. For $2<p<4$, we use a bipartite reduction, a Mellin representation of fractional powers, and a determinant comparison involving matching generating polynomials and tree shifts. For $p\ge4$, we prove a second-order stop-loss comparison for the squared singular values of bipartite graphs. This comparison is established by rank-one spectral-shift estimates, deletion-minimal counterexamples, and a finite certified analysis of the terminal sparse-sun configurations.

This paper studies the Manickam-Miklós-Singhi (MMS) property for graphs and hypergraphs. Using the structural characterisation of the $2$-uniform case, we construct new families of regular graphs with the MMS property. We then analyse the Erdős–Rényi random graph model $\mathbf{G}(n,p)$ and identify regimes in which the MMS property holds with high probability. Finally, we extend the matching-based sufficient condition to higher uniformities via pseudo-matchings and introduce a blowout construction that produces higher-uniformity hypergraphs with the MMS property from lower-uniformity examples.

We prove that all lattice path matroids are Ehrhart positive. This unifies and generalizes numerous results on the Ehrhart positivity of matroids developed over the last two decades. We rely on our previous work on the positivity of order polynomials of fences. Our main result supports the conjecture by Ferroni, Jochemko, and Schröter (2022) on the Ehrhart positivity of positroids. Furthermore, our main result implies that all Schubert matroids are Ehrhart positive, which thus settles a conjecture by Fan and Li (2024), and shows Newton polytopes of certain Schubert and key polynomials are Ehrhart positive.

A fuzzy Boolean function is a map $f:\cube^n\to [0,1]$, where $n\in\mathbb N$. We introduce and compare three ways of saying that such a function has bounded complexity. The first is a sampling property: the value $f(x)$ can be recovered, up to small error and with high probability, from the values of a bounded number of randomly chosen coordinates of $x$. We call this the holographic property. The second is a structural property: $f$ is uniformly close to a bounded-degree polynomial in boundedly many bounded linear coordinate forms. The third is computational: $f$ is uniformly close to the output of a neural network with a bounded number of non-input neurons, bounded Lipschitz activation functions and bounded incoming weights. We prove that these three properties are equivalent up to quantitative changes of the parameters. The implication from holography to polynomial structure uses a variant of a weak version of hypergraph regularity.

Let $p$ be a prime, let $d \geq 1$ be an integer and $A$ be the algebra of square matrices of size $d$ over the field of order $p$. Let $P, Q \in A[x_1, \dots x_n]$ be polynomials in $n$ indeterminates with coefficients in $A$, such that $Q$ is invertible in $ A[\![x_1, \dots, x_n]\!]$. Let also $\mathcal M \colon \mathbf Z^n \to A$ be the map associating to the $n$-tuple of integers $(\alpha_1, \dots, \alpha_n)$ the coefficient of the monomial $x_1^{\alpha_1} \dots x_n^{\alpha_n}$ in the development of the rational fraction $PQ^{-1}$ as a power series (the support of $\mathcal M$ is contained in $\mathbf N^n$). Our main result ensures that the map $\mathcal M$, viewed as a tiling of $\mathbf R^n$ by unit cubes with color set $A$, is self-similar. The self-similarity is expressed in terms of invariance under substitutions. By specializing to $d=1$, $n=2$, $P=1$ and $Q =1-x_1-x_2$, we recover the well-known self-similarity feature of the binomial coefficients modulo $p$.

We prove that every 0/1-polytope has a unique Minkowski decomposition into indecomposable polytopes, up to translation of summands. The summands lie in pairwise orthogonal subspaces. Thus, every 0/1-polytope is the Cartesian product of indecomposable 0/1-polytopes. As applications, we obtain uniform combinatorial indecomposability criteria for order and chain polytopes, matroid polytopes, stable set and clique polytopes, edge polytopes, flow polytopes, and 2-level/compressed polytopes. We also show that every nontrivial factorization of a multi-affine polynomial is a product of multi-affine polynomials in disjoint sets of variables.

A graph $G$ admits an $H$-tiling if it contains a collection of vertex-disjoint copies of $H$. In this paper, we confirm a conjecture proposed by Kühn, Osthus, and Treglown by showing that for any given graph $H$, there exists a constant $C(H)$ such that the following holds. If $G$ is a sufficiently large $n$-vertex graph satisfying $d(x) + d(y) \geq 2\left(1 - 1/\chi_{\text{cr}}(H)\right)n$ for all nonadjacent vertices $x, y \in V(G)$, then $G$ contains an $H$-tiling covering all but at most $C(H)$ vertices. Here $\chi_{\text{cr}}(H)$ denotes the critical chromatic number of $H$.