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
$\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$

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.