Covers in Partitioned Intersecting Hypergraphs

Abstract

Given an integer $r$ and a vector $\vec{a}=(a_1,\dots ,a_p)$ of positive numbers with ${\sum }_{i\le p}{a}_i=r$, an $r$-uniform hypergraph $H$ is said to be $\vec{a}$-partitioned if $V(H)={\bigcup }_{i\le p}{V}_i$, where the sets $V_i$ are disjoint, and $|e\cap V_i|=a_i$ for all $e\in H,i\le p$. A $\vec{1}$-partitioned hypergraph is said to be $r$-partite. Let $t(\vec{a})$ be the maximum, over all intersecting $\vec{a}$-partitioned hypergraphs $H$, of the minimal size of a cover of $H$. A famous conjecture of Ryser is that $t(\vec{1})\le r-1$. Tuza conjectured that if $r>2$ then $t(\vec{a})=r$ for every two components vector $\vec{a}=(a,b)$. We prove this conjecture whenever $a\ne b$, and also for $\vec{a}=(2,2)$ and $\vec{a}=(4,4)$.

4 pages

References in corpus (1)

• Intersecting extremal constructions in Ryser's Conjecture for r-partite hypergraphs