A version of the Tur{\'a}n problem for linear hypergraphs-density conditions

Halina Bielak
Inst. of Math., UMCS, Lublin

PDF

Minisymposium: VERTEX COLOURINGS AND FORBIDDEN SUBGRAPHS

Content: Let $\mathcal{H}=(V,\mathcal{E})$ be a simple linear hypergraph. We consider a blow-up hypergraph $\mathcal{G}[\mathcal{H}]$ of $\mathcal{H}$. We are interested in the following problem. We have to decide whether there exists a blow-up hypergraph $\mathcal{B}[\mathcal{H}]$ of $\mathcal{H}$, with given hyperedge densities, such that $\mathcal{H}$ is not a transversal in $\mathcal{B}[\mathcal{H}]$. Recently the density Tur{\'a}n problem was studied by Csikv{\'a}ri and Nagy for simple graphs [{\em Combin. Prob. Comput.} 21 (2012) 531--553] and [{\em The Electronic J. Combin.} 18 (2011) \# P46]. We generalize their results. We present an efficient algorithm to decide whether a given set of hyperedge densities ensures the existence of a linear hypertree $\mathcal{T}$ in all blow-up hypergraphs $\mathcal{B}[\mathcal{T}]$. Moreover, we show some conditions for critical hyperedge density of linear hypertrees and some other linear hypergraphs.

Back to all abstracts