0
$\begingroup$

This question is motivated by considerations on conflict-free colorings, which arose while studying assignment problems for frequencies in cellular networks.

A hypergraph $H=(V,E)$ is said to be linear if for all $e_1\neq e_2 \in E$ we have $|e_1\cap e_2| \leq 1$.

Let $H=(\omega, E)$ be a linear hypergraph such that $e$ is infinite for all $e\in E$. Is there a necessarily a map $c: \omega\to \{0,1\}$ such that for all $e\in E$ there is $v^*\in e$ such that $$c^{-1}\big(\big\{c(v^*)\big\}\big) \cap e \;= \;\{v^*\}\;\;?$$

(More informally, we want every edge $e\in E$ to have a vertex $v^*\in e$ such that all the vertices in $e\setminus\{v^*\}$ are colored with the (unique) color in $\{0,1\}\setminus\{c(v^*)\}$.)

$\endgroup$

1 Answer 1

1
$\begingroup$

Let $V$ be the set of points in the affine plane $\mathbb Q^2$, and $E$ be the set of lines.

Assume that the coloring is possible. Say a line is white if it contains a unique black point, and black otherwise.

There exist two white points (on two parallel lines), hence a white line through them. There exists a white point outside that line, hence infinitely many white lines concurrent at that white point (and passing through white points on the found line). Similarly, take infinitely many black lines concurrent at a black point.

Take 5 white and 5 black lines out of those collections; they have at least 20 points of mutual intersection. But at most 5 of those points are black (one per white line), and at most 5 are black. A contradiction.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .