1
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\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, 2017 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, 2017 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, 2017 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, 2017 at 15:00

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.