Polychromatic colorings of hypergraphs with high balance

1.   Introduction

This work is inspired by recent developments concerning hypergraph vertex cover, disjoint edge cover of hypergraph, the longest lifetime problem for a wireless sensor network (WSN) with battery-limited sensors. A $hypergraph$ $H = (V, E)$ consists of a ground set $V$ of $vertices$ and a collection $E$ of $hyperedges$, where each hyperedge $f \in E$ is a subset of $V$. Let $m$ be a positive integer. A $polychromatic$ $m$-$coloring$ of a hypergraph $H$ is a coloring of vertices of $H$ with $m$ colors such that every hyperedge contains at least one vertex of each color. It is a generalization of 2-colorings of a hypergraph. Obviously, in a polychromatic coloring of hypergraph $H$, each color class is exactly a vertex cover of $H$. The polychromatic number of a hypergraph $H$ is the maximum number $m$ that $H$ admits a polychromatic $m$-coloring and is denoted by $p(H)$.

The $rank$ of a hypergraph $H$ is $R(H) = \max_{f\in E}|f|$, the $anti$-$rank$ of $H$ is $S(H) = \min_{f\in E}|f|$. If $R(H) = S(H) = d$, that is, the size of every hyperedge in $H$ is $d$, we say that the hypergraph $H$ is a $d$-$uniform$ $hypergraph$. The $degree$ of a vertex $v\in V(H)$ is the number of hyperedges containing $v$ in $H$, and is denoted by $d_{H}(v)$ or simply by $d(v)$. The $maximum$ $degree$, $minimum$ $degree$, of $H$ is $\Delta(H) = \max_{v\in V(H)}d_{H}(v)$, $\delta(H) = \min_{v\in V(H)}d_{H}(v)$, respectively. A hypergraph in which each vertex has degree $d$ is called a $d$-$regular$ $hypergraph$. Throughout this paper, we denote the class of $d$-$regular$ $d$-$uniform$ $hypergraphs$ by $\mathcal{H}_{d}$. Let $f$ be a hyperedge in a hypergraph with anti-rank $S$. The operation $shrinking$ $f$ means to replace it with some $f'\subset f$. This operation is useful when considering polychromatic colorings of hypergraphs with the probabilistic method because it bounds the dependence degree. We could shrink each hyperedge $f_j$ with $|f_j| > S$ to $f_j'$ such that $|f_j'| = S$. Clearly, undoing shrinking preserves the property of being a hyperedge containing $m$ colors. (For each hyperedge $f_j'$, its coloring is dependent on the colorings of its incident hyperedges. So its dependence degree is at most $S(\Delta-1)$.) Since each hypergraph $H$ with anti-rank $S = 1$ has $p(H) = 1$, we focus on the hypergraphs with anti-rank $S\geq 2$ throughout this paper.

A subfamily $E_i$ of $E$ in a hypergraph $H = (V, E)$ is called a $cover$ in $H$ if $\cup_{f\in E_i}f = V$. A $cover$ $m$-$decomposition$ of a hypergraph $H$ is a partition of $E$ into $m$ covers in $H$, i.e. $E = \uplus_{i = 1}^{m}E_i$ and $\cup_{f\in E_i}f = V$. The maximum integer $m$ such that the hypergraph $H$ admits a cover $m$-decomposition is called the $cover$-$decomposition$ $number$ of $H$ and denoted by $\mathrm{cd}(H)$. The problem to determine the cover decomposition numbers of hypergraphs is called the maximum disjoint set cover problem (DSCP), which is $NP$-complete ^[8]. A hypergraph $H$ can model a collection of sensors, with each hyperedge $f\in E$ corresponding to a sensor which can monitor the vertices (targets) in $f\subseteq V$. Since monitoring all vertices (targets) of $V$ takes a cover in $H$, $\mathrm{cd}(H)$ is exactly the longest lifetime for a WSN corresponding to the hypergraph $H$ if each sensor can only be turned on for a single time unit (^[3,7]).

Let $H = (V, E)$ be a hypergraph with $V = \{x_1, x_2, \ldots, x_n\}$ and $E = (f_1, f_2, ..., f_m)$. The $dual$ of $H$ is a hypergraph $H^*$ whose vertices $\hat{f}_1, \hat{f}_2, ..., \hat{f}_m$ correspond to the hyperedges of $H$, and whose hyperedges $\hat{x}_i = \{ \hat{f}_j|\: x_i\in f_j$ in$\ H \}$, $i = 1, 2, \ldots, n$. Clearly, $(H^*)^* = H$ and $\Delta(H^*) = R(H)$, $\delta(H^*) = S(H)$, $R(H^*) = \Delta(H)$, $S(H^*) = \delta(H)$.

Let $p_k(H^*)$ denote the maximum $m$ such that $H^*$ admits a polychromatic $m$-coloring satisfying that each color appears at least $k$ times on each hyperedge and $\mathrm{cd}_k(H)$ denote the maximum $m$ such that $H$ has a cover $m$-decomposition satisfying that each cover contains at least $k$ incident edges of each vertex. Clearly $\mathrm{cd}_k(H) = p_k(H^*)$.

Early in the 1970s, Erdős and Lovász ^[10] considered the existence of polychromatic colorings of hypergraphs and showed that, for each integer $m\geq 2$, every hypergraph with anti-rank $S\geq m$ and each of whose hyperedges intersecting at most $m^{S-1}/(4(m-1)^S)$ other hyperedges is polychromatic $m$-colorable. (The original version is formed on $S$-uniform hypergraphs. Via the operation "shrinking", it is easy to see that it could be stated with a slight generalization as above.) Moreover, for lattice point hypergraphs, Erdős and Lovász ^[10] gave a stronger version in which the existence of polychromatic colorings with high balance is guaranteed: For $\epsilon > 0, m > 2, n > 1$, there is an $r_0 = r_0 (m, \epsilon)$ such that if $T$ is any set of lattice points in the $n$-dimensional space with $|T| = S > r_0$ then the lattice points can be $m$-colored so that each set $T+\textbf{a}$ obtained by translating $T$ with an integer vector $\textbf{a}$ contains at least $(1-\epsilon) \frac{S}{m}$ points of any given color.

Henning and Yeo ^[13] considered polychromatic colorings of hypergraphs in $\mathcal{H}_{d}$ and showed every hypergraph $H\in\mathcal{H}_{d}$ ($d\geq 2$) has a polychromatic $m$-coloring for each $m\leq\frac{d}{\ln(d^3)}$. Using a randomized algorithm, Bagaria, Pananjady and Vaze ^[3] gave a $\ln n$ approximation result in polynomial time that each hypergraph $H$ with $n$ hyperedges and anti-rank $S$ has $p(H)\geq S(1-o(1))/\ln n$. For hypergraphs $H$ with maximum degree at most $\Delta$ and anti-rank at least $S$, Li and Zhang ^[17] gave a lower bound $\lfloor {S}/{\ln (c \Delta S^{2})}\rfloor$ for the polychromatic number of hypergraphs, where $0 < c = c(\Delta, S) < 1.5582 < e$, and, for polychromatic colorings with high balance, they showed that $H$ has a polychromatic $m$-coloring such that every hyperedge in $H$ contains at least $\lfloor\ln(e\Delta S^{2})\rfloor$ vertices of each color for each $m \leq \frac{S }{\ln(e\Delta S^{2})}$.

Given a plane graph $G$, a $face$ $hypergraph$ $\mathcal{F}(G)$ based on $G$ is one whose vertex set is $V(G)$ and whose hyperedges are the vertex sets of $G$'s faces. By virtue of the four-color theorem, Mohar and Škrekovski ^[19] proved that every simple plane graph is polychromatic 2-colorable. Later Bose et al. ^[6] proved this result without the use of the four-color theorem. For a family $\mathcal{H}$ of face hypergraphs with anti-rank $S$, Alon et al. ^[1] showed that $\lfloor\frac{3S-5}{4}\rfloor\leq \min_{ H\in \mathcal{H}} \{p(H)\} \leq \lfloor\frac{3S+1}{4}\rfloor.$ A $factor$ $hypergraph$ $\mathcal{H_F}(G)$ based on $G$ is one whose vertex set is $E(G)$ and whose hyperedges are the edge sets of $G$'s $F$-factors. Axenovich et al. ^[2] determined the polychromatic number for the 1-factor hypergraph $\mathcal{H}_1(K_n)$ and bounded the polychromatic number for the 2-factor hypergraph $\mathcal{H}_2(K_n)$ and the Hamilton-cycle-factor hypergraph $\mathcal{H}_{C_n}(K_n)$.

On 2-colorings of hypergraphs, Vishwanathan ^[21] showed that, for each integer $d\geq 4$, every hypergraph in $\mathcal{H}_{d}$ is $2$-colorable. The bound for $d$ is sharp noting that Fano plane is in $\mathcal{H}_{3}$ but not $2$-colorable. Henning and Yeo ^[13] discussed 2-coloring with high balance for the hypergraphs in $\mathcal{H}_{d}$ and observed that, for each integer $k\geq 2$, every hypergraph $H\in\mathcal{H}_{d}$ has a $2$-coloring such that each hyperedge contains at least $k+1$ vertices of each color if one of the following conditions holds: $(i)$ $k\leq d/2-\sqrt{d\ln(d\sqrt{2 e})};$ $(ii)$ $d\geq2 k+3\sqrt{k\ln(k)}+44.03;$ $(iii)$ $d\geq2 k+4\sqrt{k\ln(k)}+14.04.$ Beck and Fiala ^[4] showed that every hypergraph with maximum degree $\Delta\geq 2$ has a $2$-coloring such that each hyperedge $f\in E$ contains at least $|f|/2-\Delta+1$ vertices of each color. Chen, Du and Meng ^[9] gave a sufficient condition, each hyperedge meets at most $2^S/(e(S+1))-2$ other hyperedge, to show a hypergraph with anti-rank $S\geq 4$ having a 2-coloring such that each color appears at least two times on each hyperedge.

There is much literature on cover decomposition number of (multi)graphs, using edge coloring method of (multi)graph. Gupta ^[11] showed every multigraph has a cover decomposition into at least $\min_{v\in V(G)}\{d(v)-\mu(v)\}$ covers, where $\mu(v) = \max_{u\in N(v)} |E(uv)|$. In ^[12], Gupta confirmed that each multigraph with minimum degree $\delta$ has a cover $\lfloor {(3\delta+1)}/{4}\rfloor$-decomposition. Hilton ^[14] discussed cover decomposition of multigraphs such that each cover contains at least $j$ incident edges of each vertex. Let $V_k = \{v\in V: k|d(v)\}$. Hilton and de Werra ^[15] showed every graph $G$ with $V_k$ independent has a cover $m$-decomposition such that each cover contains either $\lceil d(v)/m\rceil$ or $\lfloor d(v)/m\rfloor$ incident edges of each vertex $v\in V(G)$. Zhang and Liu ^[25] extended the conclusion to graphs $G$ with $G[V_k]$ forests and, furthermore, peelable graphs $G$. Let $g$ be a positive integer function defined on $V(G)$ such that $g(v)\leq d(v)$ for each $v\in V(G)$. Song and Liu ^[20] considered DSCP of multigraphs satisfying that each cover contains at least $g(v)$ incident edges for each vertex $v\in V(G)$, $g$-cover decomposition for short, and obtained a result with a form analogous to Gupta's one in ^[11]. Ma and Zhang ^[18] determined $\mathrm{cd}_g(G)$ for a class of graphs which extends the class of peelable graphs. Xu and Liu ^[23] discussed DSCP for multigraphs with $2\leq \delta \leq 5$. Zhang and Zhang ^[26] considered DSCP for nearly bipartite graphs. A graph $G$ is called $g$-critical on DSCP, if $\mathrm{cd}_g(G+uv)\geq \mathrm{cd}_g(G)$ for each pair of nonadjacent vertices $u, v$. Xu and Liu ^[22] gave some properties of 1-critical graphs on DSCP. Zhang ^[24] described completely disconnected $g$-critical graphs.

Bollobás et al. ^[5] researched cover decompositions of hypergraphs. We state their result in dual version: Let $\mathcal{H}$ be a family of hypergraphs with maximum $\Delta$ and anti-rank $S$. Then

$\rm(i)$ for all $\Delta$, $S$ and each $H\in \mathcal{H}$, $p(H) \geq S/(\ln \Delta + O(\ln \ln \Delta))$;

$\rm(ii)$ for all $\Delta \geq 2$, $S \geq 1$, $\min_{H\in \mathcal{H}} \{p(H) \}\leq \max\{1, O(S/\ln \Delta)\}$;

$\rm(iii)$ for each sequence $\Delta$, $S \rightarrow \infty$ with $S = \omega (\ln \Delta)$, $\min_{H\in \mathcal{H}} \{p(H) \} \leq (1+o(1))S/\ln (\Delta)$.

In Section 2, we will prove the following result, which extends the result due to Bagaria, Pananjady and Vaze ^[3] to polychromatic colorings with high balance.

Theorem 1.1. Let $n, S, k$ be three positive integers and $H$ be a hypergraph with $n$ hyperedges and anti-rank $S$.

(i) If $k$ is a fixed positive integer, then $p_k(H)\geq {S(1-o(1))}/{(2\ln n)}$.

(ii) If $k = O(\ln(n\ln n))$, then $p_k(H)\geq {S}/{O(\ln n)}$.

(iii) If $k = \omega(\ln(n\ln n))$, then $p_k(H)\geq {S(1-o(1))}/{((2+\sqrt{3})k)}$.

2.   The proof of the main result

Within the proof, we shall make use of the following classical tool of the probabilistic method–the Chernoff Bound. Let $X_1, X_2, \ldots, X_s$ be mutually independent Bernoulli variables such that $X_i = 1$ with probability $p$ and $X_i = 0$ with probability $1-p$. Define $X = \sum_{i = 1}^{s} X_i$. Clearly, $E(X) = \sum_{i = 1}^{s} E(X_i) = sp$.

Theorem 2.1. ^[16](The Chernoff Bound) For any $0 \leq t \leq sp$, $Pr(X > sp + t) < e^{- \frac {t^2}{3sp}}$ and $Pr(X < sp - t) < e^ {- \frac{t^2} {2sp}}\leq e^{ -\frac{t^{2}}{3sp}}$.

The proof of Theorem 1.1

Proof. By virtue of the operation $shrinking$, we can always assume that $H$ is $S$-uniform.

Let $n$ be large enough and $\mathcal{C} = \{1, 2, \ldots, h\}$ be a color set. Color the vertices of $H$ in such a way that each vertex is independently and uniformly assigned a color of $\mathcal{C}$. For $f\in E$, $c\in \mathcal{C}$, define $A_{f, c}$ to be the "bad" event that color $c$ appears at most $k-1$ times on hyperedge $f$. We want to avoid these "bad" events and achieve a polychromatic $m_k$-coloring with $m(\leq h)$ as large as possible. If we can show that with positive probability, each of $m$ colors appears at least $k$ times on every hyperedge, then we will be done. Let $X_{f, c}$ be the number of vertices colored with $c$ on the hyperedge $f$. Then $E(X_{f, c}) = S/h$. Clearly, for each pair of $f\in E$ and $c\in \mathcal{C}$,

and $\frac{S}{h}-k\leq \frac{S}{h}$. If $\frac{S}{h}-k\geq 0$, by the Chernoff Bound, the probability of event $A_{f, c}$ is the following.

An invalid color is one which appears at most $k-1$ times in some hyperedge of $H$. Let $L$ be the number of invalid colors in a random uniform $h$-coloring of $H$ as described as above. Then the expectation of $L$

Next, we discuss three cases according to the value of $k$, corresponding to which the function $h$ will vary.

(ⅰ) $k$ is a fixed positive integer.

Set $h = \frac{S}{2\ln(n\ln n)}$. Clearly, $\frac{S}{h}-k\geq 0$ as $n$ is large enough. By Inequality (2), for each pair of $f\in E$ and $c\in \mathcal{C}$,

Then

Thus, with positive probability, we can get a coloring of $H$ with at least $h-E(L)$ colors such that each of the colors appears at least $k$ times on each hyperedge of $H$. That is to say,

(ⅱ) $k = O(\ln(n\ln n))$.

Then there exists a positive constant, say $d$, such that $k\leq d\ln(n\ln n)$ for large enough $n$. Set $h = \frac{S}{(d+\sqrt{2d+1}+1)\ln(n\ln n)}$. Clearly, $\frac{S}{h}-k > 0$. By Inequality (1), for each pair of $f\in E$ and $c\in \mathcal{C}$,

So $E(L) < hn(n\ln n)^{-1} = h/\ln n$ and then there is

(ⅲ) $k = \omega(\ln(n\ln n)).$

In this case, set $h = \frac{S}{(2+\sqrt{3})k}$. Clearly, $\frac{S}{h}-k > 0$. By Inequality (1), for each pair of $f\in E$ and $c\in \mathcal{C}$,

Then $E(L) < h/\ln n$ and

3.   Concluding remarks

Bagaria, Pananjady and Vaze ^[3] gave the following result for hypergraphs with $n$ hyperedges.

Theorem 3.1. ^[3] Let $H$ be a hypergraph with $n$ hyperedges and $anti$-$rank$ $S$. Then $p(H)\geq S(1-o(1))/\ln n$.

From the proof of Theorem 1.1 (ⅱ), we can deduce the following result.

Corollary 3.2. Let $n, S, k$ be three positive integers and $d$ be a positive real. Let $H$ be a hypergraph with $n$ hyperedges and anti-rank $S$. If $k\leq d\ln(n\ln n))$, then $p_k(H)\geq \frac{S}{(d+\sqrt{2d+1}+1) \ln n} (1-o(1))$. In particular, if $k\leq \ln(n\ln n))$, then $p_k(H)\geq \frac{S}{(2+\sqrt{3}) \ln n} (1-o(1))$.

Let $A$ be a nonempty set. An $equitable$ $q$-$partition$ of $A$ is a collection $A_1, A_2, \ldots, A_q$ such that, for each $1\leq i < j\leq q$, $A_i\cap A_j = \emptyset$, $||A_i|-|A_j||\leq 1$ and $\cup_{1\leq i\leq q}A_i = A$. The operation $equitable$ $q$-$splitting$ a hyperedge $f$ in a hypergraph means to replace $f$ with an equitable $q$-partition of $f$. Let $H$ be a hypergraph with $n$ hyperedges and anti-rank $S$. Do an equitable $k$-splitting for each hyperedge of $H$ and denote the resulting hypergraph by $H_k$. Clearly, $H_k$ has $kn$ hyperedges and $S(H_k) = \lfloor S/k\rfloor$. By Theorem 3.1, there is $p(H_k)\geq {\lfloor \frac{S}{k}\rfloor(1-o(1))}/{\ln (kn)}$. It is easy to see that a polychromatic $m$-coloring of $H_k$ is corresponding to a polychromatic $m_k$-coloring of $H$. So undoing equitable $k$-splitting could get a lower bound for $p_k(H)$, which is at most ${S(1-o(1))}/{(k\ln (kn))}$. Obviously, for each $k\geq 2$, the lower bound shown in Theorem 1.1 is better.

By the dual relationship of $H$ and $H^{\ast}$, we have the following result on cover decomposition of a hypergraph with high balance.

Theorem 3.3. Let $n, \delta, k$ be three positive integers and $H$ be a hypergraph with $n$ vertices and minimum degree $\delta$.

(i) If $k$ is a fixed positive integer, then $\mathrm{cd}_k(H)\geq \delta(1-o(1))/(2\ln n)$.

(ii) If $k = O(\ln(n\ln n))$, then $\mathrm{cd}_k(H)\geq \delta/O(\ln n)$.

(iii) If $k = \omega(\ln(n\ln n))$, then $\mathrm{cd}_k(H)\geq \delta(1-o(1))/((2+\sqrt{3})k)$.

Acknowledgments

The authors would like to thank the referees for careful reading and valuable comments.

This work is supported by the Shandong Provincial Natural Science Foundation (Grant No. ZR2019MA032), the National Natural Science Foundation of China (Grant No.11701342) of China.

Conflict of interest

All authors declare that there is no conflict of interest.