1
$\begingroup$

Let $X\neq\varnothing$ be a set and let ${\cal E}\subseteq {\cal P}(X)\setminus\{\varnothing\}$ be a collection of non-empty subset. We say that a map $f: {\cal E}\to X$ is a chromatic self-map if

  1. $f(e) \in e$ for all $e\in {\cal E}$, and

  2. if $e_1\neq e_2 \in {\cal E}$ and $e_1\cap e_2 \neq \varnothing$, then $f(e_1)\neq f(e_2)$.

Consider for $n\in \mathbb{N}$, $n>1$ the set $[n] = \{1,\ldots,n\}$. We say that a collection ${\cal C}\subseteq {\cal P}([n])$ is complete linear if

  1. $|{\cal C}|=n$,
  2. $c\neq d \in {\cal C} \implies |c\cap d| = 1$, and
  3. $|c| > 1$ for all $c\in{\cal C}$.

Given $n>1$, does every complete linear collection on $[n]$ have a chromatic self-map?

$\endgroup$

1 Answer 1

1
$\begingroup$

By domotorp's answer https://mathoverflow.net/q/362229 to a previous question, De Bruijn-Erdos theorem characterizes complete linear collections as near-pencils or finite projective planes.

The image of a chromatic self-map is a system of distinct representatives. This is exactly the setting of Hall's marriage theorem (https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem). It is a folklore exercise that Hall's condition is satisfied for finite projective planes. And it is straightforward to define a chromatic self-map for the near-pencil.

$\endgroup$

You must log in to answer this question.

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