Skip to main content
main-content

Über dieses Buch

The problem of uniform distribution of sequences initiated by Hardy, Little­ wood and Weyl in the 1910's has now become an important part of number theory. This is also true, in relation to combinatorics, of what is called Ramsey­ theory, a theory of about the same age going back to Schur. Both concern the distribution of sequences of elements in certain collection of subsets. But it was not known until quite recently that the two are closely interweaving bear­ ing fruits for both. At the same time other fields of mathematics, such as ergodic theory, geometry, information theory, algorithm theory etc. have also joined in. (See the survey articles: V. T. S6s: Irregularities of partitions, Lec­ ture Notes Series 82, London Math. Soc. , Surveys in Combinatorics, 1983, or J. Beck: Irregularities of distributions and combinatorics, Lecture Notes Series 103, London Math. Soc. , Surveys in Combinatorics, 1985. ) The meeting held at Fertod, Hungary from the 7th to 11th of July, 1986 was to emphasize this development by bringing together a few people working on different aspects of this circle of problems. Although combinatorics formed the biggest contingent (see papers 2, 3, 6, 7, 13) some number theoretic and analytic aspects (see papers 4, 10, 11, 14) generalization of both (5, 8, 9, 12) as well as irregularities of distribution in the geometric theory of numbers (1), the most important instrument in bringing about the above combination of ideas are also represented.

Inhaltsverzeichnis

Frontmatter

1.. Irregularities of Point Distribution Relative to Convex Polygons

Abstract
Let U 2 = [0, l]2 denote the unit square in R 2. Suppose that P is a distribution of N points in U 2. For any Lebesgue measurable set A in U 2, denote by Z[P; A] the number of points P in A. We are interested in the discrepancy function
$$<Emphasis Type="Italic">D[P;A]=Z[P;A]-N\mu (A)</Emphasis>$$
where μ denotes, as usual, the 2-dimensional Lebesgue measure.
J. Beck, W. W. L. Chen

2.. Balancing Matrices with Line Shifts II

Abstract
Let an arbitrary matrix A = (a ij), 1 ≤ iK, 1 ≤ jL be given with all |a ij| ≤ 1. By a row shift we mean the act of replacing, for a particular i, all coefficients a ij in the i-th row by their negatives (-a ij). A column shift is defined similarly. A line shift denotes either a row or a column shift. Consider the following solitaire game. The player applies a succession of line shifts to A. His object is to make the absolute value of the sum of all the coefficients of A (which we shall denote by |A|) as small as possible. We shall show (answering a question of J. Komlós) that the player can always make |A| ≤ c 0 where c 0 is an absolute constant — i.e., independent of K, L, and the initial matrix. We make no attempt to find the minimal possible c 0.
J. Beck, J. Spencer

3.. A Few Remarks on Orientation of Graphs and Ramsey Theory

Abstract
Let D denote a class of digraph such that every induced digraph in D is in D again. Then either D contains all acyclic digraphs or almost no graph has an orientation in D. Proofs and variations on this theme are discussed. Some open problems in Ramsey theory are raised.
M. Cochand, P. Duchet

4.. On a Conjecture of Roth and Some Related Problems I

Abstract
Let N denote the set of positive integers and put \({\text{[1,}}{\rm N}{\text{] = \{ 1,}}...{\text{,}}{\rm N}{\text{\} }}\). We use |S| to denote the cardinality of the finite set S. If S is a given set and \(\mathcal A_1,...,\mathcal A_k\) are subsets of S with
$$S={\cup}_{i=1}^k\mathcal{A}_i,\ \mathcal{A}_i\cap\mathcal{A}_i=\Theta for\ \i\neq j,$$
then \(\{\mathcal A_1,...,\mathcal A_k\}\) will be called a k-partition (or k-colouring) of S, and the subsets \(\mathcal A_1,...,\mathcal A_k\) will be referred to as classes. Let \(f:\mathcal N^t\rightarrow \mathcal N\) be a given function. If
$$n = f(a_1,...,a_t)$$
with \(a_1,..., a_t\) belonging to the same class, then this will be called a monochromatic representation of n in the form (1)
P. Erdős, A. Sárközy, V. T. Sós

5.. Discrepancy of Sequences in Discrete Spaces

Abstract
In this article some combinatorial properties of 0.1-strings are established. A special sequence with small discrepancy ( with respect to increasing block length ) is constructed by means of De Bruijn graph. Applying a general result of W. Philipp a central limit theorem is derived for the local discrepancy.
Ph. Flajolet, P. Kirschenhofer, R. F. Tichy

6.. On the Distribution of Monochromatic Configurations

Abstract
Much of Ramsey theory is concerned with the study of structure which is preserved under finite partitions, (eg., see [8], [9], [12]). Some of the earliest results in the field were the following.
P. Frankl, R. L. Graham, V. Rödl

7.. Covering Complete Graphs by Monochromatic Paths

Abstract
A theorem of R. Radó (see in [2]) says that if the edges of the countably infinite complete graph K are colored with r colors then the vertices of K can be covered by at most r (finite or one-way infinite) vertex-disjoint monochromatic paths. Edge-coloring theorems are usually extended from finite to infinite, however, in the case of Radó’s theorem it seems natural to look for finite versions.
A. Gyárfás

8.. Canonical Partition Behaviour of Cantor Spaces

Abstract
Using topological concepts A. Blass [1] proved an uncountable version of Ramsey’s theorem. Here we prove a canonical version of this result.
Hanno Lefmann

9.. Extremal Problems for Discrepancy

Abstract
We determine the maximum number of edges in a hypergraph with a given number of vertices and given hereditary discrepancy. We derive bounds on the maximum number of rows in an integral matrix with a given number of columns and with given hereditary discrepancy. The main tool is a geometric interpretation of discrepancy and a relation between the volumes of polar convex bodies.
L. Lovász, K. Vesztergombi

10.. Spectral Studies of Automata

Abstract
It is reasonable to argue that the simplest sequences are the periodic sequences. There are at least two ways to make this truism meaningful. The n-th term of a periodic sequence can be determined once we know the period and the integer n and this amounts to approximately log2 n bits of information for large n. Also, the number of different words of length n in a periodic sequence is bounded. Periodic sequences minimise both of these characteristics. At the other end of the scale are the random sequences. We can take a random sequence to be one for which the most efficient way to find the n-th term is to make a list of the first n terms, requiring at least n bits of information. This implies another essential aspect of randomness that, for every n, the words of length n in the sequence are equidistributed.
J. H. Loxton

11.. A Diophantine Problem

Abstract
Let \(v = \left( {{v_n}} \right), n \geqslant 0 \), be an infinite sequence (mod 1). Let p ∈ [1,+∞]. The symbol |..| denotes the ”norm” on the torus R/Z, i.e the distance to the nearest integer. We define the “norm” of the sequence v
$$\left\| v \right\|p = \mathop {\lim \sup }\limits_{N \to \infty } {\left( {\frac{1}{N}\sum\limits_{n - 0}^{N = 1} | {v_n}{|^p}} \right)^{1/p}}for{\text{ }}1 \leqslant p < \infty , $$
and
$$\left\| v \right\| = {\left\| v \right\|_\infty } = \mathop {\lim \sup }\limits_{N \to \infty } |{v_N}| $$
.
M. Mendes France

12.. A Note on Boolean Dimension of Posets

Abstract
We present a universal upper bound for the boolean dimension of posets. We prove that this bound is asymptotically best possible.
J. Nešetřil, P. Pudlák

13.. Intersection Properties and Extremal Problems for Set Systems

Abstract
A general inequality is proved for collections of finite sets satisfying a certain type of intersection properties. From this result, Ramsey-type theorems are deduced. For example, if every vertex is incident to edges of at most k colors in an edge-coloring of a complete graph on 2k +1 vertices, then there is a monochromatic odd cycle.
Zs. Tuza

14.. On an Imbalance Problem in the Theory of Point Distribution

Abstract
We consider the following problem: Let f be a 2π-periodic integrable function satisfying \(\int_{0}^{2\pi} f(x)dx=0\). Given an N-tuple of points \({\omega _N} = \left\{ {{x_1},{x_2},...,{x_N}} \right\}\) on [0, 2π), denote by Pos(f,ωN) the set of all x∈[0,2π) for which \(\sum\ _{j=1}^{N}f(x-x_j)\geq 0\) is true. Let \(\beta _N(f)=inf\ m(Pos(f,\omega _N))\) where m denotes Lebesgue measure on [0,2π) and the infimum is taken over all N-tuples ωN.
We give lower and upper bounds for βN (f) in three special cases, together with some results of a more general type.
G. Wagner

15.. Problems

Abstract
Existence proofs by random selection are very popular in Combinatorics, Information Theory, Complexity Theory etc. We wonder whether they can be replaced by deterministic procedures, which have certain equidistribution properties. Our ideas are not yet precise. We came across the following number theoretical problem, which does not seem to fit into the classical theory of equidistribution.
Gábor Halász, Vera T. Sós

Backmatter

Weitere Informationen