Zoltán Füredi "A useful tool in combinatorics: Intersecting set-pair systems"

Zoltán Füredi from Rényi Institute and University of Illinois will give the talk "A useful tool in combinatorics: Intersecting set-pair systems" on the labs' Big Seminar.

Abstract:

The notion of cross intersecting set pair system (SPS) of size $m$, $\Big(\{A_i\}_{i=1}^m, \{B_i\}_{i=1}^m\Big)$ with $A_i\cap B_i=\emptyset$ and $A_i\cap B_j\ne\emptyset$, was introduced by Bollobás and it became an important tool of extremal combinatorics. His classical result states that $m\le {a+b\choose a}$ if $|A_i|\le a$ and $|B_i|\le b$ for each $i$.

After reviewing classical proofs, applications and generalizations, our central problem is to see how this bound changes with additional conditions.

In particular we consider $1$-cross intersecting set pair systems, where $|A_i\cap B_j|=1$ for all $i\ne j$. We show connections to perfect graphs, clique partitions of graphs, and finite geometries. Many problems are proposed. Most new results is a joint work with A. Gyárfás and Z. Király.

Everyone is invited to attend. The language of the lecture is English. The event is aimed at master and graduate students, as well as researchers in the field of combinatorics.