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 k11k/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 i0$. 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