Abstract
Zoltán Füredi
- Department of Mathematics,
University of Illinois
- Institute of Mathematics
of the Hungarian Academy
- z-furedi@math.uiuc.edu
- Title: Covering a graph
with cuts of minimum total size.
- Abstract:
Ervin Gyõri
- Alfréd Rényi Institute
of Mathematics
- Hungarian Academy
of Sciences
- ervin@math-inst.hu
- Title: Extremal problems
concerning triangles and pentagons
- Abstract:
Gyula O.H. Katona
- Alfréd Rényi Institute
of Mathematics
- ohkatona@renyi.hu
- Title: New types of coding
problems
- Abstract:
Miklós Simonovits <Seoul on the 3rd of July, around 16.00 and continue to
Pohang on the 4th
of July. Leave on the 10th of July. (or
perhaps on 11th) >
- Mathematical Institute
of the Hungarian Academy of Sciences, Budapest,
- miki@renyi.hu
- Title: On the Erdos-Frankl-Rodl
theorem
- Abstract: Given a family
$\LL$ of graphs, let $p=p(\LL)$ be the maximal integer such
that each graph in $\LL$ has chromatic number at least
$p+1$, and
for $n\ge 1$ let $\PP(n,\LL)$ be the set of graphs with vertex set $[n]$
containing no member of $\LL$ as a subgraph. Taking
an extremal graph
$S_n$ for $\LL$ and all its subgraphs one gets $2^{\Tur np}$ $\LL$-free
graphs. Erd\H{o}s conjectured that, in some sense, this is sharp. Improving
a result of Erd\H{o}s, Frankl, and R\"odl
(1983), according
to which $$|\PP(n,\LL)|\le 2^{\Tur np +o(n^2)}$$ we prove that $$|\PP(n,\LL)|\le
2^{\tur np},$$ for some constant $\gamma=\gamma(\LL) >0$. Actually,
we extend some classical results of extremal graph theory to this case.
The extremal graph results show that the fine structure of
extremal graphs
depend primarily on the so called Decomposition family $\MM$ of $\LL$.
Here we obtain -- in some sense -- the best possible results, using
the corresponding decomposition families: $$|\PP(n,\LL)|\le n^{c\varphi(n)}\cdot
2^{\Tur np},$$ where $\varphi(n)$ depends directly on $\MM$. Our
proof is based on Szemer\'edi's Regularity Lemma and the stability
theorem of Erd\H{o}s and Simonovits.
Vera T. Sós
<Seoul on the 3rd of July, around 16.00 and continue to Pohang on the 4th
of July. Leave on the 10th of July. (or
perhaps on 11th) >
- Alfréd Rényi
Mathematical Institute, Hungarian Academy of Sciences
- sos@renyi.hu
- Title: Some remarks on the structure of
Weyl trees
- Abstract: Random-like
sequences play important role in Theoretical
Computer Science.
Such objects, often discussed in this field, are the
$\nalfa{n}$-sequences.
Luc Devroye started investigating these sequences from the point
of view of their behaviour when one inserts them one by one into
a binary search tree. The $\nalfa{n}$-sequences
can be associated
with some ``explicite'' expansions of integers (using the digits in the continued
fraction expansion of $\alpha$). These expansions can be used to
describe the behavior of the $\nalfa{n}$-sequences on a
Weyl-tree
in a finer way.
Gábor Tardos
- Alfréd Rényi
Institute of Mathematics, Hungarian Academy of Sciences
- tardos@renyi.hu
- Title: On distinct sums
and distinct distances
- Abstract:
Suh-Ryung Kim
- Kyung Hee University
- srkim@khu.ac.kr
- Title: The competition
graphs of doubly partial orders
- Abstract:
YoungMi Koh
|