Papers

Kemeny's constant is used as a measure of the average travel time on a graph. Braess' paradox for graphs is the observation that in some graphs, when an edge is added, Kemeny's constant increases. We introduce the notion of a Braess clique $K_\ell$, a clique that when inserted into a graph on an independent set of $\ell$ vertices, will create an increase in Kemeny's constant. In this context, a Braess edge is a Braess $K_2$. We provide examples of graphs that have a Braess $K_\ell$ for $\ell\geq 3$. We observe that almost every connected planar labelled graph has a Braess $K_\ell$ for each $\ell\geq 3$. We also explore the relationship between Braess edges and Braess cliques in graphs.

A strong majority edge colouring of a graph $G$ is an edge colouring in which, for every edge $e$ and every colour $\alpha$, at most half the edges adjacent to $e$ receive colour $\alpha$. Like many related colouring notions, it admits a natural interpretation as a colouring problem for an associated hypergraph. Somewhat surprisingly, although the corresponding hypergraph may have arbitrarily large vertex degrees, a universal finite upper bound on the sufficient number of colours in a strong majority edge colouring exists under a natural modest minimum degree assumption, unlike in several other closely related majority concepts. We in particular prove that every graph $G$ with minimum degree $\delta\ge5$ admits a strong majority edge colouring with three colours, improving both the previously known bound $\delta\ge9$ for three colours and the result showing that four colours suffice whenever $\delta\ge5$. Our result is best possible with respect to the number of colours and the minimum degree assumption. We also introduce a more general framework of strong $1/k$-majority edge colourings and establish corresponding bounds for this setting.

For positive integers $d$ and $k$, let $n_k(d)$ be the maximum order of a graph of maximum degree at most $d$ and diameter at most $k$. We prove that $$ \lim_{d\to\infty}\frac{n_k(d)}{d^k}=1$$ for every fixed $k$, thereby resolving the asymptotic degree-diameter problem for fixed diameter and proving a conjecture of Bollobás. The lower bound comes from regular graphs $H_{k,q}$, indexed by prime powers $q$, whose vertices are partial flags in $\mathbb{F}_q^{\,2k+1}$. These graphs have diameter $k$ and order $|V(H_{k,q})| =(1+o(1))\Delta(H_{k,q})^k$. We also construct, for every fixed $\ell \ge 2$, graphs of maximum degree at most $d$ and line-graph diameter at most $\ell$ with $(1+o(1))d^{\ell}$ edges.

Suda introduced the notion of a $Q$-polynomial coherent configuration, which provides a natural and important concept. Subsequently, Lato introduced a notion of a $P$-polynomial coherent configuration and proved that every such configuration satisfying the definition has at most two fibers. Although Lato's definition is interesting, particularly because it characterizes distance-biregular graphs, we argue that an alternative definition is desirable. In this paper, we propose an alternative notion of $P$-polynomial coherent configurations that is naturally aligned with Suda's $Q$-polynomial framework. We show that every two-fiber coherent configuration that is $P$-polynomial in Lato's sense is also $P$-polynomial in our sense, whereas the converse does not hold. We further prove that every coherent configuration of type $(2,2;3)$, $(3,2;3)$ or $(3,3;3)$ is $P$-polynomial in our sense. In addition, we present three families of $P$-polynomial coherent configurations with an arbitrary number of fibers: those arising from tight Euclidean $t$-designs in $\mathbb R^2$, the Terwilliger algebra of $H(n,2)$, and the set of all subspaces of $\mathbb F_q^n$. Finally, we give an equivalent condition for the cross-block intersection matrices to be tridiagonal and verify that all three families satisfy this condition.

A b-coloring is a proper vertex coloring such that every color class contains a vertex, a so-called b-vertex, which sees all colors in its closed neighborhood. This type of coloring has been intensively studied from both structural and algorithmic point of view. Recently, Zaker [DAM 2025] introduced the notion of a b*-coloring, which is a b-coloring in which there is a vertex that sees a b-vertex of every color in its closed neighborhood. The b*-chromatic number is the maximum integer k such that there is a b*-coloring with k colors. We partially answer a question posed by Zaker and prove that graphs of girth at least 7 are b*-monotonic, which means that the b*-chromatic number does not increase by taking an induced subgraph. In addition, we discover a class of d-regular graphs of girth at least 5 with b*-chromatic number d+1, which strengthens a result about b-colorings by Dettlaff, Furmańczyk, Peterin, Roux, and Ziemann [AMC 2024]. We also study the parameterized complexity of finding b*-colorings, and show that for many structural parameters, the complexity coincides with that of finding b-colorings. In particular, the b*-chromatic number can be computed in polynomial time on any class of bounded clique-width. For most parameters, the translation from b-colorings is straightforward but for the feedback edge number, the FPT algorithm for b*-colorings is actually much simpler than that for b-colorings by Balabán [MFCS 2026].

We prove that the Chow polynomial of the noncrossing partition lattice is equal to the descent generating function of tieless parking functions. As a consequence, we obtain new results on the descent statistic for parking functions.

Kazhdan–Lusztig $W$-graphs encode the cell structure of Hecke algebras, while their bidirected connected components are called molecules. In finite type~$A$, the Robinson–Schensted correspondence describes cells and molecules, and Beissinger's row insertion constructs the common tableau associated with an involution. In affine type~$A$, the affine matrix-ball construction (AMBC) assigns an affine permutation a pair of tabloids together with a dominant weight, and Marberg introduced affine fixed-point-free (FPF) $W$-graphs indexed by affine FPF involutions. We classify and enumerate the molecules of Marberg's $\m$-type affine FPF $W$-graph $\Gamma_n^{\m}$ and show that molecules with the same AMBC shape have isomorphic underlying simple bidirected graphs. We also prove that labelled complete-cycle row-Beissinger truncations recover the full AMBC datum of an affine FPF involution.

In this note, we introduce the notion of ranked spreadness, a strengthening of the usual spread condition in which the elements of each member can be ordered so that their one-coordinate marginals decay geometrically with their rank. This additional structure removes the dependence on the maximum set size in random-containment estimates. We prove width-free hitting and weighted-concentration theorems for ranked-spread set systems, together with an elementary kernel-extraction theorem showing that ranked spreadness arises naturally in arbitrary distributions on small sets. Our main application is to the simulation of nonadaptive property testers by sample-based testers. If a one-sided tester has average query complexity $d$ and rejects every far input with probability at least $\delta$, then, for every integer $c>d/\delta$, it admits a one-sided sample-based simulation with expected sample complexity $O_{d,\delta,|\Sigma|}\bigl(n^{1-1/c}\bigr)$. More generally, if positive inputs are rejected with probability at most $\gamma$ and far inputs with probability at least $\delta>\gamma$, the same conclusion holds for every $c>d/(\delta-\gamma)$. In particular, for constant-query nonadaptive testers we obtain an exponent $1-\Theta(1/q)$, matching, up to the dependence on the rejection gap, the exponent conjectured by Fischer, Lachish, and Vasudev.

Let $\{0, 1\}^n$ be the Boolean cube, endowed with the probability product measure, where ${\Bbb P}(1)=p$ and ${\Bbb P}(0)=q$ with $0 < p \leq q$ and $p+q=1$. For $i=1, \ldots, m$, let $\phi_i: \{0, 1\}^n \longrightarrow {\Bbb C}$ be $L_i$-Lipschitz functions in the Hamming metric, such that each $\phi_i$ depends on at most $r$ coordinates of $x \in \{0, 1\}^n$, where $rp \geq 12$. For $j=1, \ldots, n$, let $I_j $ be the set of indices $i$ such that $\phi_i$ depends on the $j$-th coordinate. We prove that $E \exp\left\{ \sum_{i=1}^m \phi_i \right\} \ne 0$ provided $\sum_{i \in I_j} L_i \leq {1 \over 10 \sqrt{rp}}$ for all $j$. This translates into a regime for $\pm 1$ spin systems, where a linear increase in the energy of multi-spin interactions requires only a logarithmic increase of the external field to keep the partition function zero-free and the system away from the phase transition. As a corollary, we obtain efficient deterministic algorithms to approximate the partition function in the zero-free region.

For positive integers $r, m$ and $N$, every $r$-coloring of $\{1, \dots, N\}$ contains a monochromatic solution to $x_1+\dots+x_{m+1}=y_1+\dots+y_m$ provided that $N \ge 3^r (r!)^{1/m}$, which is qualitatively optimal when $m$ is logarithmic in $r$.

T. Hasunuma (J. Graph Theory, 2023) conjectured that if $G$ is a $k$-connected (resp. $k$-edge-connected) graph with minimum degree $\delta(G) \ge k + m - 1$, and $T$ is a tree of order $m$, then $G$ contains a removable copy of $T$, that is, a subtree $T'$ isomorphic to $T$ such that $G - E(T')$ is $k$-connected (resp. $k$-edge-connected). We prove (a strengthening of) this conjecture. We also consider removable matchings in graphs with high minimum degree. We show, among others, that if $G$ is a $k$-edge-connected graph on at least $2m$ vertices with minimum degree $\delta(G) \ge k + m$, then there exists a matching $M$ of size $m$ in $G$ for which $G-M$ is $k$-edge-connected.

In this note we prove that in fixed dimension the Ehrhart $h^*$-polynomial of a lattice polytope of sufficiently large lattice width is real-rooted. In particular, this implies strict log-concavity and unimodality of the $h^*$-vector and answers a question of Averkov, Hofscheier and the author. For a lattice simplex we prove the analogous statement for its local $h^*$-polynomial, also called box polynomial. The proofs were found using ChatGPT 5.6 Sol and follow essentially directly from a result by Basu and Oertel that for large enough lattice width counting lattice points approximates the volume.

We present an average case model of classical problems in combinatorial optimization where there are color constraints. In all cases we seek some (spanning) sub-structure of a complete graph of minimum cost. The edges are randomly colored either red or blue. We bias against the red edges by placing a bound on the number of them that are allowed in our structure. This bound will be lower w.h.p. than what would occur without discrimination. We examine the effect of this bias on the minimum cost of a desired structure. We consider minimum cost spanning trees, shortest paths, minimum cost perfect matchings and the asymmetric traveling salesperson problem.

The quartet distance counts the four-leaf subsets on which two binary phylogenetic trees display different topologies. We prove that its maximum over trees on $n$ leaves is $(2/3+o(1))\binom{n}{4}$, resolving a conjecture of Bandelt and Dress from 1986 and calibrating the scale of a fundamental metric for comparing phylogenetic trees. The proof reduces arbitrary pairs of trees to caterpillars by means of a common-root planarization and an identity on five-leaf trees.

A proper coloring of a graph is called a strong odd coloring if, for every vertex \(v\) and every color appearing in the open neighborhood of \(v\), that color appears an odd number of times in \(N(v)\). The corresponding minimum number of colors is the strong odd chromatic number, denoted by \(\chi_{\mathrm{so}}(G)\). Caro et al.~\cite{CaroPetrusevskiSkrekovskiTuzaStrongOdd} proved that every planar graph has strong odd chromatic number at most \(388\). Manattu et al.~\cite{ManattuVinayLakshmanan2026} later constructed planar graphs with strong odd chromatic number \(17\) and asked whether larger values are possible and whether the upper bound \(388\) can be improved. We address these questions as follows. First, we improve the general upper bound by proving that every planar graph \(G\) satisfies \(\chi_{\mathrm{so}}(G)\le 368\). This follows by improving the auxiliary proper facially odd coloring bound for loopless \(2\)-connected plane multigraphs from \(97\) colors to \(92\) colors and combining this with the reduction of Caro et al. and the Four Color Theorem. Second, we give a different explicit planar construction with \(\chi_{\mathrm{so}}(G)=20\), together with a self-contained proof of the exact value. We emphasize that Goetze et al.~\cite{GoetzeKluteKnauerParadaPenaUeckerdt2025} had already posted an arXiv preprint in May 2025 containing a planar example with strong odd chromatic number \(20\). Thus our construction is not a priority claim for the value \(20\), but rather an independent and fully verified construction whose value exceeds \(17\), the value that motivated Problem~1 of Manattu et al.

In recent work, Marcussen, Rubinfeld, and Sudan introduced the notion of quality control problems, which aim to capture the task of determining if a given input is truly random. Formally, their goal is to accept typical inputs from the specified distribution while rejecting every input whose value of a specified statistic is far from the distributional baseline. This captures the empirical practice of using specified statistics as a proxy for the quality of randomness. Empirical algorithms, however, have not exploited the asymmetry in the definition of quality control problems, which require soundness guarantees in the worst-case while only seeking average-case completeness. Their work abstracted a problem definition emphasizing this asymmetry and used it to give efficient quality control algorithms for assessing the randomness of graphs. In this work, we introduce and study quality control problems over sequences, where the goal is to distinguish a sequence of i.i.d. characters from sequences where some specified pattern appears too often (or too infrequently) as a subsequence. We consider this problem in both the finite-alphabet setting and for real-valued sequences. We refer to the former setting as the pattern counting problem. In the latter case, the natural notion of a pattern is to consider the relative ordering of the characters in the subsequence, and we refer to this as the permutation pattern counting problem. Algorithms to approximately count (permutation) patterns of length $k$ in a worst-case sequence of length $n$ can provably require exponential in $k$ queries into the sequence. In contrast, we show that by taking advantage of the asymmetry in the definition of quality control, we give algorithms that run in poly$(k)$ time to solve these problems. We also prove that any quality control algorithm (over some natural distributions) requires superlinear queries in $k$.

As is well known the Catalan numbers can be interpreted as numbers of Dyck paths. The Narayana polynomials and the q-Narayana polynomials for q=-1 can analogously be interpreted as certain weights of these paths. In the present note we try to get some information about the corresponding weights of bounded Dyck paths. This also leads to some number sequences and analogues of Pascals triangle which previously have occurred in other contexts. We consider some examples and obtain some results and conjectures.

The modular product $G\diamond H$ of graphs $G$ and $H$ is a graph on vertex set $V(G)\times V(H)$. Two vertices $(g,h)$ and $(g',h')$ of $G\diamond H$ are adjacent if $g=g'$ and $hh'\in E(H)$, or $gg'\in E(G)$ and $h=h'$, or $gg'\in E(G)$ and $hh'\in E(H)$, or (for $g\neq g'$ and $h\neq h'$) $gg'\notin E(G)$ and $hh'\notin E(H)$. The independence number $\alpha(G)$ of a graph $G$ is the maximum cardinality of a set of pairwise nonadjacent vertices in $G$. In this paper, we study the independence number of the modular product of graphs. We first structurally characterize all independent set of $G\diamond H$ which lead to the exact result on $\alpha(G \diamond H)$. Special cases of this result lead to several sharp bounds and some exact results for $\alpha(G \diamond H)$. Finally, we introduce a partition graph associated with $G \diamond H$ that provides a framework for constructing independent sets of the modular product from independent sets of its substructures.

For fixed $d\geq 2$, let $\tau_d(n)$ be the minimum size of a set $S\subseteq\{0,\ldots,n\}^d$ such that the affine lines determined by pairs of distinct points of $S$ cover the grid. Let $\sigma_d(n)$ be the analogous minimum when every grid point must lie on the closed segment joining two distinct points of $S$. A celebrated result of Alon [GAFA, 1991] proved that $\tau_d(n)$ is of order between $\Omega_d(n^{\alpha_d})$ and $O_d(n^{\alpha_d}\log n)$, where $\alpha_d=\frac{d(d-1)}{2d-1}$, and asked whether the logarithm term is necessary. We prove that $$c_d n^{\alpha_d}\leq\tau_d(n)\leq\sigma_d(n)\leq C_d n^{\alpha_d}$$ for every fixed $d\geq 2$, thereby resolving Alon's problem in a stronger form.

We study partitions which attain the largest Littlewood-Richardson coefficient. More precisely, we prove that the largest $c^\lambda_{\mu\nu}$ is attained at partitions such that $\mu \subseteq \nu$ and $\nu/\mu$ is a disjoint union of squares. We conjecture that for $n \ge 16$, all largest $c^\lambda_{\mu\nu}$ must satisfy this property. We confirm this conjecture numerically, for $16 \le n \le 45$.

Let $G$ be a simple nonempty graph with size $m$, chromatic number $\chi$, and least eigenvalue $\lambda$. We prove that \[ \chi(\chi-1) \le (m+1-\lambda^2)+\sqrt{(m+1-\lambda^2)^2-4(\lambda^2-1)(\lambda^2-m)} \] with equality if and only if $G$ is either a complete graph or a complete bipartite graph, with possibly isolated vertices. The inequality was conjectured recently by Tang and Elphick in [Electron. J. Combin. 33 (2026), \#P2.65].

We introduce and study palindromic-gap partitions: partitions whose sequence of successive differences between consecutive parts is a palindrome. We derive the generating function for this family, treating partitions with an odd and an even number of parts separately, and obtain a bivariate refinement tracking the number of parts. Specializing further, we give explicit closed formulas for the number of palindromic-gap partitions of $n$ into exactly $r$ parts. We then construct explicit bijections between palindromic-gap partitions with $2m+1$, respectively $2m$, parts and ordinary partitions with at most $m+1$ parts, in which the weight of a palindromic-gap partition is encoded by the largest part, or the two largest parts, of its image; composing these yields an explicit bijection between the odd and even families themselves. Finally, we show that a partition is palindromic-gap if and only if its Ferrers diagram, drawn with left-justified rows, is self-complementary under a $180^\circ$ rotation inside its own naturally associated rectangle, identifying palindromic-gap partitions with self-complementary partitions relative to this rectangle. This yields a partial answer to a question of Keith on the enumeration of complementable and self-complementary partitions: we give explicit generating functions for the self-complementary case and exhibit, at $n=15$, a partition that is complementable but not self-complementary, confirming that the two notions are genuinely distinct.

We study basis-aligned two-orthogonal (bato) tensors, which can be written as a sum of critical rank-one approximations whose factors are singular vectors of their flattenings. As such, bato tensors admit a Tucker decomposition and a canonical polyadic decomposition that are related to each other. We prove that generic bato decompositions are identifiable and that their truncations are critical low-bato-rank approximations. We also compute the dimension of the set of bato tensors, and identify the irreducible components of its Zariski closure with isotopy classes of maximal partial Latin hyperrectangles. Many important tensors are bato, such as determinants, matrix multiplication tensors, and other structure tensors of algebras.

For a simple graph $G$ of order $n$, let $\lambda_1(G)\ge \cdots \ge \lambda_n(G)$ denote its adjacency eigenvalues. Hong's problem asks for the optimal upper bound for $\lambda_k(G)$. A recent theorem of Sivashankar gives, for every $k\ge3$, \[ \lambda_k(G)\le \frac{(k-2)\sqrt{k+1}+2}{2k(k-1)}\,n-1, \] with sharp examples arising from maximal real equiangular tight frames. In this paper, we characterize the equality case. We also obtain an explicit combinatorial description of the extremal graphs for $\lambda_3$ and $\lambda_4$.

Lokshtanov, Ramanujan, Saurabh, and Zehavi [ICALP 2018] proved that for any CMSO formula $\phi$, testing $\phi$ on arbitrary graphs can be reduced to testing it on $(q,k)$-unbreakable graphs for appropriate parameters. Their proof is non-constructive, and they ask whether it can be made constructive. We prove that this is impossible: specifically, the parameter $q$ cannot be a computable function of $\phi$.

We introduce and study a finite simple graph of algebraic origin: the Vieta graph on the solution set over $\mathbb{F}_p$ to a symmetric, multivariate equation which is quadratic in each variable. This construction is a broad generalization of the Markoff graph over $\mathbb{F}_p$, extensively studied in the recent literature. We give a systematic approach, partly based on quadratic character sums, to the following basic counting questions: how many vertices does a Vieta graph have, and what is the degree distribution? We focus on explicit counts, addressing the low-dimensional cases in three and four variables.

The graph minor project contains the most influential results in recent undirected graph theory research. There has been progress in recent years in generalising some of their results to directed graphs, with the directed grid theorem of Kawarabayashi and Kreutzer [STOC '15] and the directed flat wall theorem of Giannopoulou, Kawarabayashi, Kreutzer, and Kwon [SODA '22]. We discuss the two different versions of the existing directed flat wall theorem and their drawbacks. Then, we present an alternative directed flat wall theorem that excludes a different digraph as a butterfly minor. This new theorem lies “in between” the two existing ones and, as such, does not have either of these drawbacks. The proof of our flat wall theorem is based on the one by Giannopoulou, Kawarabayashi, Kreutzer, and Kwon [SODA '22], which has been adapted by Giannopoulou and Wiederrecht [STOC~'24]. Here we make further adjustments to match our setting.

The topological Tverberg theorem asserts that if $r$ is a prime power then for any continuous map $f\colon \Delta_{(r-1)(d+1)}\rightarrow \mathbb{R}^d$ from the $(r-1)(d+1)$-dimensional simplex $\Delta_{(r-1)(d+1)}$ to $\mathbb{R}^d$ there exist $r$ pairwise disjoint faces of the simplex whose images have non-empty $r$-fold intersection. By refinement, the same conclusion holds if the simplex is replaced by any polytope of the same dimension. While this dimension is tight for simplices, recent work of Soberón and Zerbib shows that this need not be true for polytopes in general. Here we give topological Tverberg theorems for products of simplices. Each of these improves upon the $(r-1)(d+1)$-dimensional threshold, even while imposing the structural condition that the “Tverberg faces” of the product are themselves the products of pairwise disjoint faces from each simplex factor. As before, refinement extends these results, and in particular their dimensional improvements, to products of arbitrary polytopes. As an example, if $d+1$ is a power of two then whenever $m\geq n\geq d+1$ and $m+n=3d+2$ we show that any continuous map $f\colon \Delta_m\times \Delta_n\rightarrow \mathbb{R}^d$ admits disjoint faces $\sigma_1,\sigma_2$ of $\Delta_m$ and $\tau_1,\tau_2$ of $\Delta_n$ such that $\cap_{i,j\in[2]} f(\sigma_i\times\tau_j)\neq \emptyset$. In the case of multilinear maps, our results imply partitions of grid-indexed point sets in $\mathbb{R}^d$ by specialized subsets with stronger intersection conclusions than given by Tverberg's original theorem. Lastly, we extend our results to van Kampen–Flores type theorems which impose dimensional restrictions on the faces of each product factor.

Detecting structure in complex networks, especially those arising from physical systems, is a central problem across the sciences. One approach is via rich club analysis, which identifies important vertices using a centrality metric and measures whether those vertices are more tightly interconnected than expected by chance. While informative, this approach captures only pairwise interactions, missing out on higher-order ones known to shape the structure and function of many complex systems. We propose a hyper-rich club pipeline that asks whether central vertices are more tightly interconnected than expected by chance through hyperedges encoding higher-order interactions, which also enables the inclusion of important, often omitted, directional information. We work in a broad class of hypergraphs, which we call general directed hypergraphs, that includes as special cases undirected hypergraphs, head-and-tail directed hypergraphs, and totally ordered hypergraphs (a hypergraph related to directed simplicial complexes from topological data analysis). This unifies several non-equivalent notions of directed hypergraph under one definition. On these hypergraphs we define a hyper-rich club framework whose concrete construction depends on explicit choices the domain scientist fixes according to their research goals. Particular choices recover the existing rich club notions for graphs and undirected hypergraphs, and yield the first such notion for each version of directed hypergraphs. We demonstrate that the pipeline recovers meaningful structure in data by studying networks of very different origins: connectomes, temporal networks of infectious spread, networks of poems, and the XGI hypergraph database, in each case detecting structure the standard graph rich club misses.

This is a snapshot of a first part on a possibly much longer text on finite geometries, meaning graphs or finite abstract simplicial complexes. In in this first batch we review 12 subjects: Gauss-Bonnet, Poincare-Hopf, Index expectation, Euler's gem, Euler-Poincare,Unimodularity, Brouwer-Lefschetz, Sphere formula, Level sets, Index formula, Quadratic cohomology and Higher characteristic.