0
$\begingroup$

Let $H=(V,E)$ be a hypergraph. If $\kappa$ is a cardinal, we say that a map $c:E\to \kappa$ is an edge coloring if whenever $e_1,e_2\in E$ with $e_1\cap e_2\neq \emptyset$ then $c(e_1)\neq c(e_2)$. The smallest cardinal $\kappa$ such that there is an edge coloring $c:E\to \kappa$ is called the edge chromatic number of $H$, denoted by $\chi_e(H)$.

We say that $H=(V,E)$ is a dense linear hypergraph if

  1. $V \notin E$,
  2. $\bigcup E = V$,
  3. whenever $e_1\neq e_2 \in E$ then $|e_1\cap e_2| \leq 1$, and
  4. given $a\neq b\in V$ there is $e\in E$ with $\{a,b\}\in e$.

Given a positive integer $k$, is there a dense linear hypergraph $H= (V,E)$ with $V$ finite and $\chi_e(H) < 1/k\cdot |V|$?

$\endgroup$
2
  • $\begingroup$ What about the hypergraph with only one edge, which is $V$? $\endgroup$ Commented Aug 12, 2019 at 11:09
  • $\begingroup$ Right - thanks for your observation! I want to exclude $V \in E$ and edited the post accordingly. $\endgroup$ Commented Aug 12, 2019 at 11:23

1 Answer 1

2
$\begingroup$

Take a finite projective plane $π=\{P,L\}$ of order $n$, and remove all the points from a line $l$. Let the removed points be $p_1,p_2,...p_{n+1}$. The hypergraph $H$ defined by such an incidence structure has $n^2$ vertices, and every edge has $n$ elements.

Property 1 and 2 are obvious.

Property 3 follows from the fact that projective planes are linear hypergraphs.

Property 4 follows from the definition of a projective plane.

A coloring with $n+1$ colors can be obtained like so: every edge, as an edge of $π$, intersects $l$ on some point $p_k$. Assign the edge with color $k$. Two edges with the same color are disjoint in $H$, otherwise they would share two vertices in $π$: one in $H$, the other some $p_k$, contradiction.

As $n+1$ is $o(n^2)$, and projective planes with arbitrary large orders exist, $χ_e(H)<1/k⋅|V|$ is surely satisfied.

$\endgroup$

You must log in to answer this question.

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