Some Disguised Bi-partite Graphs

by p_square, May 23, 2019, 11:25 AM

This blog post will feature grids and a popular technique involving bipartite graphs to solve some grid related questions.

The main idea will be to treat every row and column of a grid as a vertex of a graph and join two vertices representing a row and a column by an edge depending on their intersection.

Since the exact technique is hard to rigourize in such a manner, I'll present a problem and its solution to convey the main idea.
IMO 1986/6 wrote:
Given a finite set of points in the plane, each with integer coordinates, is it always possible to color the points red or white so that for any straight line $L$ parallel to one of the coordinate axes the difference (in absolute value) between the numbers of white and red points on $L$ is not greater than $1$?

Let us reformulate the problem into a statement that involves a bipartite graph.
Let $U$ be the set of vertical lines passing through at least one point of the set.
Let $V$ be the set of horizontal lines passing through at least one point of the set.
Consider the bipartite graph $G$ with consisting of lines with the bipartition $U$ and $V$.
Let two lines in $U$ and $V$ be neighbours if they intersect at a point in the given set of points.
We wish to colour the edges in such a manner that the differences between red edge degree an white edge degree of a vertex is at most $1$.

First of all, note that all cycles have even length.
What this means, is that we can remove an arbitrary cycle by colouring its edges red and white in an alternating manner.

We are left with a forest.
Consider any tree of the forest. Give it an arbitrary root.
It can be seen inductively that given any tree rooted at $r$ and a weight $w$ which is either $-1,0$ or $1$ we can colour the edges of the tree red and white in such a way that
number of red edges to $r$ - number of white edges to $r \in \{w-1, w, w+1\}$
(This is because we can first make sure that the root is happy :)).
for every other vertice v, the difference between red and white edges is in $\{-1, 0, 1\}$. \blacksquare

The next example in store is from PSE.
Infected Checkerboard Variant wrote:
There are $14$ bacteria on a checkerboard. If in a 2x2 sub-board, 3 cells are infected, the 4th cell gets infected from the next second. Infected cells remain infected. Is it possible that eventually the whole checkerboard gets infected?

Note that there are finitely many possibilities for the initial configuration of bacteria. This reduces the problem to a simple application of Govind's lemma

The solution provided in the link is quite ingenious and quite hard to come up with. Here is a more natural way to solve the problem.
Create a bipartite graph whose vertices are rows and columns of the chessboard and join two vertices by an edge iff they intersect at an infected cell.
Since there are only 14 edges, observe that the graph is disconnected.
Every second, we add some edge to the graph.
However observe that if two vertices were in different components, we cannot add an edge joining them! Whenever we add an edge between two vertices, there must have been a path of length 3 connecting these 2 vertices.
Since initially our graph was disconnected, it will stay disconnected forever; it can never become a complete bipartite graph.. \blacksquare

For the informatics variant and a minor generalisation, check here
pro yaar god yaar. Found white text yaar
While grid bipartition did come useful when solving the previous two questions, it's true power was not revealed.
Grid bipartition can let us turn all of the powerful theorems on graphs quickly to our advantage just by reformulating the question slightly.
It isn't hard to come up with questions like this.
For example (mine)
Tweaked Konig's wrote:
Some stones were places in a rectangular grid. Let $n$ be the smallest natural number such that given any $n+1$ stones, some two are either in the same row or same column. In one step, Petya removes all stones in row or column. Prove that the minimum number of steps required by Petya to remove all the stones is $n$.

Another example (again mine)
Tweaked edge coloring wrote:
Some rooks were placed on a $n \times n$ chessboard, such that no row or column contained more than $m$ rooks. Prove that we can assign each rook one of $m$ colours such that no two rooks of the same color attack each other (For this problem, assume that rooks can attack over other rooks)

___________________________________________________________________
These grid based questions also combine well with the study of matching's in graph theory.

An example can be seen in this question here.
AoPS post wrote:
Some cells of a rectangular table with $n$ rows and $m$ columns ($ n<m $) is filled with stones such that there is at least $1$ stone in any column. Prove that there is a stone such that the number stones of row has it greater than the number stones of column has it.

Let the columns and rows represent vertices of a bipartite graph $G(V,E)$ with vertices $V=X\cup Y$ and $|X|<|Y|$. The edge $\{x_i,y_j\}\in E$ iff there is a stone at the intersection of the $i^{\text{th}}$ row and $j^{\text{th}}$ column. Notice that the degree of a vertex in $X$ or $Y$ is the number of stones in that row or column respectively. We need to show that there exists an edge $\{x_i,y_j\}$ such that $d(x_i)>d(y_j)$.

Assume the contrary and consider the counter example that minimises $|X|+|Y|$. If $\{x_i,y_j\} \in E$ then $d(x_i) \le d(y_j)$. We can assume $G$ is connected else we would be done by the minimality of our counter example. We will show that there is a matching of $X$ onto $Y$. (that is, a set of $|X|$ edges, such that each vertex in $X$ is adjacent with exactly one edge).

Suppose we have a matching, $M$ with maximum number of edges. If the matching is not complete from $X\to Y$, then $X\backslash M$ and $Y\backslash M$ are non-empty. Suppose $y_1 \in Y\backslash M$, by the condition, $y_1$ must be adjacent to some other vertex in $x_1\in X$. If $x_1\in X\backslash M$ we're done. Otherwise $x_1\in M$, let $y_2$ be the corresponding edge of $x_1$ in $M$. We see that $x_1$ has degree at least $2$, so $y_2$ has degree at least $2$, by the condition, so $y_2$ is adjacent to another vertex $x_2$.

We continue in the manner. Since $G$ is finite and connected we must eventually reach a vertex $x_n \in X\backslash M$. We can assume the path $y_1 \to x_n$ passes each vertex only once, else we contract any closed loop. Since the path is odd, say length $2m+1$, there are exactly $m$ edges on the path that are in $M$. Then if we delete those edges we are left with $m+1$ disjoint edges; that is, another matching with more edges. this contradicts the maximality of $M$. It follows that we can find a complete matching $X\to Y$

Now each edge $\{x_i,y_j\}\in M$ satisfies $d(x_i)\le d(y_j)$. But since $|X| < |Y|$ there is some $y\in Y\backslash M$, and $d(y)\ge 1$. Hence $\sum_{x\in X} d(x) < \sum_{y\in Y} d(y)$, but this is absurd. So there is no counter example, and we're done.
[Credits of the solution to Ocha]

Hall's marriage lemma (put simply without symbols) states that in a bipartite graph, iff for every subset of vertices which are of the same colour, the size of the set that consists of ala their neighbours is greater than the original size of the set, then there is a perfect matching on the graph.
Hall's marriage lemma (put simply with symbols) states that in a graph $G=(V,E)$ with bipartition $A,B$ $\forall S \subset A$ or $S \subset B, |N(S)|>|S| \Rightarrow \exists$ a perfect matching.

This too is a formidable tool in the powerful arsenal of grid bipartition. India TST 2017/1/3 falls prey to this.
India TST 2017/1/3 wrote:
Let $n \ge 1$ be a positive integer. An $n \times n$ matrix is called good if each entry is a non-negative integer, the sum of entries in each row and each column is equal. A permutation matrix is an $n \times n$ matrix consisting of $n$ ones and $n(n-1)$ zeroes such that each row and each column has exactly one non-zero entry.

Prove that any good matrix is a sum of finitely many permutation matrices.

We will induct on the common sum of all rows/columns.
Define the bipartite multi(!)-graph G in a manner similar to the start of every problem ever in this post. [join with size of intersection]
Given any $k$ rows/columns $km$ edges emanate and since each column/row swallows at most $m$, we see that by Hall's matching thm. a perfect matching exists.

The last example [again delving into Hall's thm] is RMM 2017/5.
RMM 2017/5 wrote:
Fix an integer $n \geq 2$. An $n\times n$ sieve is an $n\times n$ array with $n$ cells removed so that exactly one cell is removed from every row and every column. A stick is a $1\times k$ or $k\times 1$ array for any positive integer $k$. For any sieve $A$, let $m(A)$ be the minimal number of sticks required to partition $A$. Find all possible values of $m(A)$, as $A$ varies over all possible $n\times n$ sieves.

The answer as one learns after drawing a lot of sieves is $2n - 2$.
The construction for $2n-2$ is easy, irrelevant and left to the reader as an exercise. The interesting part is the proof for minimality..
There are easier 'local' proofs where one can delete a row or column but we present a better, more elegant proof no, I'm not biased at all.

Don't Create a bipartite graph for once.
Let $U$ be the set of $2n-2$ sticks that are either to the left of a removed cell (and stretch till the left edge) or to the right (and stretch till the end of a removed cell) of a removed cell.
Let $V$ be the set of $2n-2$ sticks that are either above a removed cell (and stretch till he top edge) or below a removed cell (and stretch till the bottom edge).
Connect a pair of vertices in $U,V$ with an edge if they intersect.

Each edge corresponds to an unblocked cell.
We will now demonstrate Hall's criterion to show that perfect matching exists between vertices in $U,V$.
This will finish the problem as then select the $2n-2$ cells that correspond to edges of the perfect matching. No pair of these $2n-2$ cells can lie on the same stick.
For any $m \le n$ and $m$ vertices in $U$, there must be some $x$ sticks that terminate at the right edge of the $n \times n$ grid and $m-x$ sticks terminating at the left edge.
Thus, the $(m-x)^{th}$ leftmost columns each must have a stick in $V$ that intersects with the largest of the $m-x$ sticks terminating at the left edge.
Similarly, each of the $x^{th}$ rightmost columns each must have a stick in $V$ that intersects wit the largest of the $x$ sticks terminating at the right edge.
Thus, there must be at least $m$ vertices in $V$ that are connected to at least one of the vertices in $U$.

For any $m \ge n$, and any subset of $U$ with size $m$, it is not hard to see that the subset of $V$ in which each vertex is connected to at least one of the $m$ sticks in $U$ has size greater than $m$ by looking at the vertices in $U$ with which the compliment of this subset of $V$ and doing the same this as the case when $m < n$ and creating a record for the longest and most confusing sentence.

___________________________________________________________________
Practice Problems:
  1. EGMO 2013/3
    Let $m$ be a positive integer. Consider a $4m\times 4m$ array of square unit cells. Two different cells are related to each other if they are in either the same row or in the same column.No cell is related to itself.Some cells are coloured blue, such that every cell is related to at lest two blue cells.Determine the minimum number of blue cells.
  2. Kazakhstan 2012 9.6
    The cell of a $(2m + 1) \times (2n + 1)$ board are painted in two colors - white and black. The unit cell of a row (column) is called dominant on the row (the column) if more than half of the cells that row (column) have the same color as this cell. Prove that at least $m + n - 1$ cells on the board are dominant in both their row and column.
  3. Belarusian National Olympiad 2007/3
    Given a $2n \times 2m$ table $(m,n \in \mathbb{N})$ with one of two signs ”+” or ”-” in each of its cells. A union of all the cells of some row and some column is called a cross. The cell on the intersection of this row and this column is called the center of the cross. The following procedure we call a transformation of the table: we mark all cells which contain ”−” and then, in turn, we replace the signs in all cells of the crosses which centers are marked by the opposite signs. (It is easy to see that the order of the choice of the crosses doesn’t matter.) We call a table attainable if it can be obtained from some table applying such transformations one time.
    Find the number of all attainable tables.

I actually haven't done the third problem, so don't blame me if there is no solution :oops:

___________________________________________________________________

PS I recently read a book 'All the Light We Cannot See' by 'Anthony Doerr' which turned out to be really good. People should try it if they can. To provide some motivation: It won the Pulitzer Prize for fiction in 2015.
This post has been edited 5 times. Last edited by p_square, May 23, 2019, 1:23 PM
graphs
combinatorics

Comment

4 Comments

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
This was something that i was looking for.Congratulation and bring gold this year.

by RAMUGAUSS, May 23, 2019, 6:00 PM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Hey p_square! Remember we met at CMI?
I read All the Light We Cannot See last year. It was a really nice read. Have you read Birth Of A Theorem? I'm reading it these days, it's pretty nice. The last pulitzer-winner I read was A Gentleman In Moscow by the way.

Lol why am I even going too offtopic? Congrats on APMO and APIO
All the best for IMO! Get gold :D

Thanks!
I'll try the books eventually
This post has been edited 1 time. Last edited by p_square, Jun 14, 2019, 11:27 AM

by PhysicsMonster_01, Jun 12, 2019, 11:03 AM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Can only be sorry that Ramsey's theorem is way longer and more confusing

by MathPassionForever, Sep 28, 2019, 7:40 PM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Answer of Belarusian NMO 2007 P3

by Physicsknight, Feb 3, 2020, 6:47 AM

Alive again :D

avatar

p_square
Shouts
Submit

  • thank you for teaching me the humpty point

    by ihatemath123, Jun 27, 2024, 2:43 PM

  • ORZZZZZZZZZZ

    by avisioner, Jun 19, 2024, 12:02 AM

  • He never had motivation to multiply out random polynomials

    by the_mathmagician, Oct 25, 2023, 1:49 AM

  • Getting a part 3 is unlikely... anyways, if it ever gets released, it would be great if you listed some problems where this methods are useful!

    by Alfombra12, Aug 13, 2023, 10:36 AM

  • still waiting for part 3

    by kn07, Jun 14, 2023, 10:55 PM

  • Orz orz :) :omighty:

    by aansc1729, Mar 13, 2023, 1:13 PM

  • waiting for part 3 since 1 year :(

    by anurag27826, Jul 18, 2022, 11:19 AM

  • pro kid moment

    by the_mathmagician, Feb 15, 2022, 2:21 AM

  • Ded blog

    by SPHS1234, Jan 31, 2022, 7:43 AM

  • orzity orz orz

    by tigerzhang, Oct 15, 2021, 10:08 PM

  • congrats on IMO gold medal!

    by mathlearner2357, Jul 25, 2021, 5:04 AM

  • orzorzorz

    by PEKKA, Jul 21, 2021, 3:55 PM

  • Wow this is awesome!!

    Waiting for part3

    by lneis1, Jun 24, 2021, 5:42 PM

  • Part 3 hype

    by NJOY, Jun 15, 2021, 9:29 AM

  • Ooh niceee! Waiting for part 3!

    by L567, Jun 14, 2021, 4:43 AM

63 shouts
Tags
geometry
HM-Point
combinatorics
conic
ellipse
graphs
About Owner
  • Posts: 442
  • Joined: Mar 25, 2017
Blog Stats
  • Blog created: Aug 15, 2018
  • Total entries: 7
  • Total visits: 14617
  • Total comments: 37
Search Blog
a