Consider an undirected graph $K(n,k,i)$, with the all $k$-element subsets of $\{1,\dots,n\}$ as vertices, and two vertices connected by an edge if their sets intersect in less than $i$ elements.

This paper claims on page 74 (Theorem 5.1) that the chromatic number of $K(n,k,i)$ is at least $n-2k+2i$. However, their is a place in the proof of the theorem which I don't understand: They say that

Otherwise we would have two $k$-subsets of color $j$ such that each of them has at least $k - i + 1$ elements in one of two disjoint hemispheres, so their intersection has at most $i-1$ elements which is impossible.

Since the intersection can be of size up to $i-1$ in each hemisphere, don't we only get that it has size at most $2i-2$ in total?

  • i-1 points are not on a hemisphere, there are on a hypersphere, a sphere of codimension 1. – Arseniy Akopyan Oct 10 at 6:59
  • 1
    @ArseniyAkopyan Why can't they be in the other hemisphere? – pi66 Oct 10 at 7:37
  • 1
    @BenBarber At most $i-1$ points of the first $k$-set are in the second $k$-set's hemisphere, and vice versa. Doesn't that make for $2i-2$ points available for intersection? – pi66 Oct 10 at 12:49
  • I'm inclined to agree. The argument is of a different shape from that of Greene which it claims to generalise. I'll have a ponder. – Ben Barber Oct 10 at 13:02
up vote 4 down vote accepted

This appears to be a genuine logical error. If $k$ is at least twice $i-1$ and $n$ is large enough that we can cover the sphere in a fine dust, then almost any pair of antipodal points will correspond to hemispheres $H_1$, $H_2$ containing at least $k-i+1$ points from sets $S_1$, $S_2$ with intersection of size $2(i-1)$.

  • Thanks. Does it seem like this error might be fixable, or does the approach completely fail? – pi66 Oct 10 at 15:21
  • I imagine you get a similar result by adding a factor of $2$ somewhere appropriate in the statement, but it looks like you'd need a new idea to get the result claimed. – Ben Barber Oct 10 at 15:46

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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