Combinatorics (math.CO)

Abstract: We introduce torsoids, a canonical structure in matching covered graphs, corresponding to the bricks and braces of the graph. This allows a more fine-grained understanding of the structure of finite and infinite directed graphs with respect to their 1-separations.

Abstract: We find the range of the major index on the various conjugacy classes of involutions in the symmetric group $S_n$. In addition to indicating the minimum and the maximum values, we show that except for the case of involutions without fixed points, all the values in the range are attained. For the conjugacy classes of involutions without fixed points, we show that the only missing values are one more than the minimum and one less than the maximum.

Abstract: The main result of this paper states that in a rooted product of a path with rooted graphs which are disposed in a somewhat mirror-symmetric fashion, there are distinct eigenvalues supported in the end vertices of the path which are too close to each other: their difference is smaller than the square root of two in the even distance case, and smaller than one in the odd distance case. As a first application, we show that these end vertices cannot be involved in a quantum walk phenomenon known as perfect state transfer, significantly strengthening a recent result by two of the authors along with Godsil and van Bommel. For a second application, we show that there is no balanced integral tree of odd diameter bigger than three, answering a question raised by H\'{i}c and Nedela in 1998. Our main technique involves manipulating ratios of characteristic polynomials of graphs and subgraphs into continued fractions, and exploring in detail their analytic properties. We will also make use of a result due to P\'{o}lya and Szeg\"{o} about functions that preserve the Lebesgue measure, which as far as we know is a novel application to combinatorics. In the end, we connect our machinery to a recently introduced algorithm to locate eigenvalues of trees, and with our approach we show that any graph which contains two vertices separated by a unique path that is the subdivision of a bridge with at least six inner vertices cannot be integral. As a minor corollary this implies that most trees are not integral, but we believe no one thought otherwise.

Abstract: The protection number of a vertex $v$ in a tree is the length of the shortest path from $v$ to any leaf contained in the maximal subtree where $v$ is the root. In this paper, we determine the distribution of the maximum protection number of a vertex in simply generated trees, thereby refining a recent result of Devroye, Goh and Zhao. Two different cases can be observed: if the given family of trees allows vertices of outdegree $1$, then the maximum protection number is on average logarithmic in the tree size, with a discrete double-exponential limiting distribution. If no such vertices are allowed, the maximum protection number is doubly logarithmic in the tree size and concentrated on at most two values. These results are obtained by studying the singular behaviour of the generating functions of trees with bounded protection number. While a general distributional result by Prodinger and Wagner can be used in the first case, we prove a variant of that result in the second case.

Abstract: A curious generating function $S_0(x)$ for permutations of $[n]$ with exactly $n$ inversions is presented. Moreover, $(xC(x))^iS_0(x)$ is shown to be the generating function for permutations of $[n]$ with exactly $n-i$ inversions, where $C(x)$ is the generating function for the Catalan numbers.

Abstract: Given a graph $X$ with a Hamilton cycle $C$, the {\em compression factor $\kappa(X,C)$ of $C$} is the order of the largest cyclic subgroup of $\operatorname{Aut}(C)\cap\operatorname{Aut}(X)$, and the {\em Hamilton compression $\kappa(X)$ of $X$ } is the maximum of $\kappa(X,C)$ where $C$ runs over all Hamilton cycles in $X$. Generalizing the well-known open problem regarding the existence of vertex-transitive graphs without Hamilton paths/cycles, it was asked by Gregor, Merino and M\"utze in [``The Hamilton compression of highly symmetric graphs'', {\em arXiv preprint} arXiv: 2205.08126v1 (2022)] whether for every positive integer $k$ there exists infinitely many vertex-transitive graphs (Cayley graphs) with Hamilton compression equal to $k$. Since an infinite family of Cayley graphs with Hamilton compression equal to $1$ was given there, the question is completely resolved in this paper in the case of Cayley graphs with a construction of Cayley graphs of semidirect products $\mathbb{Z}_p\rtimes\mathbb{Z}_k$ where $p$ is a prime and $k \geq 2$ a divisor of $p-1$. Further, infinite families of non-Cayley vertex-transitive graphs with Hamilton compression equal to $1$ are given. All of these graphs being metacirculants, some additional results on Hamilton compression of metacirculants of specific orders are also given.