Independent set in $3$-uniform hypergraph

936 Views Asked by At

Suppose $H$ is a $3$-uniform hypergraph such that each pair of vertices contained in at most one hyperedge. Let $\alpha(H)$ be the maximum independent set of $H.$ Independent set is a subset of vertices of $H$ contains no hyperedges. Note that $\alpha(H)$ can contain at most two vertices of each hyperedges. Now I'm looking for a subset of $\alpha(H),$ $\alpha'(H),$ such that it contains at most one vertex of each hyperedge. How large $\alpha'(H)$ can be?

I really appreciate any help/hint.

1

There are 1 best solutions below

0
On BEST ANSWER

Example: $\alpha'(H)=1.$

Let $H$ be any Steiner triple system. Then $\alpha'(H)=1$ while $\alpha(H)$ can be much larger.


Example: $\alpha'(H)=\sqrt{\alpha(H)}.$

If $A$ is a set and $k$ is a natural number, $\binom Ak=\{X\subseteq A:|X|=k\} $ is the set of all $k$-element subsets of $A.$

Let $S=[n]=\{1,2,\dots n\}.$

Let $V(H)=V=\binom S2;$ in other words, $V(H)=E(K_n).$

Let $E(H)=E=\left\{\binom X2:X\in\binom S3\right\};$ in other words, $E(H)$ is the set of all triangles in $K_n,$ where a triangle is considered as a set of edges.

The $3$-uniform hypergraph $H=(V,E)$ clearly has the property that two hyperedges share at most one vertex (two triangles have at most one side in common).

An independent set of $H$ corresponds to a triangle-free subset of $K_n;$ thus $\alpha(H)=\left\lfloor\frac{n^2}4\right\rfloor$ by Mantel's theorem.

A subset of $V(H)$ containing at most one vertex of each hyperedge is just an independent set of edges in $K_n;$ thus $\alpha'(H)=\left\lfloor\frac n2\right\rfloor.$

If $n=2m$ where $m\in\mathbb N,$ then $\alpha(n)=m^2$ and $\alpha'(n)=m=\sqrt{\alpha(n)}.$