The Smallest Uniform Color-Bounded Hypergraphs Which are One-Realizations of a Given Set.

A color-bounded hypergraph is a hypergraph with vertex set X and edge set $${\mathcal {E}}=\{E_1,E_2,\dots ,E_m\}$$ , together with integers $$s_i$$ and $$t_i$$ ( $$1\le s_i\le t_i\le |E_i|$$ ) for $$i=1,2,\ldots ,m$$ . A vertex coloring $$\varphi $$ is proper if the number of colors occurring in edge $$E_i$$ satisfies $$s_i\le |\varphi (E_i)|\le t_i$$ , for every $$1\le i\le m$$ . If $$s_i=s$$ and $$t_i=t$$ for all i, we simply denote the color-bounded hypergraph by $${\mathcal {H}}=(X, {\mathcal {E}},s,t)$$ . A set of positive integers $$\Phi (\mathcal {H})$$ is called feasible, if it consists of all k for which there exists a proper coloring of $$\mathcal {H}$$ using precisely k colors. Chromatic spectrum of a hypergraph $$\mathcal {H}$$ is a vector with each entry $$r_k$$ equal to the number of partitions of vertex set induced by all proper colorings using k colors. Let S be a finite set of positive integers. A color-bounded hypergraph is a one-realization of S if its feasible set is S and each entry of its chromatic spectrum is either 0 or 1. In this paper, we determine the minimum number of vertices of r-uniform color-bounded hypergraphs $${\mathcal {H}}=(X, {\mathcal {E}},2,t)$$ which are one-realizations of S for the case when $$\lceil \frac{r}{2}\rceil <t\le r-2$$ and $$\max (S)\ge \frac{3r}{2}$$ . [ABSTRACT FROM AUTHOR]