# 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.

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