Michael likes cycles
by shiningsunnyday, Nov 21, 2016, 10:31 AM
Problems From the Book wrote:
Suppose
points of an
grid are marked. Prove that there exists a
and
distinct marked points
such that for all
and
, are in the same row, while
and
are in the same column.









Lemma: Any graph of order (number of vertices
) with at least
edges has a cycle.
Proof: The heuristic is this:
Vertices of degree 1 are useless cause they can't form cycles.
So the idea is to keep deleting vertices of degree 1 along with its incident edge. This motivates strong induction. Base case is trivial.
Case 1: All vertices have degree at least
consider the longest path of the graph:
Note that for each
its set of neighbors must be within this path, otherwise there exists a neighbor of
say
such that
Add that to the path to obtain a longer path, contradiction. Therefore, because
has at least
neighbors in this maximal path, one of its neighbors must be
Then we have
a cycle, as desired.
Case 2: At least one vertex has degree
delete vertices of degree
and each of their incident edges. Afterwards we've still maintained the
condition, but the number of vertices has gone down. Apply strong induction hypothesis and we're done.
Back to problem: Set the
points of the problem as vertices in graph
and connect two vertices
and color it blue if
belong to the same row and red if they belong to the same column. It's not hard to see there're at least
blue edges and
red edges of our graph. Since there're at least
edges and
vertices, we must have a cycle.
Unfortunately, this cycle might be monochromatic - all the edges of the same color. In particular, we want to force a cycle to not be monochromatic. Let's redefine the way we defined an edge as follows:
Connect vertex
to
and
iff
is in the same row as
but
is in the same column as
In other words, our edges come in pairs: in the shape of an
Define
to be the joint of the
Note that we can't have a cycle of length
since we can't have
and
be in the same row or column.
Therefore, every vertex of nonzero degree must have at least a blue and a red edge. It suffices to show there're at least
such
shapes. We apply a heuristic similar to our lemma:
Vertices that cannot be the joint of an
called useless. In other words, a useless vertex will be completely alone in either its row or column.
If there're at most
shapes, there're at least
useless vertices. Now the claim is that at least one of the useless vertices will have exactly
other vertex in its row and column combined. If we can find such a useless vertex, delete both the row and column its in, leaving us with a
grid and
points, and we can apply strong induction.
Otherwise, each useless vertex will have at least
other vertices in its row or column and none in the other, so there's at least
vertices in its row and column combined. But any vertex that's not useless is the joint of an
shape, so there's also at least
vertices in its row and column combined.
Then... rip.


Proof: The heuristic is this:
Vertices of degree 1 are useless cause they can't form cycles.
So the idea is to keep deleting vertices of degree 1 along with its incident edge. This motivates strong induction. Base case is trivial.
Case 1: All vertices have degree at least










Case 2: At least one vertex has degree



Back to problem: Set the








Unfortunately, this cycle might be monochromatic - all the edges of the same color. In particular, we want to force a cycle to not be monochromatic. Let's redefine the way we defined an edge as follows:
Connect vertex













Therefore, every vertex of nonzero degree must have at least a blue and a red edge. It suffices to show there're at least


Vertices that cannot be the joint of an

If there're at most






Otherwise, each useless vertex will have at least




Then... rip.
Redemption: awesome actual solution
Consider a bipartite graph partitioned into
vertices representing columns and
representing rows. Connect two vertices if their intersection includes one of the
numbers. Since this graph is of order
, by the lemma we can find a cycle (even cycle of length at least
cause the graph is bipartite), and it's not hard to see this cycle is equivalent to our condition.





This post has been edited 1 time. Last edited by shiningsunnyday, Nov 21, 2016, 2:32 PM