Skip to main content
added the (graph-colorings) tag - this seems to be the closest one to chromatic number
Link
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40
edited tags
Link
YCor
  • 63.9k
  • 5
  • 187
  • 286
Source Link
pi66
  • 1.2k
  • 8
  • 18

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?