# Understanding proof about chromatic number

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
• @ArseniyAkopyan Why can't they be in the other hemisphere? – pi66 Oct 10 at 7:37
• @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

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)$$.
• 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