On the number of \(A\)-transversals in hypergraphs

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 hype...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-08
Main Authors: Barát, János, Gerbner, Dániel, Halfpap, Anastasia
Format: Article
Language:English
Subjects:
Apexes
Graph theory
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422