The workshop is the third meeting of DIMACS/DIMATIA/Renyi Working Group on Extremal Combinatorics.
The central two subjects of the workshop are extremal graph theory and extremal problems arising from combinatorial search and testing.
A polynomial proof of the Erdos-Ko-Rado theorem
In 1961, Erdos, Ko, and Rado proved that if F is a k-uniform family of subsets of a set of n elements with k≤ 1/2n, and every pair of members of F intersect, then |F| ≤ n-1 \choose k-1. They also showed that for n>2k here equality holds if F consists of all k sets containing a given element of the underlying set.
Beside their remarkable proof (induction on k, and for a given k left-shifting and induction on n), there are many interesting new proofs. In 1972, Katona used a simple and an elegant argument, the permutation method. Daykin obtained Erdos-Ko-Rado from the Kruskal-Katona theorem. Hajnal and Rothschild proved it for n> n_0(k) by an early version of the kernel (or delta-system) method, developed and used very successfully by Frankl (the first full description of the method was published in Deza, Erdos, and Frankl). Most remarkable, Lovasz in his ground-breaking paper used its geometric representation method to prove that the Shannon capacity of the Kneser graph K(n,k) is at most n-1 \choose k-1, (n ≥ 2k), thus yielding another proof (and generalization). Wilson gave an ingenious proof, using Delsarte's linear programming bound. (Actually, he proved much more concerning t-intersecting families.)
The aim of this paper is to exhibit a true, short, polynomial proof for the Erdos-Ko-Rado Theorem. This is a joint work with Kyung-Won Hwang and Paul M. Weichsel.
How bipartite is a graph with no cycle of length 2k+1?
In this talk, different parameters "measuring" bipartiteness are studied for graphs without (2k+1)-cycles, sometimes with extra degree conditions: how difficult is to make them bipartite, how many triangles are in them, etc.
Excluded subposets in the Boolean lattice
Let [n]={1,2,..,n} $ be a finite set, families FF of its subsets will be investigated. [n]\choose k denotes the family of all k-element subsets of [n]. Let P be a poset. The goal of the present investigations is to determine the maximum size of a family CF \subset 2^[n] which does not contain P as a (non-necessarily induced) subposet. This maximum is denoted by La(n,P).
There are some Ps for which La(n,P) has been exactly determined. The easiest example is the case when P consist of two comparable elements. Then we are actually looking for the largest family without inclusion that is without two distinct members F,G\ in FF such that F\subset G. The well-known Sperner theorem gives the answer, the maximum is n \choose \lfloor n/2 \rfloor.
In most cases, however La(n,P) is only asymptotically determined in the sence that the main term is the size of the largest level (sets of size \lfloor n/2 \rfloor) while the second term is c/n times the second largest level where the lower and upper estimates contain diffrent constants c.
Let the poset N consist of 4 elements illustrated here with 4 distinct sets satisfying A\subset B, C\subset B, C\subset D. We were not able to determine La(n,N)$ for a long time. Recently, a new method jointly developed by J.R. Griggs, helped us to prove the following theorem.
Theorem: n\choose \lfloor n/2 \rfloor ( 1+{2/n}+o({1/n})) ≤ La(n,N) ≤ n\choose \lfloor n/2\rfloor (1+{4/n}+o({1/n})).
Distance constrained labelings of graphs of bounded treewidth
We prove that the L(2,1)-labeling problem is NP-complete for graphs of treewidth two, thus adding a natural and well studied problem to the short list of problems whose computational complexity separates treewidth one from treewidth two. We prove similar results for other variants of the distance constrained graph labeling problem.
On vetrex-sets of the hypercube whose span avoids given hyperplanes
Let Cn denote the vertices of the n dimensional hypercube and let M \subseteq Cn be a subset of it (or a subset of it consisting of vertices of weight k, where 1 ≤ k ≤ n). We will investigate and a present a few results about the maximum size of M assuming that the span of the vertices in M completely avoids (or does not contain) the hyperplane consisting of the vertices of the hypercube of weight m. (where the weight of a vertex is the number of 1 coordinates of it).
The distance of FF-free families
If FF is a fixed hypergraph, then for two FF-free hypergraphs h1=(V,E1) and h2=(V,E2) we define their FF-free distance by the number of copies of FF in h1 \cup h2=(V,E1 \cup E2) (and denote it by D_FF(h1;h2)). For a collection CC of hypergraphs the CC-free distance of two CC-free hypergraphs (that is FF-free for all FF in CC) is D_CC(h1;h2)=\sum_{FF in CC} D_FF(h1;h2). In the talk we will consider several collections of forbidden hypergraphs. For some of them we will obtain exact results on the maximum distance of pairs of CC-free hypergraphs while for others we will give upper and lower bounds on the maximum distance.
On the Empty Hexagon Theorem
Tobias Gerken has very recently proved that any sufficiently large set P of points in general position in the plane contains the six vertices of a convex hexagon with no point of P in the interior. We explain the main parts of an alternative proof of this result.
Participation is by invitation only. To inquire please contact Jan Kratochvil, Jaroslav Nesetril or Jiri Fiala.
There is no fee charged for invited attendees.