Combinatorics (math.CO)

Abstract: Let $C$ be a cycle and $f : V(C) \rightarrow \{c_1,c_2,\ldots,c_k\}$ a proper $k$-colouring of $C$ for some $k \ge 4$. We say the colouring $f$ is safe if for any planar graph $G$ in which $C$ is an induced cycle, there exists a proper $k$-colouring $f'$ of $G$ such that $f'(v) = f(v)$ for all $v \in V(C)$. The only safe $4$-colouring is any proper colouring of a triangle. We give a simple necessary condition for a $k$-colouring of a cycle to be safe and conjecture that it is sufficient for all $k \ge 4$. The sufficiency for $k=4$ follows from the four colour theorem and we prove it for $k = 5$, independent of the four colour theorem. We show that a stronger condition is sufficient for all $k \ge 4$. As a consequence, it follows that any proper $k$-colouring of a cycle that uses at most $k-3$ distinct colours is safe. Also, any proper $k$-colouring of a cycle of length at most $2k-5$ that uses at most $k-1$ distinct colours is safe.

Abstract: The region in the complex plane containing the eigenvalues of all stochastic matrices of order n was described by Karpelevic in 1988, and it is since then known as the Karpelevic region. The boundary of the Karpelevic region is the union of disjoint arcs called the Karpelevic arcs. We provide a complete characterization of the Karpelevic arcs that are powers of some other Karpelevic arc. Furthermore, we find the necessary and sufficient conditions for a sparsest stochastic matrix associated with the Karpelevic arc of order n to be a power of another stochastic matrix.

Abstract: In this paper we define sparsity and tightness of rank 2 incidence geometries, and we develop an algorithm which recognises these properties. We give examples from rigidity theory where such sparsity conditions are of interest. Under certain conditions, this algorithm also allows us to find a maximum size subgeometry which is tight. This work builds on so-called pebble game algorithms for graphs and hypergraphs. The main difference compared to the previously studied hypergraph case is that in this paper, the sparsity and tightness are defined in terms of incidences, and not in terms of edges. This difference makes our algorithm work not only for uniform hypergraphs, but for all hypergraphs.

Abstract: For graphs $G$ and $H$, the Ramsey number $r(G,H)$ is the smallest positive integer $N$ such that any red/blue edge coloring of the complete graph $K_N$ contains either a red $G$ or a blue $H$. A book $B_n$ is a graph consisting of $n$ triangles all sharing a common edge. Recently, Conlon, Fox and Wigderson (2023) conjecture that for any $0<\alpha<1$, the random lower bound $r(B_{\lceil\alpha n\rceil},B_n)\ge (\sqrt{\alpha}+1)^2n+o(n)$ would not be tight. In other words, there exists some constant $\beta=\beta(\alpha)>0$ such that $r(B_{\lceil\alpha n\rceil},B_n)\ge (\sqrt{\alpha}+1)^2n+\beta n$ for all sufficiently large $n$. This conjecture clearly holds for every $\alpha< 1/6$ from an early result of Nikiforov and Rousseau (2005), i.e., for every $\alpha< 1/6$ and large $n$, $r(B_{\lceil\alpha n\rceil},B_n)=2n+3$. We disprove the conjecture of Conlon et al. (2023). Indeed, we show that the random lower bound is asymptotically tight for every $1/4\leq \alpha\leq 1$. Moreover, we show that for any $1/6\leq \alpha\le 1/4$ and large $n$, $r(B_{\lceil\alpha n\rceil}, B_n)\le\left(\frac 32+3\alpha\right) n+o(n)$, where the inequality is asymptotically tight when $\alpha=1/6$ or $1/4$. We also give a lower bound of $r(B_{\lceil\alpha n\rceil}, B_n)$ for $1/6\le\alpha< \frac{52-16\sqrt{3}}{121}\approx0.2007$, showing that the random lower bound is not tight, i.e., the conjecture of Conlon et al. (2023) holds in this interval.

Abstract: In this paper, we introduce a simplicial complex representation for finite non-cooperative games in the strategic form. The covering space of the simplicial game complex is introduced and we show that the covering complex is a powerful tool to find Nash Equilibrium simplices. This representation allows us to model the cost functions of a game as a weight number on a dual vertex of the strategy situation in some stars. It yields a canonical direct sum decomposition of an arbitrary game into three components, as the potential, harmonic and nonstrategic components.

Abstract: In this article, we show that the generalized tree shift operation increases the distance spectral radius, distance signless Laplacian spectral radius, and the $D_\alpha$-spectral radius of complements of trees. As a consequence of this result, we correct an ambiguity in the proofs of some of the known results.

Abstract: We consider an inverse problem for a finite graph $(X,E)$ where we are given a subset of vertices $B\subset X$ and the distances $d_{(X,E)}(b_1,b_2)$ of all vertices $b_1,b_2\in B$. The distance of points $x_1,x_2\in X$ is defined as the minimal number of edges needed to connect two vertices, so all edges have length 1. The inverse problem is a discrete version of the boundary rigidity problem in Riemannian geometry or the inverse travel time problem in geophysics. We will show that this problem has unique solution under certain conditions and develop quantum computing methods to solve it. We prove the following uniqueness result: when $(X,E)$ is a tree and $B$ is the set of leaves of the tree, the graph $(X,E)$ can be uniquely determined in the class of all graphs having a fixed number of vertices. We present a quantum computing algorithm which produces a graph $(X,E)$, or one of those, which has a given number of vertices and the required distances between vertices in $B$. To this end we develop an algorithm that takes in a qubit representation of a graph and combine it with Grover's search algorithm. The algorithm can be implemented using only $O(|X|^2)$ qubits, the same order as the number of elements in the adjacency matrix of $(X,E)$. It also has a quadratic improvement in computational cost compared to standard classical algorithms. Finally, we consider applications in theory of computation, and show that a slight modification of the above inverse problem is NP-complete: all NP-problems can be reduced to a discrete inverse problem we consider.

Abstract: For a non-bipartite finite Cayley graph, we show the non-trivial eigenvalues of its normalized adjacency matrix lie in the interval $$\left[-1+\frac{ch_{out}^2}{d},1-\frac{Ch_{out}^2}{d}\right],$$ for some absolute constant $c$ and $C$, where $h_{out}$ stands for the outer vertex boundary isoperimetric constant. This improves upon recent obtained estimates aiming at a quantitative version of an observation due to Breuillard, Green, Guralnick and Tao stating that if a non-bipartite finite Cayley graph is an expander then the non-trivial eigenvalues of its normalized adjacency matrix is not only bounded away from $1$ but also bounded away from $-1$. We achieve this by extending the work of Bobkov, Houdr\'e and Tetali on vertex isoperimetry to the setting of signed graphs. Our approach answers positively a recent open question proposed by Moorman, Ralli and Tetali.

Abstract: For each $d\leq3$, we construct a finite set $F_d$ of multigraphs such that for each graph $H$ of girth at least $5$ obtained from a multigraph $G$ by subdividing each edge at least two times, $H$ has twin-width at most $d$ if and only if $G$ has no minor in $F_d$. This answers a question of Berg\'{e}, Bonnet, and D\'{e}pr\'{e}s asking for the structure of graphs $G$ such that each long subdivision of $G$ has twin-width $4$. As a corollary, we show that the $7\times7$ grid has twin-width $4$, which answers a question of Schidler and Szeider.

Abstract: This paper generalizes a recent result by the authors concerning the sum of width-one matrices; in the present work, we consider width-one tensors of arbitrary dimensions. A tensor is said to have width 1 if, when visualized as an array, its nonzero entries lie along a path consisting of steps in the directions of the standard coordinate vectors. We prove two different formulas to compute the sum of all width-one tensors with fixed dimensions and fixed sum of (nonnegative integer) components. The first formula is obtained by converting width-one tensors into tuples of one-row semistandard Young tableaux; the second formula, which extracts coefficients from products of multiset Eulerian polynomials, is derived via Stanley-Reisner theory, making use of the EL-shelling of the order complex on the standard basis of tensors.