Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRegular Interval Exchange Transformations over a Quadratic Field
151
0
0.0
(
0
)
Added by
Francesco Dolce
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Authors
Francesco Dolce
Ask ChatGPT about the research
No Arabic abstract
We describe a generalization of a result of Boshernitzan and Carroll: an extension of Lagranges Theorem on continued fraction expansion of quadratic irrationals to interval exchange transformations. In order to do this, we use a two-sided version of the Rauzy induction. In particular, we show that starting from an interval exchange transforma- tion whose lengths are defined over a quadratic field and applying the two-sided Rauzy induction, one can obtain only a finite number of new transformations up to homothety.
rate research
Read More
The Arnoux-Rauzy systems are defined in cite{ar}, both as symbolic systems on three letters and exchanges of six intervals on the circle. In connection with a conjecture of S.P. Novikov, we investigate the dynamical properties of the interval exchanges, and precise their relation with the symbolic systems, which was known only to be a semi-conjugacy; in order to do this, we define a new system which is an exchange of nine intervals on the line (it was described in cite{abb} for a particular case). Our main result is that the semi-conjugacy determines a measure-theoretic isomorphism (between the three systems) under a diophantine (sufficient) condition, which is satisfied by almost all Arnoux-Rauzy systems for a suitable measure; but, under another condition, the interval exchanges are not uniquely ergodic and the isomorphism does not hold for all invariant measures; finally, we give conditions for these interval exchanges to be weakly mixing.
A lower bound is obtained for the greatest possible number of colors in an interval colourings of some regular graphs.
A matching $M$ in a graph $G$ is said to be uniquely restricted if there is no other matching in $G$ that matches the same set of vertices as $M$. We describe a polynomial-time algorithm to compute a maximum cardinality uniquely restricted matching in an interval graph, thereby answering a question of Golumbic et al. (Uniquely restricted matchings, M. C. Golumbic, T. Hirst and M. Lewenstein, Algorithmica, 31:139--154, 2001). Our algorithm actually solves the more general problem of computing a maximum cardinality strong independent set in an interval nest digraph, which may be of independent interest. Further, we give linear-time algorithms for computing maximum cardinality uniquely restricted matchings in proper interval graphs and bipartite permutation graphs.
An edge-coloring of a graph $G$ with colors $1,2,ldots,t$ is an interval $t$-coloring if all colors are used, and the colors of edges incident to each vertex of $G$ are distinct and form an interval of integers. A graph $G$ is interval colorable if it has an interval $t$-coloring for some positive integer $t$. For an interval colorable graph $G$, $W(G)$ denotes the greatest value of $t$ for which $G$ has an interval $t$-coloring. It is known that the complete graph is interval colorable if and only if the number of its vertices is even. However, the exact value of $W(K_{2n})$ is known only for $n leq 4$. The second author showed that if $n = p2^q$, where $p$ is odd and $q$ is nonnegative, then $W(K_{2n}) geq 4n-2-p-q$. Later, he conjectured that if $n in mathbb{N}$, then $W(K_{2n}) = 4n - 2 - leftlfloorlog_2{n}rightrfloor - left | n_2 right |$, where $left | n_2 right |$ is the number of $1$s in the binary representation of $n$. In this paper we introduce a new technique to construct interval colorings of complete graphs based on their 1-factorizations, which is used to disprove the conjecture, improve lower and upper bounds on $W(K_{2n})$ and determine its exact values for $n leq 12$.
This note resolves an open problem asked by Bezrukov in the open problem session of IWOCA 2014. It shows an equivalence between regular graphs and graphs for which a sequence of invariants presents some symmetric property. We extend this result to a few other sequences.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
