Thue type problems for graphs, points, and numbers |
| |
Authors: | Jaros?aw Grytczuk |
| |
Institution: | a Theoretical Computer Science Department, Faculty of Mathematics and Computer Science, Jagiellonian University, 30-387, Kraków, Poland b Institute of Engineering, State Higher Vocational School in Nowy S?cz, 33-300 Nowy S?cz, Poland |
| |
Abstract: | A sequence S=s1s2…sn is said to be nonrepetitive if no two adjacent blocks of S are the same. A celebrated 1906 theorem of Thue asserts that there are arbitrarily long nonrepetitive sequences over the set {0,1,2}. This result is the starting point of Combinatorics on Words—a wide area with many deep results, sophisticated methods, important applications and intriguing open problems.The main purpose of this survey is to present a range of new directions relating Thue sequences more closely to Graph Theory, Combinatorial Geometry, and Number Theory. For instance, one may consider graph colorings avoiding repetitions on paths, or colorings of points in the plane avoiding repetitions on straight lines. Besides presenting a variety of new challenges we also recall some older problems of this area. |
| |
Keywords: | Primary 05C38 15A15 Secondary 05A15 15A18 |
本文献已被 ScienceDirect 等数据库收录! |
|