# Edge coloring in dense linear hypergraphs

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

• What about the hypergraph with only one edge, which is $V$? – LeechLattice Aug 12 '19 at 11:09
• Right - thanks for your observation! I want to exclude $V \in E$ and edited the post accordingly. – Dominic van der Zypen Aug 12 '19 at 11:23

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.
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.