Given a hypergraph $H=(V,E)$ we let its intersection graph $I(H)$ be defined by $V(I(H)) = E$ and $E(I(H)) = \{\{e,e'\}: (e\neq e'\in E) \land (e\cap e'\neq \emptyset)\}$.

A linear hypergraph is a hypergraph $H=(V,E)$ such that every edge has at least $2$ elements and for all $e\neq e'\in E$ we have $|e\cap e'|\leq 1$.

It turns out that for every simple undirected graph $G$, finite or infinite, there is a linear hypergraph $H$ such that $I(H)\cong G$. The linear intersection number $\ell(G)$ of a graph $G$ is the smallest cardinal $\kappa$ such that there is a linear hypergraph $H=(\kappa,E)$ such that $I(H)\cong G$.

Question. Is there an infinite graph $G$ such that $\ell(G) < \chi(G)$?

Note. For finite graphs, the answer to this question is not known.


1 Answer 1


The answer is no. This is equivalent to stating that for any linear hypergraph $H=(\kappa,E)$ with $\kappa$ infinite (note that for $\kappa$ finite, $G=I(H)$ would be finite), we have $\chi(I(H))\leq\kappa$. This follows immediately once we show $|V(I(H))|=|E|\leq\kappa$.

For $\alpha<\kappa$ let $E_\alpha=\{e\in E:\alpha\in e\}$. If we remove $\alpha$ from every element of $E_\alpha$ we get a family of disjoint subsets of $\kappa$. By considering their least elements, it's clear there are at most $\kappa$-many of them, i.e. $|E_\alpha|\leq\kappa$. Therefore $$|E|\leq\sum_{\alpha<\kappa}|E_\alpha|\leq\kappa^2=\kappa.$$


Your Answer

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

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