4
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ i-1 points are not on a hemisphere, there are on a hypersphere, a sphere of codimension 1. $\endgroup$
    – Arseniy Akopyan
    Commented Oct 10, 2018 at 6:59
  • 1
    $\begingroup$ @ArseniyAkopyan Why can't they be in the other hemisphere? $\endgroup$
    – pi66
    Commented Oct 10, 2018 at 7:37
  • 1
    $\begingroup$ @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? $\endgroup$
    – pi66
    Commented Oct 10, 2018 at 12:49
  • $\begingroup$ 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. $\endgroup$
    – Ben Barber
    Commented Oct 10, 2018 at 13:02

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Ben Barber
    Commented Oct 10, 2018 at 15:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .