Papers

The trace of the average mixing matrix of a quantum walk measures the "laziness" of the walk: the higher the trace, the more likely that the walker returns home in the long run. In this paper, we develop tools to study this graph invariant arising from Laplacian quantum walks. It is known that the complete graph $K_n$ is the laziest connected graph on $n$ vertices. Using our machinery, we show that the star $S_n$ is the second laziest connected graph on $n$ vertices (and hence the laziest tree on $n$ vertices), the complete multipartite graph $K_{n-2,1,1}$ is the third laziest connected graph on $n$ vertices, and the double star $DS(n-3,1)$ is the second laziest tree on $n$ vertices. We also show that on the same number of vertices, more unbalanced double stars are lazier.

An $st$-orientation of an undirected graph $G$ is an acyclic digraph with a single source $s$ and a single sink $t$ that can be obtained from $G$ by assigning a direction to each edge. The classical problem of deciding if an undirected graph $G$ has an $st$-orientation can be solved efficiently. On the other hand, deciding if an $st$-orientation of $G$ exists that does not have any transitive arc is NP-complete, even if each vertex of $G$ has degree at most four. Here we show that this last decision problem remains NP-complete if $G$ is cubic, which settles an open question by Binucci et al. (2025). We obtain NP-completeness for two variants of the problem: (i) $s$ and $t$ are fixed and given as part of the input and (ii) $s$ and $t$ can be chosen freely. We then use these results to investigate the computational complexity of a problem that arises in computational evolution. Specifically, we show that the problem of deciding if an unrooted binary phylogenetic network has an orientation as a rooted binary phylogenetic network without any shortcuts (the analog of a transitive arcs in phylogenetics) is NP-complete. Our results connect the two (mostly) distinct research areas of orienting undirected graphs and orienting unrooted phylogenetic networks.

We introduce the honeycomb hierarchy, a representation-theoretic framework that gives new asymptotic upper bounds on $R_2(\delta)$. Its first level is the two-row hyperoctahedral representation graph associated with type $S^{(n-k,k)}$. Retaining every two-row irreducible and every coordinate box-transfer channel, together with a moving-projection theorem, yields an explicit four-parameter exponent $\kappa_{\mathrm{HC}}$. The earlier whole-cube exponent $\kappa_H$ is a boundary restriction of this optimization, whereas the fully optimized second MRRW exponent $M_2$ is an exact symmetric slice. The prior best curve is the combined $\kappa_{\mathrm{bin}}=\min\{\kappa_{\mathrm{CW}},\kappa_H\}$, which uses a constant-weight branch $\kappa_{\mathrm{CW}}$. Replacing only the whole-cube branch by the honeycomb bound gives $\kappa_{\mathrm{best}}=\min\{\kappa_{\mathrm{CW}}, \kappa_{\mathrm{HC}}\}$. We prove, on $0<\delta<1/2$, \[ R_2(\delta)\le \kappa_{\mathrm{best}}(\delta) \le \kappa_{\mathrm{bin}}(\delta) \le R_{\mathrm{2MQC}}(\delta)<M_2(\delta),\\[-1mm] \kappa_{\mathrm{best}}(\delta) \le \min\{\kappa_{\mathrm{CW}}(\delta), \kappa_{\mathrm{bal}}(\delta)\} <R_{\mathrm{2MQC}}(\delta), \qquad \kappa_H(\delta)=R_{\mathrm{MQC}}(\delta). \] The hierarchy has two further directions. Increasing the representation depth replaces scalar by matrix-valued transfers on the hive. Increasing the anchor depth localizes it in a stable-set hierarchy. The resulting bounds are monotone in both directions and eventually recover $A_2(n,d)$. A complementary Horn–channel hierarchy gives matrix optimizations whose $2\times2$ level is $\kappa_{\mathrm{HC}}$ and whose $3\times3$ level is a stronger bound. Already at low levels, they can be used to improve the strongest previous general bounds, while the honeycomb framework provides a route towards tighter bounds.

For a graph $ G = (V, E) $ with a vertex set $ V $ and an edge set $ E $, a function $ f : V \rightarrow \{0, 1, 2, . . . , diam(G)\} $ is called a broadcast on $ G $. For each vertex $ u \in V $, if there exists a vertex $ v $ in $ G $ (possibly, $ u = v $) such that $ f (v) > 0 $ and $ d(u, v) \leq f (v) $, then $ f $ is called a dominating broadcast on $ G $. The cost of the dominating broadcast $f$ is the quantity $ \sum_{v\in V}f(v) $. The minimum cost of a dominating broadcast is the broadcast domination number of $G$, denoted by $ \gamma_{b}(G) $. A multipacking is a set $ M \subseteq V $ in a graph $ G = (V, E) $ such that for every vertex $ v \in V $ and for every integer $ r \geq 1 $, the ball of radius $ r $ around $ v $ contains at most $ r $ vertices of $ M $, that is, there are at most $ r $ vertices in $ M $ at a distance at most $ r $ from $ v $ in $ G $. The multipacking number of $ G $ is the maximum cardinality of a multipacking of $ G $ and is denoted by $ mp(G) $. It is known that $mp(G)\leq\gamma_b(G)$. In 2014, Hartnell and Mynhardt proved that $\gamma_b(G)\leq 3mp(G)-2$ whenever $mp(G)\geq2$. In 2019, Beaudou, Brewster, and Foucaud improved this bound to $\gamma_b(G)\leq 2 mp(G)+3$ and conjectured that $\gamma_b(G)\leq 2 mp(G)$. We solve their conjecture by proving that $\gamma_b(G)\leq 2 mp(G)$ for every graph $G$. Our proof is constructive and yields a polynomial-time $2$-approximation algorithm for Maximum Multipacking problem which improves the earlier approximation factor $2+o(1)$.

Phylogenetic networks are graphs that represent the evolutionary history of species. Recently, the class of orchard phylogenetic networks, which can be reduced by so-called cherry-picking sequences, has gained attention for its computational and biological aspects. In this paper, we study a fundamental question on orchards and their cherry-picking sequences by considering the CoveringNumber problem: given an orchard network $N$, how many cherry-picking sequences are needed to reduce all subnetworks of $N$? We initiate this study by considering the problem for trees. We then show that the covering number can be computed for binary trees recursively using a similar but more fine-grained notion of survival covering number. We also give a recursive formula for the survival covering number of non-binary trees. However, computing the covering number for non-binary trees appears to be considerably more challenging. For this case, we show that the covering number of star trees (whose root is adjacent to all leaves) is equivalent to the so-called SubsetConnectivity problem, which we introduce in this paper. Finally, we show that if there is no restriction on the sequence length, a single sequence of minimum length $\binom{n}{2}$ suffices to reduce all subtrees of a tree on $n$ leaves.

Marton's inner bound, the best-known achievable region for a general discrete memoryless broadcast channel, was proposed by Katalin Marton in 1979, and whether it always achieves the capacity region has remained open since then. In this paper, we establish its strict sub-optimality: we show that the capacity region of some discrete memoryless broadcast channels can be strictly larger than Marton's inner bound.

For every fixed $k\ge2$, we give a randomized one-pass insertion-only algorithm that colors an $n$-vertex $k$-uniform hypergraph of maximum degree $\Delta$ with $O(\Delta^{1/(k-1)})$ colors using $\widetilde O_k(n)$ bits of working memory. As a graph-theoretic result of independent interest, we also prove a tight palette-sparsification theorem for general uniform hypergraphs. Independently sampled lists of $\Theta(\sqrt{\log n})$ colors from a palette of size $O(\Delta^{1/(k-1)})$ preserve colorability with high probability; the list-size dependence is asymptotically optimal. These results extend to bounded-rank hypergraphs. We complement the algorithm with a deterministic lower bound: for every fixed polylogarithmic semi-streaming space bound, there are polylogarithmic values of $\Delta$ for which any deterministic one-pass algorithm requires $\exp(\Delta^{\Omega(1)})$ colors.

We prove that every finite point set of size at least $10^{11055931}$ has four collinear points or six points that pairwise see each other. This resolves the first open case of the big-line-big-clique conjecture of Kára, Pór, and Wood.

First formulated by Amarilli, Monet, and Suciu (arXiv:2401.16210, 2024), the Non-Cancelling Intersections (NCI) conjecture is an open problem in combinatorics stating that any set union can be constructively built from its algebraically non-cancelling intersections using only disjoint unions and subset complements. In the same paper, two orthogonal possible strengthenings are proposed: using only left-linear trees, and using non-trivial intersections only positively or only negatively depending on the sign of their Möbius value. Here we show that using only left-linear trees, the conjecture is false (independent of the other strengthening). Our argument is non-constructive. We prove the existence of a counterexample, though it is of immense size.

We present a simple linear-time algorithm that outputs an Eulerian tour of an undirected multigraph with $n$ vertices and $m$ edges, if one exists, in $O(m)$ time and using $O(n)$ words of working memory. The input is given as read-only adjacency lists, and the output is written to an append-only stream in traversal order. Our algorithm first finds a sparse spanning circuit (a skeleton), then traverses the circuit step-by-step, repeatedly outputting further circuits rooted at the current vertex. This solves a problem left open by Ismaili Alaoui, Plump, and Wild (SOSA 2026): their space-efficient variant of Hierholzer's algorithm handles general directed multigraphs, but it is unclear how to generalize it to general undirected multigraphs. Our result completes the picture in the read-only model for space-efficient output of Eulerian tours.

Hard combinatorial optimization problems, many of which are NP-hard, present fundamental algorithmic challenges. Average-case analysis on random instances has emerged as a powerful framework for understanding typical algorithmic performance beyond worst-case guarantees. A substantial body of work has established negative results: for sufficiently hard instances (often controlled by the underlying graph connectivity/constraints density), no known polynomial-time algorithm can significantly outperform naive heuristics in the double asymptotic limit where both problem size and constraints density tend to infinity. We revisit this picture by studying the finite-size behavior of some optimization algorithms across easy, intermediate, and hard regimes. Through rigorous analysis of large-graph asymptotics combined with numerical experiments on canonical problems (maximum independent set and maximum $K$-SAT), we demonstrate that while algorithms do eventually converge to theoretically predicted bounds, this convergence can be remarkably slow. In the intermediate regime where instances are already highly constrained, local algorithms achieve solutions substantially better than their predicted performance in the high-constraint-density limit. This gap between finite-regime and asymptotic behavior has important practical implications: sophisticated algorithmic design remains crucial even when asymptotic theory predicts inevitable failure.

The Ramsey number $R(m,n)$ is the smallest order at which every red-blue edge coloring of a complete graph must contain a blue clique (a complete subgraph) of size $m$ or a red clique of size $n$. Determining these numbers exactly is extremely hard, and even certifying a lower bound requires exhibiting an explicit coloring that avoids both cliques. We develop an integer programming framework for certifying such lower bounds, restricting the search to circulant graphs, whose rotational symmetry lets us reformulate the problem in a projected distance space, reducing the number of binary variables from quadratic to linear in the graph order. We strengthen this projected model through coefficient reduction and solve it with a branch-and-cut algorithm whose separation routine exploits the common neighborhood structure of circulant graphs, combining heuristic and exact maximum-clique algorithms. In an extensive computational campaign on circulant graphs with up to 410 vertices, we improve the best lower bounds previously obtained by other methods by up to 11 points for 25 values of $R(3,n)$ with $24\le n\le49$ and $n\neq27$, each backed by an explicit graph certificate that can be independently verified with a stand-alone exact clique solver. To the best of our knowledge, our method also provides the first reproducible optimization-based procedure for certifying circulant Ramsey numbers $R_C(m,n)$, which we use to establish eight new values of $R_C(3,n)$ with $13\le n\le20$. Our framework, graph certificates, and stand-alone checker are provided as supplementary material to support independent verification and reuse.

In a graph $G$, a set of edges $F$ is called a forcing set if there exists a unique perfect matching $M$ such that $F \subseteq M$. Similarly, a set of edges $A$ is called an anti-forcing set if the graph with edge set $ E(G)\setminus A$ has a unique perfect matching. It is known that, given a bipartite graph $G$ of maximum degree~$3$ and a perfect matching $M$, the problem of deciding whether there exists a forcing set of size at most $k$ for $M$ is NP-complete. Moreover, given a bipartite graph $G$ of maximum degree~$4$ and a perfect matching $M$, the problem of deciding whether there exists an anti-forcing set of size at most $k$ for $M$ is NP-complete. Furthermore, given a bipartite graph of maximum degree~$5$, the problem of deciding whether there exists a perfect matching $M$ that can be made unique by a forcing set of size at most $k$ is also NP-complete. In contrast, the computational complexity of deciding whether there exists a perfect matching $M$ that can be made unique by an anti-forcing set of size at most $k$ is not known, even for general graphs. In this paper, we show that all of these problems remain NP-complete even when restricted to bipartite graphs of maximum degree~$3$.

The two-dimensional bandwidth minimization problem (2DBMP) seeks an injective embedding of a guest graph into a square grid that minimizes the maximum Manhattan distance over its edges. Heuristic methods can provide strong upper bounds, but these bounds do not by themselves certify optimality. We present an efficient exact SAT-based approach for 2DBMP that incrementally searches for the minimum feasible bandwidth and certifies optimality through satisfiability and unsatisfiability results. On the standard $\lceil\sqrt n\rceil \times \lceil\sqrt n\rceil$ host grid, under a 3600 s time limit, the proposed SAT approach certifies optimal bandwidths for 41 of 43 Regular instances and 42 of 93 Harwell–Boeing instances, achieving substantially broader optimality certification within the 3600 s time limit than a previous exact approach evaluated with a 72-hour time limit. In addition, it certifies three bandwidth values that improve all previously published comparison values considered in this study and establishes all three as optimal. We further evaluate the approach on alternative host geometries, namely $2\times\lceil n/2\rceil$ and $n\times n$ grids, to assess its effectiveness beyond the standard host. Overall, the results demonstrate that the proposed SAT approach provides an effective exact method for the small- and medium-sized benchmark instances considered in this study, with fewer than 400 vertices, while heuristic methods remain important for larger and more challenging instances.

This paper presents new theoretical results on generalizing the Jaccard distance for lattices and real valuations. We demonstrate that when the valuation is strictly positive, monotone, and modular, the Jaccard distance satisfies the triangle inequality on arbitrary lattices, effectively generalizing earlier results that depended heavily on distributivity. Moving to relatively complemented distributive lattices (which safely drop the requirement for the global bounds found in Boolean algebras), we prove the triangle inequality holds as long as the valuation is positive, monotone, supermodular, and $\log$-submodular. Additionally, we adapt the symmetric-difference Jaccard formulation for submodular valuations to sectionally complemented distributive lattices. Shifting to necessary conditions, we prove that supermodularity is a strict requirement for the standard generalized Jaccard distance to operate as a valid metric. Finally, we map the practical value of relaxing these structural constraints to computational fields like quantum information theory, formal concept analysis, and machine learning, closing with a brief look at open mathematical problems.

Reaction networks model reactions between a finite set of species. These networks can be associated with different semantics, depending on the type of analysis and the phenomena under study. The standard continuous semantics is given by a system of differential equations based on the kinetic expressions of the reactions. To simulate a network under this semantics, the full knowledge of the kinetic laws of each reaction and the initial concentrations of each species is necessary. Since in empirical settings the quantitative information about the reactions can be partially or totally unknown, the challenge is to introduce new semantics that can still be applied. In this direction, a recent approach in the state of the art concerning Reaction Networks proposes a qualitative abstraction that is too coarse to properly capture the time-course continuous behaviour. Starting from the ideas of this approach, in this paper we first introduce the causal continuous semantics for Reaction Networks to capture their continuous-time dynamics, preserving the causality hidden inside each transition. Later, we introduce the differential sign semantics to abstract in a qualitative way the behaviour of a system under the causal continuous semantics. We show that our new method, based on abstract interpretation, yields appropriate Boolean transition graphs that refine those provided by the previous approach.

For each $d\in\N_{\geq 2}$ we construct a Delone set $Y$ in $\R^{d}$ for which every Lipschitz bijection from $Y$ to $\Z^{d}$ has a very irregular inverse. For example, the inverse fails to be Lipschitz, even at just a single point. Further, we clarify the relationship between several notions of regularity for bijections between Delone sets, studied in the literature.

Let $Q$ be a nonzero $s\times t$ $(0,1)$-pattern, and let $m\ge s$ and $n\ge t$. An $m\times n$ matrix is strongly $Q$-forcing if every $1$-entry belongs to an $s\times t$ submatrix equal to $Q$. Let $F^{*}(m,n,Q)$ count these matrices. Put $H=m-s+1$ and $W=n-t+1$. We prove \[ F^{*}(m,n,Q)\ge 2^{HW}. \] Writing $r$ and $c$ for the numbers of nonzero rows and columns of $Q$, equality holds if and only if \[ (H=1\text{ or }r=1)\qquad\text{and}\qquad(W=1\text{ or }c=1). \] Thus the minimum over all nonzero $s\times t$ patterns is $2^{HW}$, attained exactly by singleton patterns when $H,W>1$, and every fixed nonzero pattern has square growth rate $1$. We also refine the count by weight. If $o(Q)$ is the number of $1$-entries of $Q$, then the number of strongly $Q$-forcing matrices at the minimum positive weight $o(Q)$ is $\binom{H+r-1}{r}\binom{W+c-1}{c}$; at every fixed density in $(0,1)$, the logarithmic growth rate is the binary entropy when $m$ and $n$ are comparable. For ordinary forcing, where every $s\times t$ submatrix contains the $1$-entries of $Q$ in their prescribed positions, let $F(m,n,Q)$ be the number of forcing matrices and let $\mathfrak m(m,n,Q)$ be their minimum weight. We prove \[ F(m,n,Q)=2^{mn-\mathfrak m(m,n,Q)} \quad\text{and}\quad 2^{\,mn-\mathfrak m(m,n,Q)+HW} \le F(m,n,Q)F^{*}(m,n,Q) \le 2^{mn}. \] The lower product bound has the same equality cases as the strong-forcing lower bound above, while the upper product bound is attained exactly by singleton patterns. In particular, the product is at least $2$, with equality exactly when $s=m$, $t=n$, and $Q$ is the all-ones pattern.

Let $K_{r,s,t}$, with $r\le s\le t$, denote the complete tripartite graph whose partite sets have sizes $r,s,t$. Mahmoodian and Mirzakhani gave three necessary conditions for $K_{r,s,t}$ to admit a decomposition into 5-cycles and conjectured that these conditions are sufficient. One of the conditions is $t\le 4rs/(r+s)$. We prove the conjecture for every odd triple on the extremal boundary $t = 4rs/(r+s)$. The proof is constructive. After reducing an arbitrary odd boundary triple to $(r,s,t)=(hga,hgb,hab)$, $a+b=4g$, we give an explicit cyclic decomposition of $K_{ga,gb,ab}$ and use the Mahmoodian and Mirzakhani scaling theorem to supply the common factor $h$. Together with the previously known all-even result, this settles the conjecture for every triple satisfying the boundary condition with equality. We also report explicit computer-generated $C_5$-decompositions for 117 odd triples satisfying the necessary conditions, 116 of which are strict-interior cases. To the best of our knowledge, all 117 cases were previously unresolved: no decomposition for any of them had been reported, and none of the 117 triples is covered by earlier existence results, constructions, or their recursive consequences. Moreover, these 117 certificates together with the boundary construction settle every previously unresolved triple satisfying the necessary conditions with fewer than $4400$ edges. Each computation is supplied as a machine-readable cycle-list certificate and can be checked independently by a short Python verifier. We also give a complete human-readable edge-label-matrix certificate for $K_{9,19,23}$.

We initiate a polyhedral study of the graph multi-separator problem proposed by Irmai et al. (2024) as an alternative to the lifted multicut problem for application to the task of image segmentation. Starting with an integer linear program (ILP) formulation and the multi-separator polytope spanned by its feasible solutions, we characterize in terms of efficiently-decidable, graph-theoretic conditions all facets induced by inequalities of the ILP. We proceed by strengthening these inequalities and describing additional facets of some multi-separator polytopes induced by the stronger inequalities. Specifically, we obtain a totally dual integral description of the multi-separator polytope for paths in the case where separation is considered for all vertex pairs. Finally, we relate the multi-separator polytope to the boolean quadric polytope, showing that facets induced by odd-cycle inequalities do not transfer generally, and to the lifted multicut polytope, showing that either polytope is a projection of a face of the other.

Arrow allegories provide a convenient abstract framework to work with lattice-valued relations, or more precisely, relations that use the elements of a given Heyting algebra as truth values. One characteristic of arrow allegories is that all relations of the given arrow allegory use the same Heyting algebra ${\mathcal H}$. In this paper we want to extend this approach to allegories where relations between different objects may use different lattices of truth values and even further to relations that use a different lattice of truth values for every pair in the relation. Therefore, we define three concrete allegories, $\mathrm{Rel}({\mathcal H})$, $\mathrm{Rel}^u({\mathcal H})$ and ${\mathcal H}{\rm-Rel}$, where the allegory listed later is a full suballegory of the previous ones. These three allegories capture the three different situations mentioned above. In particular, ${\mathcal H}{\rm-Rel}$ is the standard example of an arrow category. We investigate these allegories and provide suitable categorical definitions for these structures.

In this paper, we address several problems concerning vector spaces enclosed in a given set. Let V be a vector space over a finite field of cardinality c, and let $S \subseteq V$ be a set of vectors. A space enclosed in S is a vector subspace W of V that is also contained in S: $W \subseteq S$. We focus on enumeration problems, where the task is to list all solutions, and we first provide an algorithm to enumerate all spaces that are enclosed in S. Our algorithm is further adapted to solve two more problems: the enumeration of (inclusion-)maximal enclosed spaces, and the problem of finding an enclosed space of maximum dimension. The latter problem arises in the context of Boolean functions' regularity detection. It can also be seen as a dual version of the well-known linear span: indeed, the span is the minimum-dimension vector space that contains a given set of vectors S, and it is a fundamental concept in linear algebra. Our proposed algorithms are based on the binary partition paradigm, and have total time complexity $e^{\frac{1}{2\ln c}\ln^2 n - \Theta(\log n \log \log n)}$, where $n= |\inputset|$. The first version, for enumerating all enclosed spaces, also achieves a delay (time between consecutive outputs) of O(n). Our algorithms provide a quadratic speed-up with respect to a brute-force approach, although the speed-up appears even greater in our experimental evaluation on boolean vector spaces.

Karger's randomized contraction algorithm finds a minimum-weight cocircuit of a matroid whenever the cogirth-density ratio is bounded. We prove that the same hypothesis yields a deterministic algorithm with the same exponent. If every contraction minor of rank at least $r_0$ of a matroid $M$ has cogirth-density ratio at most $c$, then a minimum-weight cocircuit of $M$ is computable deterministically in $m^{O(r_0)} n^{O(c)}$ time when the contraction minors of bounded rank have at most $m$ parallel classes, by an algorithm that knows neither $r_0$ nor $c$. As a consequence, we give a deterministic algorithm computing the cogirth of rank-$p$ perturbed graphic matroids in $2^{O(p^2)} n^{O(1)}$ time, fixed-parameter tractable in $p$, settling the cogirth side of a question of Geelen and Kapadia (2018). The extensions of the contraction method carry over deterministically: enumerating all near-minimum 1-cocycles, computing a minimum-weight $k$-cocycle, and computing the Pareto frontier under several positive criteria.

Discrete Convex Analysis (DCA) is a discrete analog of continuous convex analysis, originally proposed as a unified theoretical framework for efficiently solvable combinatorial optimization problems. Recently, DCA has proven to be a powerful tool across diverse fields, ranging from operations research to economics and pure mathematics. Motivated by the broad applicability of DCA, this paper establishes a unified theory of discrete convex analysis over discrete structures arising from classical root systems, extending the usual setting of the integer lattice, which essentially corresponds to type A. We adopt the vertex set of the Euclidean Coxeter complex as the primal discrete domain for L-convexity, and the root lattice as the dual discrete domain for M-convexity. Using the associated polyhedral structures, we formulate L- and M-convex functions together with notions of integrality determined by the root system. We show that local optimality guarantees global optimality for these functions. Furthermore, we establish that integral L-convex functions and integral M-convex functions correspond one-to-one via the discrete Fenchel–Legendre conjugate, thereby extending the conjugacy in the original DCA from type A to all classical root systems.

The frequency $K_i$s ($i\in[4,n]$) are studied for symmetric traveling salesman problem ($TSP$) to characterize the structure properties of the edges inside and outside the optimal Hamiltonian cycle ($OHC$). Given a $K_i$ in $K_n$ where $i\in [4,n]$, the frequency $K_i$ is computed with the set of ${{i}\choose{2}}$ optimal $i$-vertex paths with fixed endpoints (optimal $i$-vertex paths) in the $K_i$. Given an $OHC$ edge in a $K_i$, it has a frequency bigger than $\frac{1}{2}{{i}\choose{2}}$ in the frequency $K_i$, and that of an ordinary edge outside the $OHC$ is smaller than $\frac{1}{2}{{i}\choose{2}}$. As the frequency of an edge is computed with the frequency $K_i$s, an $OHC$ edge of $K_n$ has an average frequency bigger than $\frac{1}{2}{{i}\choose{2}}$. It indicates an $OHC$ edge of $K_n$ is also one $OHC$ edge of a $K_i$ containing it. It also found that the probability that an $OHC$ edge has the frequency bigger than $\frac{1}{2}{{i}\choose{2}}$ increases according to $i\in [4, n]$ based on the frequency $K_i$s. For an ordinary edge outside the $OHC$, the probability that it has a frequency smaller than $\frac{1}{2}{{i}\choose{2}}$ increases according to $i$. Based on the findings, a method is given to identify the ordinary edges for $TSP$.

We study repetition avoidance in a word ${\bf w}$ and its curling-number transform $C({\bf w})$. For alphabets of sizes $2$, $3$, and $4$, we use Thue-Morse-based morphic constructions and exhaustive finite searches. A ternary word for which both ${\bf w}$ and $C({\bf w})$ are overlap-free has length at most $84$, whereas over four letters an infinite example exists. Hence $4$ is the smallest alphabet size admitting simultaneous infinite overlap-freeness. The infinite constructions are verified in Walnut; the finite maxima are obtained by exhaustive breadth-first search and checked independently.

The generalized pancake graph $P(m,n)$ is the Cayley graph of the group of colored permutations $\mathbb{Z}_m\wr S_n=(\mathbb{Z}_m)^n\rtimes S_n$ generated by generalized prefix reversals. In this paper, we establish that, for all $m,n\geq2$, the spectral gap $\gamma(P(m,n))$ of the normalized Laplacian satisfies $\alpha_m/n\leq\gamma(P(m,n))\leq1/n$, where $\alpha_m$ is a positive constant that depends only on $m$. As a consequence, for every fixed $m\geq2$, $\gamma(P(m,n))$ is $\Theta_m(1/n)$ as $n\to\infty$. The proof combines Cesi's semi-recursive spectral-gap inequality with a Fourier decomposition of the appropriate operators associated with a coset Schreier graph of color-position pairs. For fixed $n\geq2$, we also establish that $\gamma(P(m,n))$ is $\Theta_n(m^{-2})$ as $m\to\infty$. This disproves a conjecture of Blanco and Buehrle asserting that, for fixed $n$, the corresponding undirected generalized pancake graphs form an expander family. Additionally, we present a counterexample to a recent conjecture of Greaves and Zhu concerning equality between the spectral gaps of the full Cayley graph and the associated coset Schreier graph.

The tournament isomorphism problem is one of the two fundamental bottlenecks to designing better algorithms for the graph isomorphism problem. Though the problem has been investigated for more than five decades, compared to graphs, there are only very few results on the isomorphism problem of tournaments. For most classes of tournaments neither hardness nor polynomial-time solvability is known. Tournaments of bounded VC dimension are such a class for which no results are available, even though the VC dimension is arguably one of the most robust and central notions of combinatorial tameness. Resolving an open problem of Neuen and Grohe, we show that the isomorphism problem for tournaments of VC dimension $d$ can be decided in time $n^{O(d\log d)}$. Consequently, automorphism groups of tournaments of bounded VC dimension can be computed in polynomial time. To this end, we develop a new method to isomorphism-invariantly decompose tournaments. To facilitate recursion, we introduce the notion of a patched tournament and analyze bounded VC dimension in patched tournaments. We design a recursive algorithm that balances the size of the decomposed pieces against their number and makes use of the structure of near twins. In an orthogonal direction, it is known that a hereditary class of tournaments has unbounded VC dimension if and only if it contains all 2-colorable tournaments. As a second result, we show that also this class does not form an obstruction towards polynomial-time isomorphism testing and indeed show that isomorphism of tournaments of bounded chromatic number is polynomial-time decidable.

For a graph $G$, denote by $a(G)$ the number of vertices in the largest induced forest in $G$. The Albertson-Berman conjecture, which had been open since 1979, states that $a(G) \geq \frac{n}{2}$ for every simple planar graph $G$ on $n$ vertices. Although the Albertson-Berman conjecture was recently resolved in the negative by constructing a counterexample with the help of AI, we independently found a counterexample to the Albertson-Berman conjecture without AI and present it in this article. Our counterexample is on $39$ vertices with $a(G)=19$. Finally, we indicate, without a full proof, a variant of this construction with a larger number of vertices, but with a slightly smaller ratio $\frac{a(G)}{n}=\frac{37}{76}$.

The $(\min,+)$ convolution is a central problem in fine-grained complexity, and it remains open whether it can be computed in truly subquadratic time. We study it through tropical polynomials, where $(\min,+)$ convolution is exactly tropical polynomial multiplication. We introduce the tropical decomposition width, $\operatorname{tdw}(A)$, which measures how finely a tropical polynomial can be decomposed into factors of small degree. We prove two modular convexity theorems showing that bounded tropical decomposition width forces convexity on arithmetic progression subpolynomials. This yields deterministic algorithms for computing $a\otimes b$ in $$O\left(n\max(\operatorname{tdw}(a),\operatorname{tdw}(b))^2\right)$$ when $\max(\operatorname{tdw}(a),\operatorname{tdw}(b))$ is given, and in $$O\left(ne^{\min(\operatorname{tdw}(a),\operatorname{tdw}(b))(1+o(1))}\right)$$ without prior knowledge of the width. Neither algorithm requires a decomposition of the input sequences. The same structural ideas give a randomized algorithm for Multiple-Sequence $(\min,+)$ Convolution: given $k$ sequences of length at most $n$, their convolution can be computed in $$O\left(kn^2\sqrt{\min(k,n)}\log^{1.5}(kn)\right)$$ time, improving the natural $O(k^2n^2)$ bound. Finally, we introduce interpolation algebras for tropical polynomials and show that classes with bounded tropical decomposition width admit interpolation algebras of finite generating rank, whereas distinguishing all tropical polynomials of degree at most $n$ requires generating rank $\lfloor n/2\rfloor+1$. We also prove that tropical decomposition width cannot decrease under any flat $\mathbb T$-algebra extension. Together, these results connect the tractability of $(\min,+)$ convolution with structural rigidity in tropical polynomial multiplication.