Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLyndon word decompositions and pseudo orbits on q-nary graphs
65
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A foundational result in the theory of Lyndon words (words that are strictly earlier in lexicographic order than their cyclic permutations) is the Chen-Fox-Lyndon theorem which states that every word has a unique non-increasing decomposition into Lyndon words. This article extends this factorization theorem, obtaining the proportion of these decompositions that are strictly decreasing. This result is then used to count primitive pseudo orbits (sets of primitive periodic orbits) on q-nary graphs. As an application we obtain a diagonal approximation to the variance of the characteristic polynomial coefficients q-nary quantum graphs.
rate research
Read More
According to a well-know theorem by Sturm, a vibrating string is divided into exactly N nodal intervals by zeros of its N-th eigenfunction. Courant showed that one half of Sturms theorem for the strings applies to the theory of membranes: N-th eigenfunction cannot have more than N domains. He also gave an example of a eigenfunction high in the spectrum with a minimal number of nodal domains, thus excluding the existence of a non-trivial lower bound. An analogue of Sturms result for discretizations of the interval was discussed by Gantmacher and Krein. The discretization of an interval is a graph of a simple form, a chain-graph. But what can be said about more complicated graphs? It has been known since the early 90s that the nodal count for a generic eigenfunction of the Schrodinger operator on quantum trees (where each edge is identified with an interval of the real line and some matching conditions are enforced on the vertices) is exact too: zeros of the N-th eigenfunction divide the tree into exactly N subtrees. We discuss two extensions of this result in two directions. One deals with the same continuous Schrodinger operator but on general graphs (i.e. non-trees) and another deals with discrete Schrodinger operator on combinatorial graphs (both trees and non-trees). The result that we derive applies to both types of graphs: the number of nodal domains of the N-th eigenfunction is bounded below by N-L, where L is the number of links that distinguish the graph from a tree (defined as the dimension of the cycle space or the rank of the fundamental group of the graph). We also show that if it the genericity condition is dropped, the nodal count can fall arbitrarily far below the number of the corresponding eigenfunction.
In this note, we present a natural proof of a recent and surprising result of Gregory Berkolaiko (arXiv 1110.5373) interpreting the Courant nodal defect of a Schrodinger operator on a finite graph as a Morse index associated to the deformations of the operator by switching on a magnetic field. This proof is inspired by a nice paper of Miroslav Fiedler published in 1975.
A generalized lexicographical order on infinite words is defined by choosing for each position a total order on the alphabet. This allows to define generalized Lyndon words. Every word in the free monoid can be factorized in a unique way as a nonincreasing factorization of generalized Lyndon words. We give new characterizations of the first and the last factor in this factorization as well as new characterization of generalized Lyndon words. We also give more specific results on two special cases: the classical one and the one arising from the alternating lexicographical order.
We count the numbers of primitive periodic orbits on families of 4-regular directed circulant graphs with $n$ vertices. The relevant counting techniques are then extended to count the numbers of primitive pseudo orbits (sets of distinct primitive periodic orbits) up to length $n$ that lack self-intersections, or that never intersect at more than a single vertex at a time repeated exactly twice for each self-intersection (2-encounters of length zero), for two particular families of graphs. We then regard these two families of graphs as families of quantum graphs and use the counting results to compute the variance of the coefficients of the quantum graphs characteristic polynomial.
In this paper we compare two finite words $u$ and $v$ by the lexicographical order of the infinite words $u^omega$ and $v^omega$. Informally, we say that we compare $u$ and $v$ by the infinite order. We show several properties of Lyndon words expressed using this infinite order. The innovative aspect of this approach is that it allows to take into account also non trivial conditions on the prefixes of a word, instead that only on the suffixes. In particular, we derive a result of Ufnarovskij [V. Ufnarovskij, Combinatorial and asymptotic methods in algebra, 1995] that characterizes a Lyndon word as a word which is greater, with respect to the infinite order, than all its prefixes. Motivated by this result, we introduce the prefix standard permutation of a Lyndon word and the corresponding (left) Cartesian tree. We prove that the left Cartesian tree is equal to the left Lyndon tree, defined by the left standard factorization of Viennot [G. Viennot, Alg`ebres de Lie libres et monoides libres, 1978]. This result is dual with respect to a theorem of Hohlweg and Reutenauer [C. Hohlweg and C. Reutenauer, Lyndon words, permutations and trees, 2003].
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
