# Csilla Bujtas: Partition-crossing hypergraphs

Date: 5. 1. 2020

Source: Discrete mathematics seminar

Source: Discrete mathematics seminar

Torek, 7. 1. 2020, od 10h do 12h, Plemljev seminar, Jadranska 19

**Povzetek.**For a finite set

*X*, we say that a set

*H*⊆

*X*crosses a partition

*P*=(

*X*

_{1},...,

*X*

_{k}) of

*X*if

*H*intersects min(|H|,

*k*) partition classes. If |

*H*| ≥ k, this means that

*H*meets all classes

*X*, whilst for |

_{i}*H*|≤

*k*the elements of the crossing set

*H*belong to mutually distinct classes. A set system \cH crosses

*P*, if so does some

*H*∈ \cH. The minimum number of

*r*-element subsets, such that every

*k*-partition of an

*n*-element set

*X*is crossed by at least one of them, is denoted by

*f*(

*n,k,r*).

The problem of determining these minimum values for *k=r* was raised
and studied by several authors, first by Sterboul in 1973. In an earlier
research, we determined asymptotically tight estimates on *f*(*n,k,k*)
for every fixed *k* as n → ∞. Now we consider the more general
problem and establish lower and upper bounds for *f*(*n,k,r*). For various
combinations of the three values *n,k,r* we obtain asymptotically tight
estimates, and also point out close connections of the function *f*(*n,k,r*) to Turán-type extremal problems on graphs and hypergraphs.

This is a joint work with Zsolt Tuza.