Skip to main content
more concise definition
Source Link

Self-colorings Injective edge choice functions in linear hypergraphs

A linear hypergraph is a hypergraph $H=(V,E)$ such that

  1. for $e\in E$ we have $|e|\geq 2$, and
  2. if $e\neq e_1\in E$, then $|e\cap e_1| \leq 1$.

AAn self-coloringinjective edge choice function of a linear hypergraph is aan injective map $f:E\to V$ such that:

  1. for all $e\in E$ we have $f(e)\in e$, and
  2. if $e\neq e_1\in E$ with $e\cap e_1\neq \emptyset$, then $f(e)\neq f(e_1)$.

for all $e\in E$ we have $f(e)\in e$.

One can verify that the hypergraph $H=(V,E)$ where $V = \{0,1,2,3\}$ andObviously, if $E = [V]^2 = \{\{a,b\}:a\neq b\in V\}$ has no self-coloring$|E|>|V|$ there cannot be such a function.

Question. If $H=(V,E)$ is a linear hypergraph with $V$ finite and $|e|\geq 3$ for all $e\in E$, does $H$ necessarily have a self-coloringan injective edge choice function?

Self-colorings in linear hypergraphs

A linear hypergraph is a hypergraph $H=(V,E)$ such that

  1. for $e\in E$ we have $|e|\geq 2$, and
  2. if $e\neq e_1\in E$, then $|e\cap e_1| \leq 1$.

A self-coloring of a linear hypergraph is a map $f:E\to V$ such that

  1. for all $e\in E$ we have $f(e)\in e$, and
  2. if $e\neq e_1\in E$ with $e\cap e_1\neq \emptyset$, then $f(e)\neq f(e_1)$.

One can verify that the hypergraph $H=(V,E)$ where $V = \{0,1,2,3\}$ and $E = [V]^2 = \{\{a,b\}:a\neq b\in V\}$ has no self-coloring.

Question. If $H=(V,E)$ is a linear hypergraph with $V$ finite and $|e|\geq 3$ for all $e\in E$, does $H$ necessarily have a self-coloring?

Injective edge choice functions in linear hypergraphs

A linear hypergraph is a hypergraph $H=(V,E)$ such that

  1. for $e\in E$ we have $|e|\geq 2$, and
  2. if $e\neq e_1\in E$, then $|e\cap e_1| \leq 1$.

An injective edge choice function of a linear hypergraph is an injective map $f:E\to V$ such that:

for all $e\in E$ we have $f(e)\in e$.

Obviously, if $|E|>|V|$ there cannot be such a function.

Question. If $H=(V,E)$ is a linear hypergraph with $V$ finite and $|e|\geq 3$ for all $e\in E$, does $H$ necessarily have an injective edge choice function?

Source Link

Self-colorings in linear hypergraphs

A linear hypergraph is a hypergraph $H=(V,E)$ such that

  1. for $e\in E$ we have $|e|\geq 2$, and
  2. if $e\neq e_1\in E$, then $|e\cap e_1| \leq 1$.

A self-coloring of a linear hypergraph is a map $f:E\to V$ such that

  1. for all $e\in E$ we have $f(e)\in e$, and
  2. if $e\neq e_1\in E$ with $e\cap e_1\neq \emptyset$, then $f(e)\neq f(e_1)$.

One can verify that the hypergraph $H=(V,E)$ where $V = \{0,1,2,3\}$ and $E = [V]^2 = \{\{a,b\}:a\neq b\in V\}$ has no self-coloring.

Question. If $H=(V,E)$ is a linear hypergraph with $V$ finite and $|e|\geq 3$ for all $e\in E$, does $H$ necessarily have a self-coloring?