Csilla Bujtas: Partition-crossing hypergraphs

Datum objave: 5. 1. 2020
Seminar za diskretno matematiko
Torek, 7. 1. 2020, od 10h do 12h, Plemljev seminar, Jadranska 19
Povzetek. For a finite set X, we say that a set HX crosses a partition P=(X1,...,Xk) of X if H intersects min(|H|,k) partition classes. If |H| ≥ k, this means that H meets all classes Xi, whilst for |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.