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

  • $\begingroup$ What about the hypergraph with only one edge, which is $V$? $\endgroup$ 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$ Aug 12, 2019 at 11:23

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.