Rudolph Ahlswede, Bielefeld

	R.Ahlswede, " Katona's Intersection theorem: 4 new proofs "
	Authors: R.Ahlswede and L.Khachatrian.

J\'ozsef Beck, Rutgers

	talk:  RAMSEY GAMES AND THE SECOND MOMENT METHOD
	
	abstract: We study the fair Maker-Breaker graph Ramsey game
	$MB(n;q)$. The board is $K_n,$ the players alternately occupy one edge
	a move, and Maker wants a clique $K_q$ of his own. We show that Maker
	has a winning strategy in $MB(n;q)$ if $q=2\log_2 n-2\log_2\log_2
	n+O(1),$ which is {\it exactly} the highly concentrated clique number
	of the random graph on $n$ vertices with edge-probability 1/2. Due to
	an old theorem of Erd\H os and Selfridge this is best possible apart
	from an additive constant less than 3.

	Another way to split $K_n$ is the ``Picker-Chooser'', and also the
	``Chooser-Picker'' version. Again the board is the complete graph
	$K_n$.  In each round of the play Picker picks two previously
	unselected edges of $K_n,$ Chooser chooses one of them, and the other
	one goes back to Picker. In the first variant Chooser wins if he can
	occupy all the ${q\choose 2}$ edges of some complete subgraph $K_q$ of
	$K_n$; otherwise Picker wins.  This is the {\it Chooser-Picker} game.

	The second variant is where Picker wants a $K_q.$ This is called the
	{\it Picker-Chooser} game.

	One can also consider the three {\it avoidance versions} in which the
	{\it builder} player becomes the {\it anti-builder}, and {\it loses}
	by completing a a $K_q.$

	The game-theoretic threshold of each game is exactly the same $2\log_2
	n-2\log_2\log_2 n+O(1).$

Christian Bey, Rostock

	no talk

Sergei Bezrukov, ?

	talk: The Kruskal-Katona theorem: 35 years later
        abstract: We present a short survey on the shadow-minimization problem
	in posets, discuss some new approaches and research directions and
	give some applications of this problem. The applications include
	isoperimetric problems on graphs, extremal poset problems, network
	reliability, combinatorial topology and others.

Joachim Biskup, Hildesheim

	talk: Models for controlled query evaluation - lying versus refusal
	abstract: A shared information system is expected to comply with the
	following potentially conflicting requirements. It should provide
	useful answers to arbitrary queries, while on the other hand it should
	preserve certain secrets according to a security policy.  We study two
	approaches to meet these requirements, namely refusal of statements
	and lying.  The investigation is performed using a logical framework,
	both with respect to the information system and the preservation of
	secrets, using two different models for security policies.

	Under the model of "unknown secrecies", the assessment shows that
	refusal is better than lying. In particular, while preserving the same
	secrets refusal can provide more useful answers.

	Under the model of of "known potential secrets", the comparison proves
	that, in general, lying and refusal are incomparable in many respects,
	but, under fairly natural assumptions, they lead to surprisingly
	similar behaviors and convey exactly the same information to the user.

Thomas A Bohman

       talk: On a list coloring conjecture of Reed

       Abstract: Reed conjectured that if each vertex in a graph G has a list
       of available colors such that the size of each list exceeds the maximum
       vertex-color-degree then there exists a proper coloring of G from the
       lists.  In this talk we present a counterexample to Reed's conjecture.

Endre Boros, Rutgers

	talk:  Polymatroid separators of hypergraphs
      authors:  Endre Boros, K. Elbassioni, V. Gurvich, L. Khachiyan (Rutgers,
      New Jersey, USA), K. Makino (University of Osaka, Japan)

	abstract: We consider the family A(t) of all minimal subsets S of a
	finite base set V, for which f(S) >= t, where f is a monotone
	setfunction, and t is a fixed threshold. Analogously, we shall
	consider the family B(t) of those maximal subsets for which f(S) <
	t. It is easy to see that members of B(t) are exactly the maximal
	independent sets of A(t) (i.e. the complements of minimal transversals
	of A(t)), and vice versa. In general, if a hypergraph H and the family
	I=I(H) of its maximal independent sets are such that H=A(t) and I=B(t)
	for some integral valued monotone setfunction f and threshold t, then
	we say that (f,t) is a separator for H. Finally, such a separator is
	called polymatroid, if f is a nonnegative, monotone, submodular
	setfunction.

	In the flavor if extremal combinatorics, we shall present inequalities
	between the cardinalities of A(t) and B(t), for various types of
	setfunctions f.  We show that every Sperner hypergraph has a
	polymatroid separator, and that for such a separator

                        t >= |B(t)|^{O(1/log |A(t)|)}

	must hold. We shall also show that this inequality allows for the
	incrementally efficient generation of the hypergraph H, represented by
	the separator (f,t).  Such generation problems have numerous
	applications, in a multitude of areas, including data mining (finding
	all maximal frequent, minimal infrequent sets), text mining (finding
	the best linear query in vector space models), machine learning
	(finding the best rules or patterns), hypergraph dualization
	(generating all minimal transversals), reliability theory (generating
	all minimal working and/or maximal failing states), integer
	programming (generating all minimal feasible solutions), stochastic
	programming (constructing deterministic equivalents to certain
	stochastic models), etc.

Ernesto Burattini, CNR, Naples

	no talk

Beifang Chen, Memphis

	no talk

Jonathan Cutler, Memphis
	
	no talk
	
Joe Csima, McMaster Uni, Canada

	Latin Squares, Timetables and Hypergraphs

Michel Deza, CNRS

	talk: Clusters of cycles

Stefan Dodunekov, Sofia (es Bielefeld)

	talk?

Pierre Duchet

       talk: Menger's via hypergraphs : a short proof of the Hoffman '74
       theorem on path systems

Konrad Engel, Rostock

	TALK: Katona theorems - Generalizations and an application by Konrad
	Engel, Rudolf Ahlswede, Christian Bey, Gyula Katona, Levon
	Khachatrian, and Uwe Leck 

	ABSTRACT: Let $[n]:=\{1,\ldots,n\}$ and let $2^{[n]}$ be the power set
	of $[n]$.  Moreover, let
	\[
	{[n] \choose \le k} := \{X \subseteq [n]: |X| \le k\}.
	\]

	A family ${\cal F} \subseteq 2^{[n]}$ is called {\it
	$t$--intersecting} if $|X \cap Y| \ge t$ for all $X,Y \in {\cal
	F}$. Let $M(n,t)$ and $M_{\le k}(n,t)$ be the maximum size of a
	$t$--intersecting family in $2^{[n]}$ and ${[n] \choose \le k}$,
	respectively. Let \begin{eqnarray*} S(n,t,r)&:=&\{X \in 2^{[n]}: |X
	\cap [t+2r]| \ge t+r\},\\ S_{\le k}(n,t,r)&:=&S(n,t,r) \cap {[n]
	\choose \le k}.  \end{eqnarray*} A celebrated result of Katona is the
	following: \[ M(n,t)=|S(n,t,\lfloor(n-t)/2\rfloor)|.  \] 

	In this talk
	we discuss the questions: For which numbers $k$ do we have \[ M_{\le
	k}(n,t)=|S_{\le k}(n,t,\lfloor(n-t)/2\rfloor)|?  \] Is it true that
	for $k < (n+t)/2$ \[ M_{\le k}(n,t)=\max\{|S_{\le k}(n,t,r)|: r =
	0,\dots,\lfloor(n-t)/2\rfloor\}?
	\]

	Results on the maximum size of $t$--intersecting families ${\cal F}$
	which have the additional property $|X \cup Y|\le n-s$ for all $X,Y
	\in {\cal F}$ will be presented.

	A family ${\cal F} \subseteq 2^{[n]}$ is said to be a {\it Sperner
	family} if $X\not\subset Y$ for all $X,Y \in {\cal F}$.  Kleitman and
	Milner proved that, for $k \le n/2$, the average size of the sets in a
	Sperner family with at least ${n \choose k}$ members is at least
	$k$. Using the well--known Erd\H{o}s--Frankl--Katona characterization
	of the extreme points of the profile--polytop of 1--intersecting
	Sperner families we show:

	Let $k \le (n+2)/2 - \sqrt{n}/2.$ If ${\cal F} \subseteq 2^{[n]}$ is a
	1--intersecting Sperner family with at least ${n-1 \choose k-1}$
	members, then the average size of sets in ${\cal F}$ is at least
	$k$. This statement fails if $n/2 \ge k > n/2-\sqrt{8n+1}/8 + 9/8$.

P\'eter L. Erd\H os, R\'enyi Institute

	no talk

P\'eter Frankl, Waseda University, Tokyo (on leave from CNRS Paris)

	talk: tba

Zolt'an F\"uredi, R\'enyi Institute, Budapest

	talk: tba

Jerry Griggs, Columbia, SC

	 talk: Problems on Chain Partitions

	abstract: We intend to survey the current state of progress of efforts
	to prove conjectures, some now 25 years old, concerning the existence
	of partitions of the Boolean lattice--or more general classes of
	ranked posets--into chains with specified sizes or ranks.  The talk is
	dedicated to Gyula O.H. Katona, who first got me interested in the
	subject and who always encourages my research in this area.

Vince Grolmusz, E\"otv\"os University, Budapest

	 TALK:  Co-orthogonal codes
	 AUTHORS: Vince Grolmusz

	Abstract: We define, construct and sketch possible applications of a
	new class of non-linear codes: co-orthogonal codes.  The advantage of
	these codes are twofold: first, it is easy to decide whether two
	codewords form a unique pair (this can be used in decoding information
	or identifying users of some not-publicly-available or non-free
	service on the Internet or elsewhere), and the identification process
	of the unique pair can be distributed between entities, who perform
	easy tasks, and only the information, gathered from all of them would
	lead to the result of the identifying process: the entities, taking
	part in the process will not have enough information to decide or just
	to conjecture the outcome of the identification process.

	The identification is done by the following procedure: two sequences,
	$a=(a_1,a_2,\ldots,a_n)$ and $b=(b_1,b_2,\ldots,b_n)$ forms a {\em
	pair}, say, modulo 6, if 6 is a divisor of the sum
	$$\sum_{i=1}^na_ib_i.$$ If, for every $a$ there is exactly one $b$
	which forms a pair with $a$ (and this fact can be decided easily),
	then, for example, keeping $b$ secret would identify $a$. Our main
	result is that these codes (co-orthogonal codes) contain much more
	code-words, than the orthogonal codes, where the pairs are identified
	by the fact that in the sum above 6 is not a divisor of the sum. We
	also note, that taking 6 (or a non-prime power other small integer) is
	an important point here: we will get more code-words than in the case
	of primes!


Andr\'as Gy\'arf\'as, SZTAKI, Budapest

	 talk: Transitive edge colorings of graphs
	 abstract: A.Sali proposed a conjecture (1996) on hypergraphs and
	 proved that it would imply that the dimension of $n$-element lattices
	 is $o(n)$ as suggested by F\"uredi and Kahn (1988) as a trial case
	 for a conjectured sharper bound.

	 We prove Sali's conjecture in a stronger form.  The proof relies on
	 concepts and results which seem to have independent interest. One of
	 them is an extension of the induced matching lemma of Ruzsa and
	 Szemer\e'di to transitively colored graphs.

Hans-Dietrich Gronau, Rostock

	talk: Orthogonal covers of graphs (Gyusziszekcioban szeretne elmodnani)

Kati Gyarmati, E\"otv\"os University, Budapest

	no talk

Ervin Gy\H ori, R\'enyi Institute, Budapest
      talk: tba

Andr\'as Hajnal, Rutgers

	talk: tba

Jochen Harant, Ilmenau

	no talk

Sven Hartman, Rostock
     TALK: Minimum matrix representations under cardinality constraints
     Abstract: apr. 30-i leveleben

	A database relation $R$ over an attribute set $\Omega$ may be
	considered as a matrix, whose columns correspond to the attributes in
	$\Omega$. Every row in the matrix specifies a tuple $\pi$ in the
	relation $R$. A subset $K\subseteq\Omega$ is a key if the restrictions
	$\pi[K]$ are mutually distinct for all $\pi\in R$.  For every Sperner
	family $S$ over $\Omega$ there exists a relation whose set of minimal
	keys equals $S$, called an Armstrong relation for $S$.

	A natural question to be asked is the following: Given a Sperner
	family $S$, what is the minimum size of an Armstrong relation for $S$?
	For $S=\binom{\Omega}{3}$, this question leads to the investigation of
	orthogonal double covers (ODCs) of complete graphs.

	Given some entry $i$ in the matrix, its degree $\deg(C,i)$ counts how
	often this entry occurs in the column $C\in\Omega$.  Cardinality
	constraints impose restrictions on these degrees: Given a set
	$M\subseteq \mathbb N$, all degrees $\deg(C,i)$ should belong to the
	set $M$. Constraints of this kind frequently appear in database design
	and knowledge representation.

	Demetrovics, F\"uredi and Katona asked for the minimum size of an
	Armstrong relation for $\binom{\Omega}{3}$ where all degrees
	$\deg(C,i)$ lie in $M=\{1,3\}$. Solutions were given by Bennett and
	Wu, and by Gronau and Mullin. We continue the investigation of
	Armstrong relations under cardinality constraints and present results
	for the degree sets $M=\{1,k\}$ and $M=\{3\}$.

Penny Haxell, Waterloo

      talk: Independent transversals

      Abstract:Let $G$ be graph whose vertex set is partitioned into $r$
      parts. An {\it independent transversal} of $G$ is an independent set of
      vertices of $G$ that contains exactly one vertex from each part. We
      discuss conditions on $G$ that guarantee the existence of an independent
      transversal, and give some applications to other problems.

A.J.W. Hilton, Reading 

	talk: Amalgamations of connected k-factorizations
       by A.J.W.Hilton,M.Johnson,C.A.Rodger and E.Wantland
	Abstract. Necessary and sufficient conditions are found for a graph
	with exactly one amalgamated vertex to be the amalgamation of a
	k-factorization of K(kn+1) in which each factor is connected. From
	this result, necessary and sufficient conditions for a given edge
	coloured K(r) to be embedded in a connected k-factorization of K(kn+1)
	are deduced.
 
Ron Holzman, Haifa

	Title: Linear vs. hereditary discrepancy
	Authors: Tom Bohman and Ron Holzman
	
	Abstract: The linear discrepancy of a hypergraph H is a worst-case
	measure of the cumulative error introduced on an edge of H by
	integer-rounding of real numbers assigned to the vertices of H. The
	hereditary discrepancy of H is the maximum, over all restrictions of
	H, of the standard, two-coloring discrepancy. Lovasz, Spencer and
	Vesztergombi (1986) proved that the linear discrepancy is bounded
	above by the hereditary discrepancy, and conjectured a sharper bound
	involving also the number of vertices.

	We prove the conjecture for hypergraphs of hereditary discrepancy
	1. This includes as special cases interval hypergraphs, for which the
	conjecture was verified by Lovasz, and initial-segment hypergraphs
	corresponding to two permutations, for which the conjecture was proved
	by Knuth (1995) and independently by Ossowski.

	For hypergraphs of higher hereditary discrepancy, we have some partial
	results and we propose a sharpening of the conjecture.

Wilfried Imrich, Leoben

	 Title: Fast recognition of partial cubes

	 Bo\v{s}tjan Bre\v{s}ar, University of Maribor

	 Wilfried Imrich, Montanuniversit\"at Leoben

	 Sandi Klav\v{z}ar, University of Maribor

	 Astract: Isometric subgraphs of hypercubes, or partial cubes as they
	 are also called, are a rich class of graphs that include median
	 graphs, subdivision graphs of complete graphs, and classes of graphs
	 arising in mathematical chemistry and biology. In general one can
	 recognize whether a graph on $n$ vertices and $m$ edges is a partial
	 cube in $O(mn)$ steps, faster recognition algorithms are known for
	 median graphs and acyclic cubical complexes.

	 With the aid of structural decomposition theorems we exhibit new
	 classes of partial cubes that can be recognized in $O(m\log n)$
	 steps.

Jeong-Hyun Kang, Urbana

	no talk

Gyula K\'arolyi, E\"otv\"os University, Budapest

	no talk

Michal Karonski


	talk: On graph irregularity strength

	abstract: An assignment of positive integer weights to the edges of a
	simple graph $G$ is called irregular if the weighted degrees of the
	vertices are all different.  The irregularity strength, $s(G)$, is the
	maximal weight, minimized over all irregular assignments, and is set
	to $\infty$ if no such assignment is possible.  We show, that
	$s(G)\leq c_1 n/\d$, for graphs with maximum degree $\D\le n^{1/2}$,
	and $s(G)\leq c_2 (\log n) n/\d$, for graphs with $\D >n^{1/2}$, where
	$c_1$ and $c_2$ are explicit constants.  To prove the result, we are
	using a combination of deterministic and probabilistic techniques.\\
	This is joint work with Alan Frieze, Ron Gould and Florian Pfender.

Gyula Y. Katona, Budapest University of Technology and Economics

	TALK: Hamiltonian Chains in Hypergraphs
	with P. Frankl

	Let ${\cal H}$ be a $r$--uniform hypergraph on the vertex set $V({\cal
	H})=\{v_1, v_2,\ldots,v_n\}$ where $n>r$.  A cyclic ordering $(v_1,
	v_2,\ldots , v_n)$ of the vertex set is called a {\em hamiltonian
	chain} iff for every $1\leq i\leq n$ there exists an edge $E_j$ of
	${\cal H}$ such that $\{v_i, v_{i+1},\ldots, v_{i+r-1}\}=E_j$.

	An $r$-uniform hypergraph is {\it $k$-edge-hamiltonian} iff it still
	contains a hamiltonian chain after deleting any $k$ edges of the
	hypergraph. What is the minimum number of edges of such a hypergraph?
	We give lower and upper bounds for this question for several values of
	$r$ and $k$.


Zsolt Katona, E\"otv\"os University, Budapest

	TALK: Intersecting families of sets, no $l$ containing two common
	elements

	abstract: Let $H$ denote the set $\{f_1,f_2,...,f_n\}$, $2^{[n]}$ the
	collection of all subsets of $H$ and $\F\subseteq 2^{[n]}$ be a
	family. The maximum of $|\F|$ is studied if any $k$ subsets have a
	non-empty intersection and the intersection of any $l$ distinct
	subsets ($1\leq k<l$) is empty. This problem is reduced to a covering
	problem.

	If we have the conditions that any two subsets have a non-empty
	intersection and the intersection of any $l$ distinct subsets contains
	no two different elements we show that the maximum of $|\F|$ is
	$(l-1)n+o(n)$.

Levon Khachatrian, Bielefeld

      Talk: Forbidden weights
On a Generalization of the Kruskal-Katona Theorem

J\'anos K\"orner, Rome

	      talk: NEW ENTROPY BOUNDS IN ASYMPTOTIC COMBINATORICS

	      Abstract: 
	      Search theory, as founded by R\'enyi and continued in the work
	      of Katona, is the best example for the relevance of Information
	      Theory to extremal combinatorics. Many of the problems in this
	      field are, from a purely mathematical point of view, questions
	      about the largest possible size of a family of subsets of an
	      $n$--set in which certain small configurations are excluded. In
	      this talk we shall survey the best non--existence bounds for
	      several of these problems in which the excluded configuration
	      has at most 4 member sets.

	      To illustrate the advantage of studying these problems
	      collectively, we explain the following recent result obtained
	      with Angelo Monti.  Following Erd\H os and Rado, three sets are
	      said to form a {\it delta triple} if any two of them have the
	      same intersection.  Let $F(n, 3)$ denote the largest cardinality
	      of a family of subsets of an $n$--set not containing a
	      delta--triple.  It is not known whether $\limsup_{n \rightarrow
	      \infty} n^{-1} \log F(n, 3)<1$.  We say that a family of
	      bipartitions of an $n$--set is qualitatively 3/4--weakly
	      3--dependent if the common refinement of any 3 distinct
	      partitions of the family has at least 6 non--empty classes,
	      (i. e., at least 3/4 of the total.) Let $I(n)$ denote the
	      maximum cardinality of such a family.  We derive a simple
	      relation between the exponential asymptotics of $F(n, 3)$ and
	      $I(n)$ and show, as a consequence, that $\limsup_{n \rightarrow
	      \infty} n^{-1} \log F(n, 3)=1$ if and only if $\limsup_{n
	      \rightarrow \infty}n^{-1} \log I(n)=1.$

Dariusz Kowalek, Wroclaw

	TALK:  Graphs in the Steiner triple systems for $v=2^n-1$, $n\ge 3$
	points

	abstract: Steiner triple system, $STS(v)$, is a pair $(X,{\cal B})$
	where $X$ is a set of cardinality $v$ and ${\cal B}$ is a family of
	3-element subset of $X$ with the property that every 2-element subset
	of $X$ occurs precisely once as a subset of a member of ${\cal B}$.
	The members of the set $X$ are called the \emph{points} and the
	members of the set $\cal B$ are called \emph{blocks} or \emph{lines}.
	Steiner triple systems exist if and only if $v\equiv
	1\lor3(\textrm{mod }6)$.  In a Steiner triple system $STS(v)=(X,{\cal
	B})$, for each pair $\{x,y\}\subset X$, we maydefine the graph
	$G_{a,b}$ as follows.  The vertices of $G_{a,b}$ are the points in
	$X\setminus\{a,b,c\}$ where $\{a,b,c\}\in{\cal B}$.  The pair
	$\{x,y\}$ is an edge of $G_{a,b}$ if and only if either $\{a,x,y\}$ or
	$\{b,x,y\}\in{\cal B}$.

	Clearly $G_{a,b}$ is a union of disjoint cycles.  The aim of this
	presentation is to show that $STS(v)$, in which all graphs have all
	cycles with lengths 4, exists if and only if $v=2^n-1$, $n\ge 3$.

Andre Kundgen, Toronto

	talk:  Coloring face-hypergraphs of graphs on surfaces
	with Radhika Ramamurthi

	abstract: The face-hypergraph of a graph G embedded on a surface has
	the same vertex-set as G, and every hyperedge consists of the vertices
	incident to some face of G.

	A hypergraph is weakly k-colorable (weakly k-choosable) if there is a
	coloring of its vertices from a set of k colors (from every assignment
	of lists of size k to its vertices) such that no edge is
	monochromatic. Thus a weak coloring of a face-hypergraph corresponds
	to a vertex coloring of the underlying graph such that no face is
	monochromatic.

	We show that hypergraphs can be extended to face-hypergraphs in a
	natural way and use tools from topological graph theory, the theory of
	hypergraphs and design theory to obtain general bounds for the
	coloring and choosability problems. To show the sharpness of several
	bounds, we construct for every even n, an n-vertex (pseudo)
	triangulation of a surface such that every triple is a face exactly
	once.

	We conjecture that every plane face-hypergraph is weakly 2-choosable
	and we pose several open questions, most notably: Can the vertices of
	a planar graph always be properly colored from lists of size 4, with
	the restriction on the lists that the colors come in pairs and a color
	is in a list if and only if its twin color is?

Uwe Leck, Rostock

	talk: A new generalization of the Kruskal-Katona theorem

	abstract: We consider the poset $P(N;A_1,A_2,\dots,A_m)$ consisting of
	all subsets of a finite set $N$ which do not contain any of the
	$A_i$'s, where the $A_i$'s are mutually disjoint subsets of $N$. The
	elements of $P$ are ordered by inclusion. We present a new result
	saying that $P$ belongs to the class of Macaulay posets, i.e. we show
	a Kruskal-Katona type theorem for $P$.  For the case that the $A_i$'s
	form a partition of $N$, the dual $P^*$ of $P$ became known as the
	orthogonal product of simplices. Since the property of being a
	Macaulay poset is preserved by turning to the dual, we showed in
	particular that orthogonal products of simplices are Macaulay posets.
	Besides, we proved that the posets $P$ and $P^*$ are additive.

Andr\'as Luk\'acs, SZTAKI, Budapest

       no talk

Alexandre Makhnev, Ekaterinburg

	TALK: On some pseudo-geometric graphs for partial geometries

Gregory Margulis, Yale

	no talk

Jiri Matousek, Prague

     talk: Transversals and the fractional Helly theorem

----------------------------
Jeanette McLeod, Darwin

	no talk

Peter Mih\'ok, Kassa

	talk: On generalized colorings of hypergraphs

	abstract:
\documentstyle[12pt]{article}
\setlength{\oddsidemargin}{-0.2in}
\setlength{\textwidth}{6.7in}
\setlength{\topmargin}{-0.3in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\parskip}{0.12in}
\setlength{\textheight}{9.5in}
\pagestyle{plain}

\def\huh{\hbox{\vrule width 2pt height 8pt depth 2pt}}
\def\Bbb#1{{\bf #1}}
\def\eqnum#1{\eqno (#1)}
\def\blacksquare{\hbox{\vrule width 4pt height 4pt depth 0pt}}
\def\square{\hbox{\vrule\vbox{\hrule\phantom{o}\hrule}\vrule}}

\newcommand{\prf}{\noindent{\b {Proof.}}\ }
\def\b#1{{\mbox{\boldmath $#1$}}}

\newcommand{\ak}{\hspace{20pt}}
\newcommand{\bak}{\parindent=0pt}
\newcommand{\kw}{\rule{2mm}{2mm}}
\def\lewz#1{\leqno(#1)}

\newcommand{\sm}{\smallskip}
\newcommand{\ms}{\medskip}
\newcommand{\bs}{\bigskip}
\newcommand{\mcq}{{\cal Q}}
\newcommand{\mcg}{{\cal G} }
\newcommand{\mcr}{{\cal R} }
\newcommand{\mcp}{{\cal P}}
\newcommand{\mci}{{\cal I}}
\newcommand{\mco}{{\cal O}}
\newcommand{\F}{\mbox{\boldmath $F$}}
\newcommand{\M}{\mbox{\boldmath $M$}}
\newcommand{\Q}{\mbox{\boldmath $Q$}}
\newcommand{\U}{\mbox{\boldmath $U$}}
\renewcommand{\S}{\mbox{\boldmath $S$}}
\newcommand{\mcc}{\mbox{\boldmath $C$}({\cal P})}
\newcommand{\mk}{{\scriptstyle \circ}}
\newcommand{\p}[1]{{\cal P}_#1}
\newcommand{\MM}{\mbox{\sf%
\makebox[0ex][l]{\rule[-.025ex]{.15ex}{1.55ex}}%
\makebox[0ex][l]{\rule[1.53ex]{.4ex}{.05ex}}%
\makebox[.05ex][l]{\rule[-.025ex]{.4ex}{.05ex}}M}}
\newcommand{\Pn}{${\cal P}_{1}, {\cal P}_{2}, \ldots ,{\cal P}_{n}$}
\newcommand{\mcipp}{Ip\;({\cal R})}
\newcommand{\mcip}{Ip\;}

\newtheorem{dnt}{Definition}
\newtheorem{pro}{Proposition}
\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}
\newtheorem{cor}{Corollary}
\newtheorem{con}{Conjecture}
\newtheorem{exa}{Example}
\newtheorem{prbl}{Problem}
\begin{document}

\baselineskip=12pt

\centerline{{\Large {\bf On generalized colorings of hypergraphs}}}
\bigskip

\centerline{Peter Mih\'ok}
\smallskip
\centerline{{\it Department of Applied Mathematics}}
\centerline{{\it Faculty of Economics, Technical University}}
\centerline{{\it B. N\v emcovej, 040 01 Ko\v{s}ice, Slovak Republic}}
\centerline {{\it and}}
\centerline{{\it Mathematical Institute, Slovak Academy of Science}}
\centerline{{\it Gre\v s\'akova 6, 040 01 Ko\v{s}ice, Slovak Republic}}
\centerline{\scriptsize{e-mail:{\it mihokp@tuke.sk}}}



\begin{abstract}
Let $H$ be a hypergraph $H = (X,E)$, where $E$ is a system of subsets
(hyperedges) of a finite set $X$ - called the set of vertices of $H$. We
will consider simple hypergraphs (i.e. without loops and multiple edges)
only. A simple graph $G = (V,E)$ is a simple hypergraph whose edges are
$2$-element subsets of the vertex set $V$. A property $\mcp$ of hypergraphs
is any nonempty isomorphism closed class of hypergraphs. A property of
hypergraphs is called hereditary if it is closed under
induced-subhypergraphs and additive if it is closed under taking disjoint
unions of hypergraphs. For additive hereditary properties \Pn \ a hypergraph
$H = (X,E)$ is said to be (\Pn)-partitionable if its vertex set $X$ can be
partitioned into sets $X_1,X_2, \dots,X_n$ such that the induced
subhypergraph $H_i = (X_i,E(X_i))$ has property $\mcp_i$ for $i=1,2,
\dots,n$. Let us denote by $\p1\mk\p2\mk\cdots\mk\p{n}$ the class of all
(\Pn)-partitionable hypergraphs. A property $\mcr$ of hypergraphs is ${\em
reducible}$ if there are nontrivial properties $\p1,\p2$ such that $\mcr =
\p1 \mk \p2$, otherwise it is called ${\em irreducible}$.

We will present the Unique Factorization Theorem for additive hereditary
properties of hypergraphs and a necessary and sufficient condition for the
existence of uniquely (\Pn)-partitionable hypergraphs. The presented results
are generalizing the analogous statements for simple graphs.
\end{abstract}

\newpage

\section{Motivation and main results}

We consider finite simple hypergraphs, so that a hypergraph $H$  be a
ordered pair $H = (X,E)$, where $E$ is a system of subsets (hyperedges) of a
finite set $X$ - called the set of vertices of $H$. We will consider simple
hypergraphs (i.e. without loops and multiple edges) only.
Definitions not given here may be found in \cite{lo79,be73}.
A {\it property of hypergraphs} is any nonempty class of hypergraphs closed
under isomorphism. A property of hypergraphs is called {\it hereditary} and
{\it additive} if it is closed under taking induced subhypergraphs and
disjoint unions of hypergraphs, respectively. Hereditary properties of
graphs have been investigated intensively (see \cite{both97, bobr97}). In
\cite{ja01} it was proved that additive and hereditary properties of
hypergraphs form a completely distributive algebraic lattice.

\noindent Let $\p1,\p2, \dots,\p{n}$ be properties of hypergraphs. A
hypergraph $H$ is $(\p1,\p2, \dots,\p{n})$-{\it partitionable} if the vertex
set $X$ of $H$ can be partitioned into sets $X_1, X_2,\dots, X_n$ such that
the induced subhypergraphs $(X_i,E(X_i))$ of $H$, where $E(X_i)$ consists of
all hyperedges of $H$ all of whose vertices belong to $X_i$, has property
$\p{i}$; $i=1,2,\dots,n$. Let us denote by $\p1\mk\p2\mk\cdots\mk\p{n}$ the
class of all (\Pn)-partitionable hypergraphs. We shall denote by $H[X_i]$
the induced subhypergraph  $(X_i,E(X_i))$, \ and by $[H[X_i]]$ the smallest
additive hereditary property of hypergraphs which contains $H[X_i]$.

\noindent A hereditary property $\mcr$ is said to be {\it reducible} if
there exist hereditary properties $\p1$ and $\p2$ such that
$\mcr=\p1\mk\p2$; otherwise the property $\mcr$ is {\it irreducible}.
Reducible properties of hypergraphs are related to generalized colourings of
hypergraphs and can be considered as generalization of regular colouring of
hypergraphs (see e.g. \cite{lo68}).



The notions given above and presented results are motivated by analogous
notions and results for simple finite graphs.
The problem: {\it "Is the factorization of a property of graphs into
irreducible properties unique?"} has been stated in the book \cite{jeto95}
of Jensen and Toft "Graph Coloring Problems". The affirmative answer for
hereditary and additive properties of graphs was given and proved in
\cite{mi00b}.
The aim of the talk will be to prove the unique factorization in the class
of additive hereditary properties of simple hypergraphs.

\begin{thm} \label{uft}
Any reducible additive hereditary property of simple hypergraphs is uniquely
factorizable
into irreducible factors (up to the order of factors).
\end{thm}

The proof of the main Theorem is using the concept {\it
$\mcr$-decomposability number of a hypergraph} defined as follows:

\begin{dnt}
Let $H = (X,E)$ be a hypergraph and $\mcr$ be an additive hereditary
property of hypergraphs. Define

\noindent $dec_{\mcr}(H) = \max \{ n : \mbox{ there exists a partition} \
(X_1,X_2, \ldots ,X_n), X_i \not= \emptyset$, \ of $X$ such that

$[H[X_1]] \mk [H[X_2]]\mk \ldots \mk [H[X_n]] \subseteq \mcr \}.$ If
$H\not\in\mcr$ we set $dec_{\mcr}(H)$ to be zero.

\noindent A hypergraph $H$ is said to be $\mcr$-decomposable if
$dec_{\mcr}(H) \geq 2$; otherwise $H$ is $\mcr$-indecomposable.
\end{dnt}

The concept is motivated by the following observation:

Let us suppose that a hypergraph $H \in \mcr = \mcp \mk \mcq$ and let
$(X_1,X_2)$ be a $(\mcp,\mcq)$-partition of $H$. Then $[H[X_1]] \mk [H[X_2]]
\subseteq \mcr$. Thus if the property $\mcr$ is reducible, every hypergraph
$H \in \mcr$ with at least two vertices is $\mcr$-decomposable.

We shall prove that for any additive reducible hereditary property of
hypergraphs also the converse assertion holds:

\begin{thm} \label{reddec}
A hereditary additive property of hypergraphs $\mcr$ is reducible if and
only if all hypergraphs in $\mcr$ with at least two vertices are
$\mcr$-decomposable\@.
\end{thm}

\ms

A~hypergraph $H$ is said to be {\it uniquely (\Pn)-partitionable} if $H$ has
exactly one
(unordered) (\Pn)-partition $(X_1,X_2,\ldots,X_n)$.
Let us denote by \U$(\mcp_1 \mk \mcp_2 \mk \dots \mk
\mcp_n)$ the class of all uniquely (\Pn)-partitionable hypergraphs.
In the case $\mcp_1 = \mcp_2 = \dots = \mcp_n = \mcp$ we write
$\mcp_1 \mk \mcp_2 \mk \dots \mk \mcp_n = \mcp^n$ and we say that
$H$ belonging to  \U$(\mcp^n)$ is uniquely $(\mcp,n)$-partitionable.


It turns out that the existence of uniquely partitionable hypergraphs
follows from the proof of the Unique Factorization Theorem.

\begin{thm} \label{irr}
Let $\mcp$ be an additive hereditary property of hypergraphs.

Then  for $n\geq 2, \U({\cal P}^n) \not = \emptyset$ if and only if ${\cal
P}$ is
irreducible.
\end{thm}

Analogously as for hereditary properties of graphs (see \cite{mi00b}) we
shall prove that every reducible additive hereditary property $\mcr$ of
hypergraphs can be generated by hypergraphs which are uniquely partitionable
with respect to its irreducible factors.

\begin{thm} \label{eupg}
Let $\mcr = \mcp_1 \mk \mcp_2 \mk \ldots \mk \mcp_n$, $n\geq 2$ be the
factorization of a reducible additive hereditary property $\mcr$ into
irreducible factors.

Then every hypergraph $H \in \mcr$ is an induced subhypergraph of a uniquely
(\Pn)-partitionable hypergraph $H^*$.
\end{thm}

Finally, we give a necessary and sufficient condition for the existence of
uniquely
(\Pn)-partitionable hypergraphs (for graphs see \cite{brbu99}):

\begin{thm} \label{char}
Let $\mcp_1, \mcp_2, \dots ,\mcp_n$, $n\geq 2$, be
any non-trivial additive hereditary properties of hypergraphs.  Then there
exists a uniquely $(\mcp_1, \mcp_2, \dots , \mcp_n)$-partitionable
hypergraph if and only if for each $i,j \in \{1, 2, \dots , n\}$ with
$i \not = j$ we have that $gcd(\mcp_i, \mcp_j) = \Theta$  or
$\mcp_i = \mcp_j$ is an irreducible pro\-per\-ty.
\end{thm}

The construction used in the proofs can be used to prove analogous results
for oriented graphs, simple digraphs and other combinatorial structures. For
partially ordered sets the Unique Factorization Problem remains open.

Some relations to the papers of J. Demetrovics, Z. F\"uredi and G.O.H.
Katona (see \cite{deka83,defu85}) on the combinatorial problems of database
models will be mentioned.

\begin{thebibliography}{10}

\bibitem{be73}
C. Berge, {\em Graphs and Hypergraphs}, North Holland - Elsevier, 1973.

\bibitem{both97}
B.~Bollob{\'a}s and A.~G. Thomason, {\em Hereditary and monotone properties
of graphs}, in: R.~L. Graham and J.~Ne{\v s}et{\v r}il, eds., The
mathematics of
  Paul Erd{\H o}s, {II}, Algorithms and Combinatorics vol.~14
(Springer-Verlag,
  1997), 70--78.

\bibitem{bobr97}
M.~Borowiecki, I.~Broere, M.~Frick, P.~Mih{\'o}k and G.~Semani{\v s}in, {\em
Survey of hereditary properties of graphs}, Discussiones Mathematicae -
Graph  Theory {\bf 17} (1997), 5--50.

\bibitem{brbu99}
I.~Broere, J.~Bucko, {\em Divisibility in additive hereditary graph
properties and uniquely partitionable graphs}, Tatra Mountains Math.
Publications {\bf 18} (1999) 79--87.

\bibitem{deka83}
J. Demetrovics, G.O.H. Katona, {\em Combinatorial problems of database
models}, Colloquia Math. Soc. J. Bolyai 42. Algebra, Combinatorics and Logic
in Computer Science, Gy\" or, 1983, 331--353.

\bibitem{defu85}
J. Demetrovics, Z. F\" uredi and G.O.H. Katona, {\em Minimum matrix
representation of closure operations}, Discrete Applied Mathematics {\bf 11}
(1985) 115--128.

\bibitem{ja01}
J. Jakub{\'\i}k, On the lattice of additive hereditary properties of finite
graphs, manuscript 9 pages.

\bibitem{jeto95}
T.~R. Jensen and B.~Toft, Graph co\-lou\-ring prob\-lems
  (Wiley--Inter\-sci\-ence Publications, New York, 1995).

\bibitem{lo68}
L. Lov\'asz, {\em On chromatic number of finite set systems}, Acta Math.
Acad. Sc. Hun. {\bf 19} (1968) 59--67.

\bibitem{lo79}
L. Lov\'asz, {\em Combinatorial Problems and Exercices}, Akad\'emiai
Kiad\'o, Budapest 1979

\bibitem{mi85}
P.~Mih{\'o}k, {\em Addi\-ti\-ve he\-re\-di\-ta\-ry pro\-per\-ties and
  u\-ni\-que\-ly par\-ti\-ti\-o\-nab\-le graphs}, in: M.~Borowiecki and
  Z.~Skupien, eds., Graphs, hypergraphs and matroids (Zielona G{\'o}ra,
1985), 49--58.

\bibitem{mi00b}
P. Mih\'ok, {\em Unique factorization theorem}, Discussiones Mathematicae -
Graph Theory {\bf 20} (2000) 143--153.

\end{thebibliography}

\end{document}

Bal\'azs Mont\'agh, Memphis

	talk: Anti-Ramsey theorem on big double stars and on long paths

	abstract:
\begin{abstract}
Erd\H{o}s, Simonovits and S\'os have initiated the investigation of 
anti-Ramsey
problems for graphs. We say that  a graph is {\it totally multicolored} (TMC, 
for
short) if any two of its edges have different colors. Given a family ${\cal 
L}$
of graphs, let $AR(n,{\cal L})$ be the largest integer  $t$ for which it is 
possible to
$t$-color the edges of $K_n$ so that every color is used at
least once, and there is no TMC subgraph that belongs to ${\cal L}$. It is 
easy
to see that $AR(n,{\cal L})\ge ex(n,{\cal L}^*)+1$, where ${\cal
L}^*=\{L-e:L\in {\cal L},e\in E(L)\}$.


Let ${\cal T}_m$ be the family of all trees with $k$ edges,
and let ${\cal T}^d_m$ be the
family of all trees with $m$ edges of diameter at most $d$. Jiang and
West have determined the numbers $AR(n,{\cal T}_m)$. They have found that
$AR(n,{\cal T}_m)=ex(n,{\cal T}^*_m)+1$.
The case $k=n-1$, that is, the case of spanning trees,
was solved independently by Bialostocki
and Voxman.
Bialostocki
conjectured that $AR(n,{\cal T}_{n-1})=AR(n,{\cal T}^4_{n-1})$.

We prove that much more is true. First of all, $AR(n,{\cal
T}_{n-1})=AR(n,{\cal T}^3_{n-1})$. Furthermore, $AR(n,{\cal L})=AR(n,{\cal
T}_n)$ holds even for a family ${\cal
L}$ that is much smaller than ${\cal T}^3_n$, in fact, for a family with 
$|{\cal
L}|=4$.
Let ${\cal DS}^k_{m}$ be the families
of double stars (that is,  trees
of diameter 3) with $m$ edges whose
maximal degree is at least $k$. We shall show that $AR(n,{\cal
T}_{n-1})=AR(n,{\cal DS}^{n-4}_{n-1})<AR(n,{\cal DS}^{n-3}_{n-1}).$
Our method works also in the case when the trees are a bit smaller than
the spanning trees:
we proved that if $n>11k/2+7$
then $AR(n,{\cal T}_{n-k})=AR(n,{\cal
DS}^{n-2k-2}_{n-k})$.

We prove a similar theorem for a concrete graph: if
if $n>k^2+7k-1$ then
$AR(n,P_{n-k})=AR(n,{\cal T}_{n-k})={n-k-1\choose 2}+1$. This is an
expansion of a part of a theorem of Simonovits ans S\'os that was
published without proof.

\end{abstract}

Dhruv Mubayi, Georgia Tech

	Talk: Some new results about hypergraph Turan numbers
	with Vojtech Rodl.
	Abstract: We describe some recent results 
        about asymptotics for hypergraph Turan numbers.
        For example, we will show a new proof of a result
        of Frankl and Furedi about the Turan number of the
        triple system 123, 124, 345. 

Brendan Nagle, Atlanta

	talk: Counting Small Cliques in Hypergraphs

	abstract: Szemer\'edi's Regularity Lemma is a powerful tool in
	extremal graph theory.  Many of its applications are based on the
	following ``Counting Fact": if $G = (V,E)$ is a graph with $V=V_1\cup
	\ldots \cup V_k$ where each $G[V_i,V_j]$, $1\leq i<j\leq k$, is
	$\varepsilon$-regular with density $d$ and $|V_1|=\ldots =|V_k|=n$,
	then $G$ contains $d^{{k \choose 2}}n^k (1+f(\varepsilon))$ cliques
	$K_k$, where $f(\varepsilon ) \rightarrow 0$ as $\varepsilon
	\rightarrow 0$.  While there were several attempts to generalize
	Szemer\'edi's Regularity Lemma to hypergraphs, none seemed to admit an
	analogue of the Counting Fact above.  In this talk, we discuss a
	generalization of Szemer\'edi's Regularity Lemma to 3-uniform
	hypergraphs due to Frankl and R\"odl, and we discuss the corresponding
	Counting Fact it succeeds to render.  We also discuss some recent
	applications of this work.


J\'anos Pach, R\'enyi Institute, Budapest

	no talk

Luke Pebody, Memphis

	no talk

Oleg Pikhurko, Cambridge

     talk: Minimum Saturated Hypergraphs.

Stefan Porubsky, Prague

        talk: Sets of regular systems of divisors of a generalized
        integer 
	
	abstract: The notion of a regular systems of divisors of a number
	underlying a Narkiewicz's idea of the generalization of the familiar
	Dirichlet and unitary convolution of arithmetical functions is used to
	extend some combinatorial results about systems of subsets of divisors
	of a generalized integer.

Radhika Ramamurthi, Urbana

	talk: Splittable colorings of graphs and hypegraphs( with Furedi)

	Abstract: Ramsey colorings can be interpreted as total colourings
	(colorings of the edges and vertices) using a two round game played
	with an adversary.  Given integers n,m and r, we want to color the
	vertices and edges of the complete graph (or k-uniform hypergraph) on
	n vertices with r colors in two rounds. We lose if, at the end of two
	rounds, there is a totally monochromatic m-clique, that is a graph or
	hypergraph on m vertices all of whose vertices and edges have the same
	color.  In the first round, we color all the edges. We then challenge
	the devil to color the vertices from the same r colors. The threshold
	below which we always win (assuming intelligent play) is exactly the
	Ramsey number R_r(m).  We investigate the threshold when the players
	roles are reversed - i.e.  the devil does Round 1 and we do Round
	2. This parameter was introduced by Erdos and Gyarfas. We generalize
	the problem to hypergraphs and provide some general bounds for the
	threshold beyond which we always win the second game.

Oliver Riordan, Cambridge

       TALK:  The diameter of a scale free random graph
       AUTHORS: Bela Bollobas and Oliver Riordan
       ABSTRACT:    Can I send one later? The subject is random graphs


Ian Roberts, Darwin

    TALK: Minimising union-closed collections
    AUTHORS: Ian Roberts

	Abstract: A collection of sets C is union-closed if A union B is in C
	whenever A,B is in C.  The size of C is the number of sets in C. The
	volume of C is the sum of the cardinalities of the sets in C. A
	natural question to ask is how to choose m k-sets to achieve the
	minimum size over all union-closed collections generated by m
	k-sets. Another natural question is to ask how to choose m k-sets to
	achieve the minimum volume over all union-closed collections generated
	by m k-sets. There is a natural ordering on k-sets which appears to
	achieve both minimums simultaneously. Partial results on this will be
	presented and the methods of proof outlined.

Vojtech Rodl, Atlanta

	no talk

Peter Rosenstiehl, CNRS, Paris

	talk: P. ROSENSTIEHL, P. OSSONA DE MENDEZ CODING POINTED HYPERMAPS
	abstract:  Connected permutations on an ordered set are 
		   in one to one relation
		   with pointed hypermaps. The coding relise one 
		   properties of the right minima
		   of a permutation, and the unusual 
		   correspondance of D. Knuth.

Andrzej Rucinski, Poznan

	talk: Ramsey Properties of Families of Graphs

	Abstract: We assume only the basic knowledge of Ramsey Theory, in
		particular the standard arrow notation. We say that the
		sequence of graphs G_1,...,G_r dominates H_1,...,H_s if every
		graph which arrows G_1,...,G_r, also arrows H_1,...,H_s.  For
		instance, in the edge-coloring case, K_6,K_4 dominates
		K_4,K_3,K_3.

		For sequences of complete graphs, we characterize this
		relation by showing that a natural necessary condition
		(illustrated by the above example) is sufficient as well. For
		sequences of non-complete graphs we have several partial
		results in the vertex-coloring case, and several conjectures
		in the edge-coloring case. This is a joint work by two sets of
		authors whose union consists of R. Graham, T. Luczak, V. Rodl,
		S. Urbanski and the speaker.

Mikl\'os Ruszink\'o, SZTAKI, Budapest

	 talk: On the maximum size of $(p,Q)$-free families
	 by Furedi, Gyarfas, Ruszinko

	Abstract: Let $p$ be a positive integer and let $Q$ be a subset of
	$\{0,1,\dots ,p\}$. Call $p$ sets $A_1,A_2,\dots ,A_p$ of a ground set
	$X$ a $(p,Q)$-system if the number of sets $A_i$ containing $x$ is in
	$Q$ for every $x\in X$.  In hypergraph terminology, a $(p,Q)$-system
	is a hypergraph with $p$ edges such that each vertex $x$ has degree
	$d(x)\in Q$.  A family of sets ${\cal F}$ with ground set $X$ is
	called $(p,Q)$-free if no $p$ sets of ${\cal F}$ form a $(p,Q)$-system
	on $X$.  We address the Tur\'an type problem for $(p,Q)$-systems:
	$f(n,p,Q)$ is defined as $\max |{\cal F}|$ over all $(p,Q)$-free
	families on the ground set $[n]=\{1,2,\dots ,n\}$.

	We study the behavior of $f(n,p,Q)$ when $p$ is fixed (allowing
	$2^{p+1}$ choices for $Q$) while $n$ tends to infinity.  The new
	results of this paper mostly relate to the middle zone where
	$2^{n-1}\le f(n,p,Q) \le (1-c)2^n$ (in this upper bound $c$ depends
	only on $p$).  This direction was initiated by Paul Erd\H os who asked
	about the behavior of $f(n,4,\{0,3\})$.  In addition we give a brief
	survey on results and methods (old and recent) in the low zone (where
	$f(n,p,Q)=o(2^n)$) and in the high zone (where $2^n-(2-c)^n <
	f(n,p,Q)$). The results were obtained by Zolt\'an F\"uredi, Andr\'as
	Gy\'arf\'as and Mikl\'os Ruszink\'o.

 
Imre Ruzsa, R\'enyi Institute, Budapest

	no talk

Alexander Sapozhenko, Moscow

	  Talk: Sum-free sets and independent sets

G\'abor S\'arkozy, Worcester

	no talk

Stanley Selkow, Worcester

	no talk

Mikl\'os Simonovits, R\'enyi Institute, Budapest

	 talk: On the Erd\H{o}s-Frankl-R\"odl theorem
	 \author{J. Balogh, B. Bollob\'as and M. Simonovits}

	 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.

G\'abor Simonyi, R\'enyi Institute, Budapest

	talk: Imperfection ratio and graph entropy

	abstract: The imperfection ratio is a recently introduced (by
        Gerke and McDiarmid) graph invariant that measures how far is a graph
        from being perfect. The main new result in the talk is that the
        imperfection ratio can be expressed in terms of graph entropy, an
        information theoretic functional defined by Korner in the 1970's.

Jozef Skokan, Urbana (with V. R\"odl)

      talk: Regularity lemma for $k$-uniform hypergraphs


	Abstract:The Regularity Lemma of Szemer\'edi has been an important
	tool in graph theory and combinatorics since its discovery in
	1973. There were several attempts to generalize this lemma for
	$k$-uniform hypegraphs. However, until work of P. Frankl and
	V. R\"odl, all these generalizations had failed to produce results
	comparable to the graph case.

	In this talk, we summarize the most recent development in this area
	and outline ideas used in formulation and the proof of a regularity
	lemma for graphs, 3-uniform hypergraphs, and 4-uniform (and in general
	$k$-uniform) hypergraphs. 

Cliff Smyth, Rutgers

       Title: Equilateral or 1-distance sets and Kusner's Conjecture
 
	Abstract: A 1-distance set in a metric space is a set of points such
		  that each pair determines the same distance.  The maximum
		  size of a 1-distance set in Euclidean R^n is n+1.  If the
		  distance on R^n is given by a general norm less is known.  A
		  lower bound of ((log/loglog)(n))^(1/3) is due to Brass and
		  an upper bound of 2^n is due to Petty.  The upper bound is
		  attained for the max norm.

		  In 1983 Kusner conjectured that for the L^p norm, 1 < p <
		  infty the answer is n+1.  All that had been known for
		  general p was a lower bound of n+1 and an upper bound of
		  2^n.  We show an upper bound of O(n^c) where c=(p+1)/(p-1).

Sung-Yell Song, Pohang

	no talk

Tibor Szab\'o, Zurich

      talk: k-wise intersection theorems (joint work with Van Vu)

	Abstract: Intersection theorems usually estimate the size of a family
	of sets with some restriction on the pairwise intersections of its
	members.  Notable examples, among others, are the theorems of Fischer;
	Ray-Chaudhuri and Wilson; Frankl and Wilson.  We investigate similar
	statements when the restrictions apply to $k$-wise intersections,
	$k>2$, instead of pairwise ones. Part of the difficulty is that linear
	algebra, which provides a natural context for $k=2$, does not seem to
	have the appropriate concepts when $k>2$.  F\"uredi established a
	combinatorial connection between the pairwise and $k$-wise case, for
	uniform systems. We aim to obtain precise results, and consider
	nonuniform examples as well.

L\'aszl\'o Szeg\H o, E\"otv\"os University, Budapest

	no talk

L\'aszl\'o Sz\'ekely

       talk: KATONA'S PROOF TO ERDOS-KO-RADO REVISITED
       Szerzok: Gyula Karolyi, Mario Szegedy, Laszlo Szekely
       abstract: For a long time, Katona's celebrated cyclic permutation proof
       to the Erdos-Ko-Rado theorem was a single exceptional gem. Then more
       similar exceptional gems were found. Peter Erdos, Faigle, and Kern made
       a systemtatic description of the existing gems, using groups, but they
       hardly added any new items to the list. Now it is clear, that these
       gems are the rule, and not the exception.

Endre Szemer\'edi, Rutgers

	talk: tba

John Talbot, Oxford

     talk: Lagrangian Hypergraphs
     author: J. Talbot
     abstract:
     How large can teh aLagrangian of an $r$-graph with $m$ edges be? Frankl
     and F\"uredi conjectured taht the $r$-graph of size $m$ formed by taking
     the first $m$ sets in the colex order has the largest Lagrangian of all
     $r$-graphs of size $m$. WE prove the first "interesting" case of this
     conjecture, namely that the $3$-graph with $k\choose 3$ edges and largest
     Lagrangian is the complete $3$-graph of order $k$.

Ulrich Tamm, Bielefeld

       talk: A continued fractions approach to a conjecture of Stanley

Kriszti\'an Tichler, R\'enyi Institute, Budapest

	  talk: Extremal theorems on database matrices
	  Abstract: Consider a matrix satisfying the following two
	  properties. There are no two rows of the matrix having the same
	  entries in both columns of any edge of a given graph G on the
	  columns. On the other hand for each subset of the columns not
	  containing any edge of the graph there are two rows having the same
	  entries in these columns. In this paper we maximize the minimal
	  number of the rows of such a matrix on all graphs. The heart of the
	  proof is a combinatorial lemma, which might be interesting in
	  itself.  

Bernhard Thalheim, Cottbus

	talk: Reconsidering the Hungarian approach to database complexity

Norihide Tokushige, Ryukyu

	 talk: Frankl, Tokushige: Weighted multiply intersecting families

David Weinreich, Gettysburg College

      no talk