On the number of A-transversals in hypergraphs

Publication date 25 November 2022

Abstract: A set

S

of vertices in a hypergraph is extit{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

m a t h c a l H

and a non-empty set

A

of non-negative integers, we say that a set

S

is an extit{

A

-transversal} of

m a t h c a l H

if for any hyperedge

H

of

m a t h c a l H

, we have mbox{

| H c a p S | i n A

}. Independent sets are

0, 1, d o t s, 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, d o t s, a

or

A

being the set of odd or the set of even numbers.

This page was built for publication: On the number of $A$-transversals in hypergraphs