0
$\begingroup$

Let $H=(V,E)$ be a hypergraph, let $n\in\mathbb{N}$. A vertex coloring is a map $c: V\to \{1,\ldots, n\}$ such that for $v\neq w \in V$ we have $c(v)\neq c(w)$ whenever there is $e\in E$ such that $v, w\in e$. We call the least $m\in\mathbb{N}$ such that there is a coloring map from $V$ to $\{1,\ldots,m\}$ the chromatic number $\chi(H)$ of $H=(V,E)$.

If $|e| = n$ for all $e\in E$ we say that $H=(V,E)$ is $n$-regular.

Let $n\in\mathbb{N}$. What is the maximum chromatic number that an $n$-regular hypergraph $H=(V,E)$ with $|E|=n$ can have?

$\endgroup$
  • $\begingroup$ Some lower bound. Take a prime power $q$, take $q^2+q+1$ sets of order $q$ and one more vertex. The edges form a projective plane on the sets, and each edge contains an extra vertex. Thus there are $n=q^2+q+1$ edges of order $n$, and $q^3+q^2+q+1$ vertices, al should be of different colors. Thus the chromatic number should be at least of orde $n^{3/2}$. $\endgroup$ – Ilya Bogdanov Nov 15 '16 at 8:54
  • $\begingroup$ Very nice, thanks Ilya! Of course, a trivial upper bound is $\chi(H) \leq n^2$, but so far I haven't had a lower bound as good as yours. $\endgroup$ – Dominic van der Zypen Nov 15 '16 at 9:02
3
$\begingroup$

The answer is $n^{3/2}(1+o(1))$.

For the upper bound, observe that there are at most $n\cdot{n\choose 2}$ pairs of vertices lying in one edge. Thus, if $|V|>n^{3/2}(1+o(1))$, then there are two vertices not belonging to an edge, and we may identify them harmlessly (they will be of the same color). Repeating the procedure, we eventually get at most $n^{3/2}(1+o(1))$ vertices, so this number of colors suffices.

The lower bound (from the comment above). Take a prime power $q$, take $q^2+q+1$ sets of order $q$ and one more vertex. The edges form a projective plane on the sets, and each edge contains an extra vertex. Thus there are $n=q^2+q+1$ edges of order $n$, and $q^3+q^2+q+1$ vertices, all these vertices should be of different colors. Thus the chromatic number should be at least of orde $n^{3/2}$.

This works only for special $n$, surely, but the prime powers are dense enough to provide the lower bound of the form $n^{3/2}(1+o(1))$ for all values of $n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.