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