Balanced independent sets and colorings of hypergraphs

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 $\mathrm{\mid }{V}_i\mathrm{\mid }=n$ for each $i$. An independent set $I$ in $H$ is balanced if $\mathrm{\mid }I\cap V_i\mathrm{\mid }=\mathrm{\mid }I\cap V_j\mathrm{\mid }$ 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=\mathrm{\mid }E\mathrm{\mid }\mathrm{/}n$, and an upper bound on the balanced chromatic number ${\chi }_b(H)$ in terms of the maximum degree $\mathrm{\Delta }$. Our results recover those of recent work of Chakraborti for $k=2$.