Vera T.Sos

Mathematical Institute of the Hungarian Academy of Sciences, Budapest, Hungary


DIMACS Center
4th Floor Seminar Room 431, CoRE Building
Rutgers University
Friday, April 11, 1997 at 11:30 am (Refreshments at 11:15 a.m.)

"Order, disorder and what is between"

An important question of mathematics and computer science is, how random-like objects can be generated in nonrandom ways and when an individual object could be considered as random or ``random-like'' and in which sense.

Considering different structures (graphs, numbers, permutations, etc.) this questions has different aspects and we may have several nonequivalent answers. In the talk we shall concentrate on two topics.

(a) Quasi-random graphs Thomason and Chung - Graham - Wilson gave a class of graph properties, all possessed by random graphs and at the same time equivalent to each other. With Simonovits we proved, that this class (quasi-random graphs) can be characterized also in the Szemeredi-partition of graphs. Using this approach we proceed, that some properties, which do not imply quasi-randomness on their own, do imply it if we consider the corresponding hereditarily extended properties. (Large subgraphs of random-like graphs must also be random-like.)

(b) Quasi-periodic sequences; the distribution of ({nx}), ([nx]) sequences, for x irrational. ({} denotes "fractional part", [] denotes "integer part".) We remark, that ({nx}), ([nx]) sequences can be considered as the one-dimensional analog of Penrose-tilings (related to the atomic structures of quasi-crystals, which are ``between'' crystal and amorphous atomic structures.)

The results may contribute to study the problem: how to create a scale between periodic and random sequences, between non-random and random graphs, etc.


Index

dimacs-www@dimacs.rutgers.edu
Document last modified on April 8, 1997