Are there any known upper bounds on the number of maximal independent sets in a hypergraph? I'm aware that simple graphs have an upper bound of $O(3^{n/3})$. How about on the number of independent sets?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ You might have some info in David Conlon's lecture 14, taking about Moon-moser inequality for hypergraph, due to Caen (alas I can't access Caen paper) its.caltech.edu/~dconlon/Extremal-course.html $\endgroup$– Thomas LesgourguesCommented Jul 20, 2021 at 1:20
-
$\begingroup$ @ThomasLesgourgues Thanks for the link! $\endgroup$– Reijo JaakkolaCommented Jul 20, 2021 at 16:09
-
$\begingroup$ @bof That is exactly what I wanted. Maybe you can provide an argument for the upper bound on the number of maximal independent sets as an answer? $\endgroup$– Reijo JaakkolaCommented Jul 20, 2021 at 16:16
-
$\begingroup$ @bof The hypergraphs that I need to consider are not necessarily $r$-uniform, for any fixed $r$, so I needed a bound on the general case. However, I would be interested to here also about the uniform case, if you have any nice references on that. $\endgroup$– Reijo JaakkolaCommented Jul 21, 2021 at 19:25
-
$\begingroup$ OK, I posted my comment as an answer. I just wanted to make sure I wasn't misunderstanding the question. I don't know about the uniform case, no doubt it's more difficult. $\endgroup$– bofCommented Jul 21, 2021 at 23:38
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The family of maximal independent sets of a hypergraph has the property that no member of the family is contained in another. Such a family of sets is called an antichain or a clutter or a Sperner family. By Sperner's theorem, a Sperner family of subsets of an $n$-element set has at most $\binom n{\lfloor n/2\rfloor}$ members. In particular, a hypergraph $H=(V,E)$ of order $|V|=n$ has at most $\binom n{\lfloor n/2\rfloor}$ maximal independent sets. This bound is attained when $E$ is the set of all $\left(\lfloor n/2\rfloor+1\right)$-element subsets of $V$.
