A linear hypergraph is a pair $\pi=(\{1,\ldots,n\}, L)$ where $n\in\mathbb{N}$, $n\geq 2$ and $L\subseteq {\cal P}(X)$ has the following properties:

  1. for $e\in L$ we have $|e|\geq 2$;
  2. if $e_1\neq e_2 \in L$ then $|e_1\cap e_2|\leq 1$.

We call $\pi = (\{1,\ldots,n\}, L)$ projective if for all $x, y\in \{1,\ldots,n\}$ there is $e\in L$ such that $\{x,y\}\subseteq e$. The graph $G_\pi$ associated to a linear hypergraph $\pi$ is given by $G=(V,E)$ where $V = L$ and $E = \{\{e_1, e_2\} \subseteq L: e_1\neq e_2\text{ and } e_1\cap e_2\neq \emptyset\}$.

Question. Is there a non-projective hypergraph $\pi=(\{1,\ldots,n\}, L)$ such that $G_\pi$ cannot be colored with $n-1$ colors?

  • $\begingroup$ Do you mean "$P(X) = X = \{0,1,\dots\}$"? Also, when you define "projective," do you mean "(unique) $e \in L$"? $\endgroup$ – Yuichiro Fujiwara Feb 7 '17 at 16:33
  • $\begingroup$ By ${\cal P}(X)$ I mean the power set (set of subsets) of $X$. I didn't understand your other question. $\endgroup$ – Dominic van der Zypen Feb 8 '17 at 6:23
  • 1
    $\begingroup$ Ah, there is a typo in my previous comment. But I take your reply as meaning that the undefined set $X$ is actually $X = \{1,\dots,n\}$ (i,e., $\pi = (X, L)$), am I correct? As for the latter half of my previous comment, you define projective by using $E$, which is only defined later on when you introduce the graph $G_{\pi}$. That's why I thought you might mean $e \in L$ instead $e \in E$. $\endgroup$ – Yuichiro Fujiwara Feb 8 '17 at 10:38
  • $\begingroup$ Oh I see -- I will correct this, thank you for pointing out my error! Also, the $E$ mentioned in the definition of projective should be $L$, as in the definition of $\pi = (\{1,\ldots, n\}, L)$. $\endgroup$ – Dominic van der Zypen Feb 8 '17 at 15:00

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.