Purely periodic β-expansions in the Pisot non-unit case

It is well known that real numbers with a purely periodic decimal expansion are rationals having, when reduced, a denominator coprime with 10. The aim of this paper is to extend this result to beta-expansions with a Pisot base beta which is not necessarily a unit. We characterize real numbers having a purely periodic expansion in such a base. This characterization is given in terms of an explicit set, called a generalized Rauzy fractal, which is shown to be a graph-directed self-affine compact subset of non-zero measure which belongs to the direct product of Euclidean and p-adic spaces.     

Nonexistence of a Kruskal-Katona Type Theorem for Subword Orders

We consider the poset SO(n) of all words over an n-element alphabet ordered by the subword relation. It is known that SO(2) falls into the class of Macaulay posets, i. e. there is a theorem of Kruskal–Katona type for SO(2). As the corresponding linear ordering of the elements of SO(2) the vip-order can be chosen.Daykin introduced the V-order which generalizes the vip-order to the n2 case. He conjectured that the V-order gives a Kruskal–Katona type theorem for SO(n).We show that this conjecture fails for all n3 by explicitly giving a counterexample. Based on this, we prove that for no n3 the subword order SO(n) is a Macaulay poset.     

A theorem of Jon F. Carlson on filtrations of modules

We give an alternative proof to a theorem of Carlson [J.F. Carlson, Cohomology and induction from elementary abelian subgroups, Quart. J. Math. 51 (2000) 169-181] which states that if G is a finite group and k is a field of characteristic p, then any kG-module is a direct summand of a module which has a filtration whose sections are induced from elementary abelian p-subgroups of G. We also prove two new theorems which are closely related to Carlson’s theorem.     

The great theorem of A.A. Markoff and Jean Bernoulli sequences

A proof of Markoff’s Great Theorem on the Lagrange spectrum using continued fractions is sketched. Markoff’s periods and Jean Bernoulli sequence ¹ are used to obtain a simple algorithm for the computation of the Lagrange spectrum below 3.     

Reconstructing compositions

We consider the problem of reconstructing compositions of an integer from their subcompositions, which was raised by Raykova (albeit disguised as a question about layered permutations). We show that every composition w of n?3k+1 can be reconstructed from its set of k-deletions, i.e., the set of all compositions of n-k contained in w. As there are compositions of 3k with the same set of k-deletions, this result is best possible.     

Reducibility number

Let P be a poset in a class of posets P. A smallest positive integer r is called reducibility number of P with respect to P if there exists a non-empty subset S of P with |S|=r and P-S∈P. The reducibility numbers for the power set 2ⁿ of an n-set (n?2) with respect to the classes of distributive lattices, modular lattices and Boolean lattices are calculated. Also, it is shown that the reducibility number r of the lattice of all subgroups of a finite group G with respect to the class of all distributive lattices is 1 if and only if the order of G has at most two distinct prime divisors; further if r is a prime number then order of G is divisible by exactly three distinct primes. The class of pseudo-complemented u-posets is shown to be reducible. Deletable elements in semidistributive posets are characterized.     

Continued fractions and the Markoff tree

We give here a full account of Markoff's celebrated result on badly approximable numbers. The proofs rely exclusively on the classical theory of simple continued fractions, together with Harvey Cohn's method using words in the free group with two generators for the determination of the structure of periods of the continued fractions of Markov irrationals. Appendix A gives a short self-contained presentation of the results on continued fractions used here and Appendix B gives short proofs of some results on the still open uniqueness problem for Markoff numbers.     

On Euler numbers modulo powers of two

To determine Euler numbers modulo powers of two seems to be a difficult task. In this paper we achieve this and apply the explicit congruence to give a new proof of a classical result due to M.A. Stern.     

Simple arguments on consecutive power residues

By some extremely simple arguments, we point out the following:

(i)

If n is the least positive kth power non-residue modulo a positive integer m, then the greatest number of consecutive kth power residues mod m is smaller than m/n.

(ii)

Let OK be the ring of algebraic integers in a quadratic field with d∈{−1,−2,−3,−7,−11}. Then, for any irreducible π∈OK and positive integer k not relatively prime to , there exists a kth power non-residue ω∈OK modulo π such that .

     

Toward a language theoretic proof of the four color theorem

This paper considers the problem of showing that every pair of binary trees with the same number of leaves parses a common word under a certain simple grammar. We enumerate the common parse words for several infinite families of tree pairs and discuss several ways to reduce the problem of finding a parse word for a pair of trees to that for a smaller pair. The statement that every pair of trees has a common parse word is equivalent to the statement that every planar graph is four-colorable, so the results are a step toward a language theoretic proof of the four color theorem.     

Nonrepetitive colorings of trees

A coloring of the vertices of a graph G is nonrepetitive if no path in G forms a sequence consisting of two identical blocks. The minimum number of colors needed is the Thue chromatic number, denoted by π(G). A famous theorem of Thue asserts that π(P)=3 for any path P with at least four vertices. In this paper we study the Thue chromatic number of trees. In view of the fact that π(T) is bounded by 4 in this class we aim to describe the 4-chromatic trees. In particular, we study the 4-critical trees which are minimal with respect to this property. Though there are many trees T with π(T)=4 we show that any of them has a sufficiently large subdivision H such that π(H)=3. The proof relies on Thue sequences with additional properties involving palindromic words. We also investigate nonrepetitive edge colorings of trees. By a similar argument we prove that any tree has a subdivision which can be edge-colored by at most Δ+1 colors without repetitions on paths.     

Tackling the jump number of interval orders

Although the jump number problem for partially ordered sets in NP-complete in general, there are some special classes of posets for which polynomial time algorithms are known.Here we prove that for the class of interval orders the problem remains NP-complete. Moreover we describe another 3/2-approximation algrithm (two others have been developed already by Felsner and Syslo, respectively) by using a polynomial time subgraph packing algorithm.     

Interval stability and interval covering property in finite posets

Given a finite ranked posetP, let (P) be the maximum size of a subset ofP such that no two elements of it belong simultaneously to some interval ofP and let (P) be the minimum number of intervals covering all elements ofP. We say thatP has the strong interval stability property (resp. the strong interval covering property) if for each subposetP induced by consecutive levels ofP, i.e.,P=P _(l)...P _(u), one has (P)=max{|P _(l)|, |P _(u)|} (resp. (P)=max{|P _(l)|, |P _(u)|}).We prove these properties for several classes of posets and discuss some general facts concerning the numbers (P) and (P), e.g., NP-completeness and min-max relations.     

Homotopy type of the boolean complex of a Coxeter system

In any Coxeter group, the set of elements whose principal order ideals are boolean forms a simplicial poset under the Bruhat order. This simplicial poset defines a cell complex, called the boolean complex. In this paper it is shown that, for any Coxeter system of rank n, the boolean complex is homotopy equivalent to a wedge of (n−1)-dimensional spheres. The number of such spheres can be computed recursively from the unlabeled Coxeter graph, and defines a new graph invariant called the boolean number. Specific calculations of the boolean number are given for all finite and affine irreducible Coxeter systems, as well as for systems with graphs that are disconnected, complete, or stars. One implication of these results is that the boolean complex is contractible if and only if a generator of the Coxeter system is in the center of the group.     

Boolean Monomial Dynamical Systems

An important problem in the theory of finite dynamical systems is to link the structure of a system with its dynamics. This paper contains such a link for a family of nonlinear systems over the field with two elements. For systems that can be described by monomials (including Boolean AND systems), one can obtain information about the limit cycle structure from the structure of the monomials. In particular, the paper contains a sufficient condition for a monomial system to have only fixed points as limit cycles. This condition depends on the cycle structure of the dependency graph of the system and can be verified in polynomial time.Received February 2, 2004