Papers

We introduce an approximate version of matrix product factorization for graphs. A simple graph $G$ on $n$ vertices is said to admit an $\varepsilon$-matrix product factorization if there exist simple graphs $H$ and $K$ on the same vertex set such that $A(H)A(K)$ and $A(G)$ disagree in at most $\varepsilon n^{2}$ entries. This Hamming-type relaxation preserves, outside the error set, the exact interpretation of each edge as having a unique $H$-then-$K$ two-step witness. We establish equivalent matrix, and witness formulations, showing that the sets $N_H(w)\times N_K(w)$ form an approximate disjoint decomposition of the ordered adjacency relation of $G$, and we derive quantitative constraints involving walk counts and the degrees of the factor graphs. We then construct approximate factorizations for several graph families. Every complete graph $K_n$ has matrix-product-factorization distance $O(1/n)$, despite the exact congruence obstruction that permits exact factorization only when $n\equiv 1\pmod 4$. More generally, a blow-up of a fixed graph on $r$ vertices admits an $\varepsilon$-factorization with $\varepsilon\le r/n$, and the construction is exact whenever every non-isolated part has even order. For bipartite graphs, we give one-sided factorizations that realize one orientation of almost all edges. In particular, every tree on $n\ge2$ vertices admits an $\varepsilon$-factorization with $\varepsilon\le 1/n$, although no nontrivial tree is exactly factorizable. These results show that rigid exact obstructions may disappear under a vanishing proportion of entrywise errors.

We give a closed formula for the number $p^{S_2}(n)$ of self-avoiding polygons (SAPs) of length $n$ on the strip $S_2:=\mathbb{Z}\times\{0,1,2\}$, together with closed formulas for those subtypes of SAPs which are determined by the numbers of vertical steps in their leftmost and rightmost columns. For the subtype whose leftmost and rightmost columns each contain two vertical steps, we also derive an alternative representation as a binomial sum. Our derivation is elementary: it is purely combinatorial and geometric and avoids generating functions. Comparing the two representations yields a new geometric proof of an identity arising in Larsen's treatment \cite{L07} of a problem posed by Gessel \cite{G95}. Finally, we show that this subtype of SAPs is closely connected to the sequence A007909. More precisely, for $m\geq0$, the number of these SAPs whose leftmost and rightmost columns each contain two vertical steps and whose length equals $2m+6$ is given by the term of this sequence with index $m$, which thereby acquires a geometric interpretation alongside the compositions it enumerates.

For graphs \(G\) and \(H\), let \(N(G,H)\) be the number of unlabeled, not necessarily induced copies of \(H\) in \(G\), and let \(f(n,H)\) be the maximum of \(N(G,H)\) over all \(n\)-vertex planar graphs \(G\). Ghosh, Győri, Martin, Paulos, Salia, Xiao and Zamora conjectured that, for every fixed integer \(\ell\ge 2\), \[ f(n,P_{2\ell+1}) =4\ell\left(\frac{n}{\ell}\right)^{\ell+1}+O(n^\ell). \] We prove the conjecture, including the stated error term. Along the way, we also settle the Cox–Martin optimization conjecture.

A tree cover of an $n$-point metric space is a collection of $k$ dominating trees such that every pairwise distance is approximately preserved by at least one tree. The best known general upper bound on the distortion is $\widetilde{O}(n^{1/k})$. Recently, Chen, Tan, and Xu (ITCS 2026, SICOMP 2026) proved a lower bound of $\Omega_k(n^{1/2^{k-1}})$ using a topological approach. We improve their lower bound to $\Omega_k(n^{1/[k(p-1)]})=\Omega_k(n^{1/O(k^2)})$, where $p$ is the smallest prime strictly larger than $k$. Thus, the gap between the known upper and lower exponents is reduced from exponential in $k$ to a factor of $O(k)$. Our key observation is a qualitative difference between the antipodal symmetry underlying the binary labels in the previous approach and the cyclic symmetry used here. In the binary setting, every joint label has a unique antipodal partner, whereas every label in $\mathbb{Z}_p^k$ has many partners that differ from it in every coordinate. This flexibility allows an equivariant Borsuk–Ulam-type theorem in only $k(p-1)$ dimensions to produce two nearby vertices with different labels in all $k$ trees. A cyclic unwinding argument then shows that they are far apart in every tree.

For a finite nonempty subset $A$ of an abelian group, let $\sigma(A)=|A+A|/|A|$ and $\delta(A)=|A-A|/|A|$. The classical sum-difference inequalities state that $$\sigma(A)^{1/2}\leq\delta(A)\leq\sigma(A)^2.$$ The exponent $2$ in the second inequality is known to be optimal, whereas it has remained open whether the exponent $1/2$ in the first inequality can be improved. We settle this question by constructing an explicit family of finite sets $A_K\subset\mathbb{Z}$ such that $$\frac{\log\sigma(A_K)}{\log\delta(A_K)}\longrightarrow 2,$$ hence the exponent $1/2$ in the first inequality is also optimal. The construction and its proof were developed with the assistance of Hyra, an AI research agent based on the open-weights Hy3 model.

We prove a conjecture of Regts and Sevenster: a complex-valued graph parameter $f$ with $f(\emptyset)=1$ has exponentially bounded edge-connection rank if and only if it is a mixed partition function. The bound is exact: for a real number $R\ge 1$, the connection ranks satisfy $\operatorname{rk} M_{f,t}\le R^t$ for all $t\ge 0$ if and only if $f$ has a model on a super vector space $\mathbb{C}^{k|2\ell}$ with $k+2\ell\le R$. Consequently the base of exponential growth of the connection ranks is the least number of colours of a model, the two dimensions of a minimal model are determined by $f$, and the parameters with a model on a prescribed $\mathbb{C}^{k|2\ell}$ are characterised. The proof organises fragments modulo the connection kernel into a rigid symmetric tensor category whose morphism spaces have the connection ranks as dimensions; the rank hypothesis and an argument of Schrijver make its additive idempotent completion semisimple, Deligne's theorem provides a fibre functor to super vector spaces, and the resulting super tensor network is identified with the Regts-Sevenster model exactly, circuit signs included. An appendix shows that in a rigid symmetric $\mathbb{C}$-linear category with $\mathrm{End}(\mathbf{1})=\mathbb{C}$, exponentially bounded endomorphism growth makes the trace zeta function of every endomorphism rational, with explicit degree bounds.

The Stanley–Gasharov conjecture asserts that every claw-free graph is Schur-positive. Prajapati and, independently, Matherne and Morales identified the same pair of counterexamples, both of which are line graphs, thereby disproving the conjecture. In this paper, we construct two infinite families of counterexamples to the Stanley–Gasharov conjecture, thereby answering a question of Matherne and Morales. Every graph in the first family is a line graph, whereas no graph in the second family is a line graph. Prajapati further showed that the graph $G_2$, which has $12$ vertices and $21$ edges, is the smallest counterexample under the ordering that first compares the numbers of vertices and then the numbers of edges. We show that $G_2$ is also the smallest counterexample under the reverse ordering, which first compares the edge numbers and then the vertex numbers. Similarly, we exhibit a graph $Q$ with $13$ vertices and $27$ edges and show that $Q$ is the smallest counterexample that is not a line graph under each ordering. Our two infinite families are obtained from $G_2$ and $Q$, respectively, by adjoining a clique of order at least $4$ and connecting one of its vertices to a distinguished vertex of the original graph by a single edge.

Let $G=(V,E)$ be a possibly infinite, locally finite graph with non-negative Ollivier–Ricci curvature and degrees bounded by $d<\infty$. We prove that there exists a constant $C_d$ such that the continuous-time random walk displacement and log-volume growth satisfy \[ \mathbb{E}_x \mathrm{dist}(x,X_t)^2 \le t \exp\left[C_d \sqrt{\log t \log\log t}\right], \] \[ \log \mathrm{Vol}(B(x,r)) \le \exp\left[C_d \sqrt{\log r \log\log r}\right], \] for every $x\in V$ and all $r,t \ge e^e$.

This paper investigates the relationship between coding theory and extremal combinatorics by representing codes in general metric spaces as independent sets in proximity graphs. We provide a generalized framework for the Gilbert-Varshamov (GV) bound applicable to codes over any finite metric space and explore the conditions under which global combinatorial parameters can force the existence of codes exceeding this bound. Central to our analysis is the introduction of Ramsey-Sidorenko and independence-forcing graphs. We establish density thresholds for various graph families and utilize the Karush–Kuhn–Tucker conditions to analyze entropy optimization in the Hamming case. Furthermore, we derive upper bounds on code sizes using fractional packings in vertex-transitive and nonedge-transitive graphs. Our findings demonstrate that local subgraph statistics alone are insufficient to surpass the GV bound in the Hamming case, suggesting that improvements must stem from large-scale structural properties of the space.

Given two $m$-ary predicates $P,Q$, an $n$-ary polymorphism is a tuple $(f_1,\dots,f_m)$ of functions such that $x^{(1)},\dots,x^{(n)} \in P$ implies $(f_1(y_1),\dots,f_m(y_m)) \in Q$, where $y_i = (x^{(1)}_i,\dots,x^{(m)}_i)$. This generalizes the usual definition in universal algebra, in which $P = Q$ and $f_1 = \cdots = f_m$. In earlier work, we studied when all polymorphisms of a single predicate are "trivial": either all depend on a single coordinate (common to all of them), or they constitute a "certificate" for the predicate. We showed that it suffices to check this condition for $2$-ary polymorphisms, and even for $1$-ary polymorphisms, modulo an explicit list of obstructions. In this paper we generalize the first result to the $P,Q$ setting, for a relaxed notion of certificate. We also generalize the second result in the promise setting, in which $P,Q$ range over the same alphabets and $P \subseteq Q$.

We investigate a remarkable probability distribution on the symmetric group, due to Steck from the early 1970's, arising from a natural process that intertwines continuous and discrete selections for the values and positions, respectively, of a permutation. Steck used a matrix determinant to express his distribution, whereas we contribute new combinatorial formulas for it in terms of "bottom-to-top maxima" (that are simply the left-to-right maxima of the inverse) permutation statistics. These formulas specialize, in the case of the identity permutation, to a result of Pitman–Stanley from the late 1990's. We then use the Steck distribution to define a game of best choice (secretary problem variation) that incorporates a filtering process for the pool of candidates over time. We solve the model for the case where there is a single filtering step. It turns out that the probability of winning the game under optimal play is similar to the classical model ($1/e$, asymptotically), but that the interviewer must employ a different (non-positional) strategy in order to attain it. The optimal strategy depends on the relationship between interview position and the next bottom-to-top maximum value after the filtering step. Among other results, we prove that the optimal strategy always transitions from rejection to acceptance between positions $(1/e)$ and $(1/e) + (1 - 1/e)y$ as a proportion of the total candidates considered, where $y$ is the proportion of unfiltered candidates.

It is shown that the $\mathsf{OR}$-rank (covering rank) of the $2^n \times 2^n$ unique disjointness matrix is $n^{O(1)}(3/2)^n$, hence the known lower bound $1.5^n$ turns out to be essentially tight. By the way, an upper bound $1.89^n$ is obtained for the $\mathsf{SUM}$-rank (partition rank) of this matrix.

For graphs $F$ and $H$, the Ramsey number $R(F,H)$ is the minimum integer $N$ such that every $N$-vertex graph contains $F$ or its complement contains $H$. If $F$ is connected and $|F|\ge\sigma(H)$, a construction of Burr gives $R(F,H)\ge(\chi(H)-1)(|F|-1)+\sigma(H)$, where $\sigma(H)$ denotes the minimum order of a color class in a proper $\chi(H)$-coloring of $H$. Burr proved that this bound is attained for $F=C_n$ when $n$ is sufficiently large. Allen, Brightwell and Skokan conjectured that equality already holds whenever $n\geq |H| \chi(H)$, while Haslegrave, Hyde, Kim and Liu subsequently proved it whenever $n\ge C|H|\log^4\chi(H)$. Pokrovskiy and Sudakov conjectured that the optimal linear condition $n\geq C|H|$ suffices; this conjecture was also highlighted by Montgomery in his 2026 ICM survey (see Conjecture 9.2). In this paper, we resolve this conjecture by proving that there is an absolute constant $C>0$ such that $R(C_n,H)=(\chi(H)-1)(n-1)+\sigma(H)$ for every nonempty graph $H$ and every $n\ge C|H|$. This gives the first bound linear in $|H|$, and is best possible up to a constant factor. Our proof builds on the framework of Haslegrave, Hyde, Kim and Liu, and combines some new ideas in expansion and switching cycle lengths.

In 1978 Babai raised the question whether all semiminimal Cayley graphs have bounded chromatic number. In this paper we show that semiminimal Cayley graphs of abelian and generalized dihedral groups have circular chromatic number at most 4, thus extending a result of Barajas and Serra.

Let $S_n(32\text{-}1)$ and $S_n(3\text{-}21)$ denote the sets of $n$-permutations avoiding the vincular patterns $32\text{-}1$ and $3\text{-}21$, respectively. Using Lehmer codes, we realize these families as weighted posets $L_n(32\text{-}1)$ and $L_n(3\text{-}21)$, where the weight of a code is the inversion number of its permutation. We show that the maximal elements of each of these posets, $\operatorname{Max} L_n(32\text{-}1)$ and $\operatorname{Max} L_n(3\text{-}21)$, are enumerated by the Fibonacci numbers. We demonstrate that the classical reverse-complement map on permutations restricts to a natural bijection between these two sets of maximal elements, revealing a deep symmetry between their underlying poset structures.

Let $\mathbf p=(p_1,\ldots,p_n)$ and $\mathbf q=(q_1,\ldots,q_n)$ belong to $(0,1/2]^n$, and let $\mu_{\mathbf p}$ and $\mu_{\mathbf q}$ be the associated measures on $2^{[n]}$. Suppose that $p_1q_1=\max_{i\in[n]}p_iq_i$. We prove that every pair of cross-intersecting families $\mathcal A,\mathcal B\subseteq2^{[n]}$ satisfies the sharp inequality $\mu_{\mathbf p}(\mathcal A)\mu_{\mathbf q}(\mathcal B)\leq p_1q_1$. This confirms a conjecture of Suda, Tanaka and Tokushige [Math. Program. 166 (2017) 113–130]. We also determine all equality cases. When $p_1q_1<1/4$, equality is attained only when both families consist of all subsets containing the same product-maximizing coordinate. At the endpoint $p_1q_1=1/4$, we identify precisely the additional extremal pairs, which are induced by half-sized increasing families on the coordinates satisfying $p_i=q_i=1/2$. We further resolve the remaining conjecture from the same paper by proving a dimension-free stability theorem. Assume that the first coordinate has maximum probability under both measures and that $p_1,q_1<1/2$. If $\mu_{\mathbf p}(\mathcal A)\mu_{\mathbf q}(\mathcal B)\geq(1-\varepsilon)p_1q_1$, then there exists a coordinate $j$ such that both $\mathcal A$ and $\mathcal B$ are within $c(p_1,q_1)\varepsilon$, in their respective measures, of the family of all subsets containing $j$. This improves the conjectured $O(\sqrt{\varepsilon})$ bound to a linear one. The main new ingredient in the sharp measure theorem is a log-odds interpolation combined with induction on coordinate sections, while stability follows from a semidefinite estimate and a one-coordinate approximation theorem.

Via the method of marked permutation tables presented in this paper, we generalize the formula for the sixth moment of a random determinant to account for entries with arbitrary distribution. That is, let $f_6(n) = \mathbb{E}(\det A)^6$, where $A$ is an $n$ by $n$ random matrix with independent and identically distributed entries. We show that the exponential generating function $F_6(t) = \sum_{n=0}^\infty f_6(n)t^n/(n!)^2$ is D-finite and we present it in a closed form. Our method relies on carefully decomposing marked permutation tables into a shell, a core, and a floating component, each of which has a separate contribution to $F_6(t)$. After this decomposition, it is sufficient to enumerate over a finite number of possible shells, which we did using a highly intricate computer program. We verified our result up to $n = 7$ in the general case and up to $n = 9$ for random matrices whose entries only take two values by using a different method for computing $f_6(n)$ for these cases.

We study general position sets in strong products involving paths and cycles. For every connected graph $H$ and every $s\ge 2$, we prove that gp$(P_s \boxtimes H)=2$gp$(H)$. We also determine the corresponding values when the path is replaced by $C_4$, $C_5$, or $C_6$, and establish a general upper bound for gp$(C_s \boxtimes H)$. These results are then applied to strong products of two cycles. We determine several exact values, construct infinite families attaining the general upper bound, and provide counterexamples to the conjectured multiplicativity of the general position number under the strong product.

We study automorphism groups in five extremal families of polyhedral graphs. For every $n\ge14$, we prove that every minimum-order $3$-polytopal graph containing a vertex of each degree $3,4,\ldots,n$ is asymmetric. The proof uses an exact planar defect decomposition, a complete description of the high-degree tail, and a saturation theorem for the subgraph induced by the uniquely high-degree vertices. Duality gives the corresponding asymmetry result for minimum-face polyhedra containing faces of every size $3,4,\ldots,n$. For the three polyhedral graphs whose complements are also polyhedral, we determine the ordinary and extended automorphism groups and identify the extended group \[ \mathsf{Aut}^{\pm}(G_{13})\cong (C_2\times C_2)\rtimes C_4. \] Next, we classify automorphism groups of radius-one polyhedra. In the unique-dominating-vertex case they are cyclic or dihedral, and in the triangulated case the possibilities are \[ 1,\qquad C_2,\qquad C_3,\qquad C_2\times C_2,\qquad S_3. \] For polyhedra that are unigraphic among the class of self-dual, we show that their automorphism group is either $1$ or $C_2$. Finally, we consider polyhedra that are products of graphs, for each of the four standard graph products, and we classify them according to their automorphism group.

This article focuses specifically on the study of self-dual double cyclic codes over a finite field $\mathbb{F}_q$. A self-dual double cyclic code is a double cyclic code that is equal to its dual. Structurally, a double cyclic code of length $(r,s)$ over $\mathbb{F}_q$ is a $\mathbb{F}_q[x]$-submodule of $\mathbb{F}_{q,r,s}:=\mathbb{F}_q[x]/\langle x^r-1\rangle\times\mathbb{F}_q[x]/\langle x^s-1\rangle$. Moreover, any double cyclic code of length $(r,s)$ over $\mathbb{F}_q$ is generated by two pairs of polynomials in $\mathbb{F}_{q,r,s}$. From the properties of the generating elements, we provide the necessary and sufficient conditions such that two pairs of polynomials in $\mathbb{F}_{q,r,s}$ generate a self-dual code. Furthermore, we examine the existence of self-dual double cyclic codes for some specific lengths: $(r,r)$; $(r,2r)$ and $(2r,r)$; and $(r,s)$, where $\gcd(r,s)=1$. For each case, we provide a construction method with some explicit examples over various finite fields. We also observe some connections between self-dual double cyclic codes and other classes of self-dual codes.

In this paper, we revisit the Poincaré polynomials, Betti numbers, and Euler characteristics of the Deligne-Mumford moduli spaces $\overline{\mathcal M}_{0,n}$ of stable $n$-pointed rational curves. We give elementary derivations of two recent closed formulas for their Poincaré polynomials, due respectively to Aluffi-Marcolli-Nascimento (arXiv:2406.13095) and to Eur-Ferroni-Matherne-Pagaria-Vecchi (arXiv:2504.16776). Our approach shows that both formulas are already implicit in the generating-series results of Getzler and Manin, and can be extracted from them by elementary manipulations of generating functions, the binomial series, and standard identities for Stirling numbers. Beyond these new derivations, the same method also yields new linear recurrence relations for refined invariants associated with these Poincaré polynomials, namely distinguished summands and a bivariate refinement. As a further consequence, we obtain two additional formulas for the Betti numbers, not previously recorded in this form. We also study the Euler characteristics $\chi(\overline{\mathcal M}_{0,n})$. Using the Taylor expansion of a suitable branch of the Lambert $W$-function, we show that their sequence is obtained by evaluating complete Bell polynomials at an explicit auxiliary integer sequence. This Bell-polynomial representation yields Hessenberg determinantal formulas and a new linear recursion, distinct from the well-known quadratic Keel-Manin recursion. It also provides an explicit extraction of the Euler characteristics from the Lambert $W$-function expression considered by Aluffi-Marcolli-Nascimento. Finally, we refine the Manin-Zagier asymptotic estimate for these Euler characteristics by computing the full asymptotic expansion.

We study dynamical phase retrieval for Schr\”odinger evolutions on finite connected graphs. Let \[ H\_Q=\Delta\_G+Q \] be a graph Schr\”odinger operator with a real diagonal potential. We investigate when phaseless data obtained from the associated Schr\”odinger evolution \[ |e^{-itH\_Q}u\_0(j)|, \qquad 0\leq t\leq T,\ j\in V, \] determines the initial state $u\_0\in\C^V$ up to a global phase. We give a uniqueness criterion in terms of the eigenvalues and eigenvectors of $H\_Q$. The assumptions are a $B\_2$ condition on the spectrum, meaning that the sums $\lambda\_j+\lambda\_k$ determine the unordered pair $\{j,k\}$, invertibility of the squared-eigenvector matrix $\bigl(\phi\_k(j)^2\bigr)\_{j,k}$ and an overlap condition on the supports of pairs of eigenvectors. Under these hypotheses, the phaseless Schr\”odinger data determine every initial state uniquely, modulo global phase. We then show that the criterion is both realized and generic. Every finite connected graph admits an explicit real diagonal potential for which the criterion holds. Moreover, for every finite connected graph, dynamical phase retrieval holds for Lebesgue-almost every real potential $Q\in\R^V$ and every $T>0$. We also give several obstructions to uniqueness.

We study a graph-limit problem for Banach-decorated graphs. Given a sequence of $X$-decorated graphs whose homomorphism densities converge against all $X^*$-decorated test graphs, we ask whether the limiting densities are represented by an $X$-valued graphon. The results connect this graph-limit problem with Banach-space structure. If $X^*$ is separable, then the graphon representation property for graph sequences uniformly bounded in $L^p$ for every finite $p$ holds if and only if $X$ is reflexive. For Banach lattices, it is equivalent to the Radon–Nikodým property. For dual Banach spaces, it is equivalent to the conjunction of the Radon–Nikodým property and weak sequential completeness. In the bounded setting, the same characterization extends to arbitrary Banach spaces: for every Banach space $X$, the representation property for uniformly $L^\infty$-bounded graph sequences holds if and only if $X$ has the Radon–Nikodým property and is weakly sequentially complete.

Fiorini, Joret, and Wood (2013) showed that tree minors satisfy the so-called Erdős-Pósa property with a linear bound: For every tree $T$ there exists a constant $c \geq 1$ such that, for every graph $G$ and integer $k\geq 0$, either $G$ contains $k$ vertex-disjoint subgraphs each containing a $T$-minor, or $G$ has a set $X$ of at most $c k$ vertices such that $G-X$ has no $T$-minor. In this paper, we prove that the same result remains true if, given a subset $S$ of vertices of $G$, one only considers $T$-minors of $G$ that are rooted in $S$. Here, a $T$-minor is rooted in $S$ if there is a minor-model of $T$ where each branch set contains a vertex from $S$. This result can be seen as a generalization of the classical $S$-Path Theorem of Gallai, which corresponds to the case $T=K_2$. The upper bound on the size of $X$ is best possible up to the value of the constant $c$, and improves on an earlier $O(k^2)$ bound due to Hodor, La, Micek, and Rambaud (2026).

The Comtet numbers $b(n,k)$ and $B(n,k)$ of the first and second kind arise from the powers of $(1+x)\log(1+x)$ and of its compositional inverse, respectively. By interpreting both families as special values of weighted Stirling polynomials, we answer Lehmer's question of whether $B(n,k)$ satisfies a recurrence with a fixed number of terms by proving the four-term recurrence $kB(n+1,k+1)=B(n,k-1)-(n-k)B(n,k)-B(n+1,k)$. The corresponding relation for the unsigned array was conjectured by M. Kurkov, but not proved, in OEIS A354794. We further derive explicit formulas, convolution identities, and differential-difference relations for the Touchard-type polynomials attached to the two families.

Let $D$ be a digraph of order $n$ and size $m$ with the property that no out-neighborhood or in-neighborhood of any vertex is acyclic. We show that, if $D$ is strongly connected, then $m\geq 7n/3$, and, if $D$ is strongly $2$-connected, then $m\geq 8n/3$. Both results are best-possible.

Graph $k$-coloring is one of the classic NP-complete problems. Previous work has studied its average time complexity, defined to be the average runtime of computing a $k$-coloring over the set of all $k$-colorable graphs on $n$ vertices. A highly influential result of Dyer-Frieze from 1989 gave an algorithm with $O(n^2)$ average runtime for constant $k$. This quadratic runtime appeared natural (and possibly even optimal) since almost all $k$-colorable graphs have $\Theta(n^2)$ edges, so one needs at least this time in order to read the (entire) input. However, this was later improved by Kučera in 1995 to average runtime $O(n^2/k)$ for every $k \leq n^{c}$ where $c \in (0, 1)$. Nevertheless, in the most interesting case of $k = O(1)$, the best-known bound remained quadratic in $n$. The true average complexity of the $k$-coloring problem has remained elusive for the last three decades. We break the longstanding quadratic barrier. Our main result in this paper shows that the exact average-case complexity of this fundamental problem is $\Theta(nk)$ for every $k \leq n^{c'}$ and some $c' \in (0, 1)$. For $k = O(1)$, this reveals the average sublinear nature of $k$-colorability: the average-case complexity is linear in $n$, and thus sublinear in the size of the input. We further show that our $\Theta(nk)$ average runtime is optimal, since a simple bound proves that every algorithm that correctly $k$-colors all $k$-colorable graphs requires $\Omega(n k)$ average runtime. Our proofs draw on ideas from sublinear and local algorithms and also yield a local computation algorithm (LCA) for $k$-coloring with average-case probe complexity $\text{poly}(k)$. A key new ingredient in our algorithm is a method for certifying the unique colorability of random subgraphs, using tools from the theory of graph regularity.

Using tools from topological dynamics, H.~Furstenberg introduced the notion of central sets and established the celebrated Central Sets Theorem. The sets which satisfy the conclusion of the Central Sets Theorem are called $C$-sets. Hindman, Maleki, and Strauss first brought the concept of an important type of $C$-sets called the quasi-central sets which are not central sets. In 2017, A. Ghosh gave the combinatorial treatment of $C$-sets in commutative adequate partial semigroups, where $C$-sets are the sets which satisfy the conclusion of Central Sets Theorem for commutative adequate partial semigroups. In this work, we discuss the Quasi-central sets algebraically and dynamically for commutative adequate partial semigroups. We give dynamical characterization of members of idempotent ultrafilters for commutative adequate partial semigroups, also we study the minimal dynamical systems for an adequate partial semigroup.

The main result of the paper is that an inductive argument is established to prove the Fuglede's conjecture for an infinite sequence of square-free order cyclic groups. The tile-to-spectral direction of the conjecture holds for all square-free cyclic groups, whereas we prove the spectral-tiling direction only for those groups among them whose prime factors grow rapidly. To achieve this, we develop an inductive technique with roots in a previous paper by the author co-authored with Fallon, Kiss, and Mayeli. Following recent preprints, Fuglede's conjecture remains open only for finite cyclic groups, and until now, there was no cyclic group for which the conjecture was known that possessed an arbitrary number of distinct divisors.

We study (bounded) finitely additive measures on the group of integers $\mathbb Z$, as elements of the Banach algebra $\mathrm{ba}(\mathbb Z)$, viewed as a natural generalization of ultrafilters. The algebraic structure of $\mathrm{ba}(\mathbb Z)$ extends the semigroup structure of the Čech–Stone compactification, allowing methods from ultrafilter theory to be applied in a broader measure-theoretic setting. We investigate idempotent finitely additive measures and establish additive properties of subsets of $\mathbb Z$ having positive measure. We then proceed to study almost translation-invariant and translation-invariant finitely additive measures, showing that these stronger notions yield correspondingly stronger additive conclusions. In particular, we prove that every subset of $\mathbb Z$ whose measure exceeds a certain explicit threshold necessarily is an $\mathsf{IP}_{n}$-set; with stronger properties and lower thresholds depending on the properties of the relevant measures. Several examples illustrating the sharpness and limitations of the results are also presented, together with a discussion of open problems and directions for future research.