Balanced independent sets and colorings of hypergraphs

Abstract

A $k$-uniform hypergraph $H=(V,E)$ is $k$-partite if $V$ can be partitioned into $k$ sets $V_1,\dots ,V_k$ such that every edge in $E$ contains precisely one vertex from each $V_i$. We call such a graph $n$-balanced if $|V_i|=n$ for each $i$. An independent set $I$ in $H$ is balanced if $|I\cap V_i|=|I\cap V_j|$ for each $1\le i,j\le k$, and a coloring is balanced if each color class induces a balanced independent set in $H$. In this paper, we provide a lower bound on the balanced independence number ${\alpha }_b(H)$ in terms of the average degree $D=|E|/n$, and an upper bound on the balanced chromatic number ${\chi }_b(H)$ in terms of the maximum degree $\Delta$. Our results recover those of recent work of Chakraborti for $k=2$.

arXiv comment14 pages