On the number of A-transversals in hypergraphs

Barát, János and Gerbner, Dániel and Halfpap, Anastasia (2024) On the number of A-transversals in hypergraphs. PERIODICA MATHEMATICA HUNGARICA, Publis. ISSN 0031-5303

Preview

Text s10998-024-00586-1.pdf Download (221kB) | Preview

Abstract

A set S of vertices in a hypergraph is 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}}} H and a non-empty set A of non-negative integers, we say that a set S is an A - transversal of {{\mathcal {H}}} H if for any hyperedge H of {{\mathcal {H}}} H , we have |H\cap S| \in A | H ∩ S | ∈ A . Independent sets are \{0,1,\dots ,r{-}1\} { 0 , 1 , ⋯ , r - 1 } -transversals, while strongly independent sets are \{0,1\} { 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, A=\{a\} A = { a } , A=\{0,1,\dots ,a\} A = { 0 , 1 , ⋯ , a } or A being the set of odd integers or the set of even integers.

Actions (login required)

Edit Item