Let $n>1$ be an integer and set $[n]:=\{1,\ldots,n\}$. We say that ${\scr L}\subseteq {\cal P}([n])$ is a linear intersection structure if for all $L_1\neq L_2\in {\scr L}$ we have $|L_1\cap L_2|\leq 1$. For any positive integer $k$ we call a map $c:{\scr L}\to [k]$ a coloring if $c(L_1)\neq c(L_2)$ whenever $L_1\neq L_2\in {\scr L}$ have the property that $L_1\cap L_2 \neq \emptyset$. In that case we say that ${\scr L}$ is $k$-colorable.

Suppose that ${\scr L}$ is a linear intersection structure on $[n]$ and that ${\scr L}$ is not $(n-1)$-colorable. If $|L|>2$ for all $L\in{\scr L}$, does this imply that for any $L_1, L_2\in {\scr L}$ we have $|L_1|=|L_2|$?

  • $\begingroup$ Certainly there are at least $n$ lines. Do you know any examples with more than $n$ lines? If there are just $n$ lines then every pair of lines share a point. Do you know any examples with $n$ lines and some pair of points not on a common line? Otherwise (since every line has at least three points) the structure is a finite projective plane: $n=k^2+k+1$ for some $k$ and all lines are incident with $k+1$ points and vice versa. $\endgroup$ – Aaron Meyerowitz Apr 27 at 6:35
  • $\begingroup$ @AaronMeyerowitz you may replace any line by two (or more) disjoint subsets. The number of lines increases of course. But this is $(n-1)$-colorable. $\endgroup$ – Fedor Petrov Apr 27 at 11:40
  • $\begingroup$ @FedorPetrov Yes, I was only asking about the case that it takes at least $n$ colors. If there are $m$ lines one can make a graph on $m$ points with edges indicating intersection. It is given that this graph has chromatic number at least $n$. One way to force that is if it has an $n$-clique. Of course the chromatic number of a graph can exceed the clique number. But can that happen with a graph derived from a linear intersection structure on $n$ points? $\endgroup$ – Aaron Meyerowitz Apr 27 at 13:29

If the answer to your question is "yes," then that would imply the famous (and still unresolved) Erdős–Faber–Lovász conjecture.

The EFL conjecture states (in the language of linear hypergraphs) that if $\mathcal{L} \subseteq 2^{[n]}$ has any two of its members intersecting in at most one point, then $\mathcal{L}$ can be colored with at most $n$ colors.

If EFL is false, then we could take a linear hypergraph with edge chromatic number larger than $n$ and split one of its edges into two disjoint pieces to get a non-uniform family that cannot be colored with $n-1$ colors. (This splitting suggested in a comment to OP)

So, the answer is either 'no' or the question is very hard.

  • $\begingroup$ You show that if EFL is false then the answer to the OP as asked is no, not yes. But if EFL is true that just means that the we can assume any possible example of “no” has chromatic number $n.$ $\endgroup$ – Aaron Meyerowitz Apr 30 at 5:25
  • 1
    $\begingroup$ What you are describing as the EFL conjecture doesn’t seem the same as what I find. $\endgroup$ – Aaron Meyerowitz Apr 30 at 6:47
  • $\begingroup$ @AaronMeyerowitz, (1) my statement is "If OP is yes, this would imply EFL." I agree that if EFL were proven true, this would not resolve OP's problem (and I did not claim as much). (2) EFL has a handful of equivalent versions. See faculty.math.illinois.edu/~west/regs/efl.html $\endgroup$ – Pat Devlin May 6 at 2:40
  • $\begingroup$ Before getting into the implications, doesn’t EFL say that if $n$ points are each incident with $n$ lines then $n$ colors suffice to color the lines so that intersecting lines have distinct colors? That doesn’t seem close to what you said. $\endgroup$ – Aaron Meyerowitz May 6 at 17:33
  • $\begingroup$ No, definitely not (it would certainly be easy to prove if there were at most $n$ lines). It’s “if we have a collection of ‘lines’ on $n$ points such that two lines share at most one point, then the lines can be colored with at most $n$ colors so that intersecting lines get different colors.” But it’s equivalent to a lot of other things. $\endgroup$ – Pat Devlin May 8 at 16:07

I think the answer is yes simply because the only examples are finite projective planes.

Do you know otherwise? Is this what you suspect? If so, why not ask that?

Let me recast things in another way: Say that there is a set of lines $\mathcal{L}=\{L_1,\cdots L_m\}$, a set of points $\mathcal{P}=\{p_1,\cdots,p_n\}$, and a relation of incidence between points and lines.

Your key requirement for a linear intersection structure (LIS) is:

  • There are never two lines $L,L'$ and two points $p,p'$ with both points incident with both lines.

Because of the symmetry one sees that roles of points and lines can be swapped giving another LIS. We will not be bothered, though, by saying two lines intersect when we mean that there is a point incident to both.

Here are two stronger conditions, either of which implies that a system is a LIS:

  • Every two points determine exactly one line.

  • Every two lines intersect at exactly one point.

Those which satisfy the first condition are called linear spaces (of the geometric variety) and are known to always have $n \leq m.$

Those satisfying the second could be called dual-linear spaces.

Here is a troublesome example satisfying both. A pencil consists of $n$ lines and $n$ points with $l_i$ incident with just $p_i$ and $p_n$ except that $l_n$ is incident with exactly $p_1,\cdots,p_{n-1}.$ Note that it is self dual. The coloring number is $n$ but the line size is not uniform.

One way to exclude this is, as you do, saying that every line is incident with at least $3$ points. A gentler one is to simply state that there are is some set of $4$ points no three co-linear. See if you can prove that that alone is enough to make all lines the same size (given linear and dual linear).

DO you have any bad examples in mind other than pencils which have line coloring number $n$ , non-uniform line size? If not, why not use the less exclusive definition.

For a linear space $n\leq m$ while for a dual linear space $m \leq n$ so for one satisfying both, $n=m.$

It is known that for spaces satisfying both conditions along with the $4$ point condition, there is a $q$ with $n=m=q^2+q+1,$ All lines are incident with $q+1$ points and each point is incident with $q+1$ lines.

SO if your conditions force a projective plane then, yes, all the lines have the same size.

To back up, The coloring number can be defined via a graph with $m$ nodes with edge $u_iu_j$ if the corresponding lines intersect. Your condition is that this graph has chromatic number at least $n.$ One way to force this is to have a clique of size $n$, i.e. $n$ pairwise intersecting lines. In that case we could drop any other lines and still have a LIS with coloring number $n$ although perhaps this is uniform while the larger one wasn't.

Here is something I feel like I have seen but I can't find any reference:

  • A set of $n$ pairwise intersecting lines on $n$ points is a projective plane or a pencil.

This leaves the case of clique number less than $n$ and coloring number perhaps greater than $n$ but certainly no smaller.

Can this happen? I doubt it.

If we drop one incident point from one line in a projective plane the number of points is $n^2+n$ and the number of lines is still $n^2+n+1$ However the coloring number goes don to $n^2+n$

What can we say about graphs with clique number $\kappa$ and coloring number $\kappa+1$ or more? Specifically, what is a lower bound on the number of lines (we only care about ones coming from LIS but we can ignore that until we need it. )

In the case $\kappa=2$ there are graphs which are triangle-free but have arbitrarily high chromatic number. However the number of point grows quadratically with the coloring number.

Finally there are calculations one can do depending of the smallest and/or largest line size. I'll just say that when the smallest line size is $3$ or more than the number of lines can't excede $\frac{n(n-1)}6$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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