On the number of $A$-transversals in hypergraphs

Abstract

A set $S$ of vertices in a hypergraph is \textit{strongly independent} if every hyperedge shares at most one vertex with $S$. We prove a sharp result for the number of maximal strongly independent sets in a $3$-uniform hypergraph analogous to the Moon-Moser theorem. Given an $r$-uniform hypergraph $\mathcal{H}$ and a non-empty set $A$ of non-negative integers, we say that a set $S$ is an \textit{$A$-transversal} of $\mathcal{H}$ if for any hyperedge $H$ of $\mathcal{H}$, we have \mbox{$|H\cap S|\in A$}. Independent sets are $\{0,1,\dots ,r-1\}$-transversals, while strongly independent sets are $\{0,1\}$-transversals. Note that for some sets $A$, there may exist hypergraphs without any $A$-transversals. We study the maximum number of $A$-transversals for every $A$, but we focus on the more natural sets, e.g., $A=\{a\}$, $A=\{0,1,\dots ,a\}$ or $A$ being the set of odd or the set of even numbers.

10 pages