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 H ⊆ X 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.