Arbitrary girth and chromatic number

In 1961, using a probabilistic argument, Paul Erdős proved that there exist graphs with arbitrarily large girth and chromatic number. In this blog post, we prove this theorem.

Statement of the theorem

For any number $k\ge 3$, there exists a graph with girth at least $k$ and chromatic number at least $k$.

Idea behind the proof

In a random graph $G\in\mathcal{G}_{n,p}$, as the probability of each edge $p$ increases, so does the expected number of edges in the graph $G$. Increase in the number of edges does two things:

1. It increases the chromatic number $\chi(G)$ of the graph. We want this to prove the theorem.
2. It decreases the girth $g(G)$ of the graph, since more edges mean more chances for a small cycle. We want the opposite of this to prove the theorem.

To get both $\chi(G)\geq{k}$ and $g(G)\geq{k}$, we need a $p$ that is large enough to have the required chromatic number $\chi(G)\geq{k}$, but small enough to have the required girth $g(G)\geq{k}$.

Sketch of the proof

We will implement the above idea as follows:

1. We will construct a random graph $G$ by fixing a value for $p$ such that $G$ has a small number of cycles of length less than $k$, for any large $n$. We will then delete these cycles, giving us a graph $G^\prime$ that has no cycles of length less than $k$. In other words, $g(G^\prime)\geq{k}$. Aha!
2. Keeping $p$ fixed, we will then increase $n$ to get $\chi(G^{\prime\prime})\ge k$. Note that keeping $p$ fixed and increasing $n$ increases the chromatic number of the graph, since $\chi(G^{\prime\prime})\ge v(G^{\prime\prime})/ \alpha(G^{\prime\prime})$ where
• $v(G^{\prime\prime})=O(n)$ (the number of vertices in the graph)
• $\alpha(G^{\prime\prime})=O(\log{n})$ (the maximum size of any color class in the graph).

The interesting thing about this approach is that every graph in the family $\mathcal{G}_{n,p}$ with the above values for $n$ and $p$ will almost surely have both girth and chromatic number $\geq k$.

Techniques used

Probabilistic method

The proof

1. Let $X_i$ be a random variable denoting the number of cycles of length $i$. What is the expected value $E(X_i)$?
1. What is the possible number of cycles of length $i$ over $n$ vertices?
1. Number of ways of choosing $i$ vertices of a cycle: $n \choose i$
2. Number of ways of creating a cycle out of $i$ chosen vertices: $(i-1)!/2$ since any permutation of the $i$ vertices is a cycle. However, cycles have no "ends" (hence the division by $i$) and clock-wise and counter-clock-wise orderings translate to the same cycle (hence the division by 2).
3. So the possible number of cycles of length $i$ over $n$ vertices is $ {n\choose i} (i-1)!/2$.
2. If each edge occurs with probability $p$, then the probability of $i$ edges of the cycle in the graph is $p^i$.
3. So $E(X_i)={n\choose i}(i-1)! p^i/2$
2. Lets call "cycles of length less than $k$" as small cycles.
3. Let $X=\sum_{i=3}^{k-1}X_i$ be a random variable denoting the number of small cycles. What is the expected number of small cycles? $E(X) = E(\sum_{i=3}^{k-1}X_i) = \sum_{i=3}^{k-1}E(X_i) \\ = \sum_{i=3}^{k-1} {n\choose i} (i-1)! p^i/2 \\ \le\sum_{i=0}^{k-1} {n\choose i} (i-1)! p^i/2 \\ \leq \sum_{i=0}^{k-1}(np)^i = \frac{(np)^k-1}{np-1}$
4. What is the probability that the number of such small cycles is more than $n/2$? By Markov's inequality, $\mathbf{Pr}(X>n/2) \le E(X)/(n/2)\le\frac{2(np)^k-1}{n(np-1)}$.
5. By choosing $np=n^{1/k}$, or in other words, $p=p_0:=n^{-(k-1)/k}$ \[\lim_{n\rightarrow\infty}\mathbf{Pr}(X>n/2)=0\] This means that when $p=p_0$, almost surely, we only have small cycles (no large cycles).
6. By deleting one vertex on each of the possibly $n/2$ cycles, we obtain $G^\prime$ which has girth at least $k$. In this process, we would have deleted no more than $n/2$ vertices, meaning the number of vertices in $v(G^\prime)$, $v(G^\prime)\ge n/2$.
7. We have now fixed a value of $p$ for which the graph $G^\prime$ has girth $g(G^\prime)\geq k$. This completes part (1) from the sketch of the proof. Now onto part (2).
8. For $G\in\mathcal{G}_{n,p}$, the size of the maximum independent set $\alpha(G)$ is bounded by $\alpha(G)\leq (1/p)\ln(n^2)$ for large $n$. We also note that deleting vertices does not increase the size of the maximum independent set. This implies that for $G^\prime$, $\alpha(G^\prime)\leq (1/p)\ln(n^2)$ is still valid (where $n$ is the number of vertices in the original graph $G$).
9. The chromatic number for $G^\prime$ \[\chi(G^\prime)\geq v(G^\prime)/\alpha(G^\prime) \geq \frac{(n/2)}{(1/p)\ln(n^2)} = \frac{np}{4\ln(n)} = \frac{n^{1/k}}{4\ln(n)}\] By choosing a large enough $n$, we can get $\chi(G^\prime)\ge k$.

Application

With the above method, for $k=10$, we need a graph $G\in\mathcal{G}_{n,p}$ where $n$ is around $10^{20}$ vertices and probability $p=10^{-18}$. All resulting graphs will almost surely have both girth and chromatic number greater than 10.

Redei's theorem

Redei's theorem states that every tournament has a directed Hamilton path. We prove this theorem in this blog post.

Background

Tournament

A tournament is a complete graph with oriented edges.

It can be viewed as the result of a round-robin tournament, where every team plays every other team and there is always a winner and a loser in every match (no ties). The direction of each edge is from the winner to the loser of that match. In the above graph, team 1 beat team 2, hence the edge $1\rightarrow 2$ and so on.

Hamilton path

A Hamilton path is a path connecting all vertices of a graph (once and only once).

The directed path shown above in red is a Hamilton path, since it connects all vertices of the graph.

Now we are ready for the theorem and its proof.

Redei's theorem

Every tournament has a directed Hamilton path. This was first proven by Laszlo Redei in 1934.

Proof by induction

For the base case, consider a directed graph on 2 vertices, say $v_1\rightarrow v_2$. This is also a Hamilton path, since it covers both vertices. So the statement holds true for our base case.

For the inductive step, we assume that each tournament on $(n-1)$ vertices has a Hamilton path. Assume that this path is {$v_1,\cdots,v_{n-1}$} as shown in the graphs below. We consider 3 different scenarios for the new vertex $v$ added to this graph.

1. In the first scenario, we have an edge $v\rightarrow v_1$ as shown by the red edge in the graph below. The new path $\{v,v_1,\cdots,v_{n-1}\}$ is a Hamilton path. So for this scenario, a tournament on $n$ vertices does have a Hamilton path.

2. In the second scenario, we have an edge $v_{n-1}\rightarrow v$ as shown by the red edge in the graph below. The new path $\{v_1,\cdots,v_{n-1},v\}$ is a Hamilton path. So for this scenario too, a tournament on $n$ vertices does have a Hamilton path.

3. In the final scenario different from the previous two, we have both $v_1\rightarrow v$ and $v\rightarrow v_{n-1}$ as shown in the graph below. In this case, the first vertex $v_i$ such that there is an edge $v\rightarrow v_i$ (shown as a dotted edge) completes a Hamilton cycle $\{v_1,\cdots,v_{i-1},v,v_{i+1},\cdots,v_{n-1}\}$. (Note that $i$ could be $n-1$ (the last vertex) if all edges preceding it go into $v$.) So for this scenario too, a tournament on $n$ vertices has a Hamilton path.

The above cover all the scenarios for the inductive step, completing an inductive proof of Redei's theorem that every tournament has a directed Hamilton path.

Conclusion

Using the analogy of matches in a round-robin tournament between $n$ teams, Redei's theorem says that it is always possible to find $n$ matches, such that team A beat team B, which beat team C and so on, which beat team N. Now that was not obvious before! (Note: team A doesn't mean team 1. $\{A, B, \cdots, N\}$ is some permutation of $\{1, 2, \cdots, n\}$.)

References

1. Bondy, J.A., Murty, U.S.R., Graph Theory, 2008.

Experiments in graph 3-coloring - block-cutpoint graph

Introduction
One way to reduce the runtime complexity of an algorithm is to partition the problem into smaller sub-problems, solve the sub-problems and combine these solutions to solve the original, bigger problem. This approach can be used when coloring a graph.

I investigated an approach that uses a block-cutpoint representation of the given graph. On a high level, here is the solution:

1. Given an undirected graph, construct its block-cutpoint graph.
2. Solve the 3-coloring problem for each of the blocks.
3. Combine the solution for each of the blocks to 3-color the original graph.

Definitions
Bi-connected graph
An undirected graph is bi-connected if any two vertices lie on a cycle. In other words, there are at least 2 distinct, disjoint paths between any two vertices. This concept is similar to that of a strongly connected component in a directed graph.

Block (aka Bi-connected component)
A bi-connected subgraph of a graph is called a block.

Cutpoint (aka cut vertex)
A vertex whose removal disconnects a graph is called a cut point or a cut vertex. Such vertices are "on the boundary" of a block. In Figure 1, they are shown in red color.

Block-Cutpoint graph

• A graph where a block is collapsed into a vertex,
• a cut vertex is represented as a vertex in this graph,
• there is an edge between a block vertex and a cut vertex only if the cut vertex is part of the block,
• there is an edge between two cut vertices only if there are adjacent in the original graph.

Interesting point to note is that any undirected graph can be represented as a tree of blocks and cutpoints, as shown in the figure above.

Coloring algorithm

1. Partition given graph G into blocks B1, B2, ..., Bm.
2. Color each of the blocks independently.
3. The reconciliation step: two blocks, say B1 and B2, can share only 1 vertex (the cut vertex), say X.
1. If X is colored with the same color, then we simply merge the colorings for B1 and B2.
2. If X is colored differently in B1 and B2, say c1 and c2, respectively, then:
1. we make X's color in B2 as c1 (its color in B1)
2. All vertices in B2 colored as c2 are now colored as c1 and
3. all vertices in B2 colored as c1 are now colored as c2.
3. So in essence, we swapped colors c1 and c2 in B2.
4. If we perform the reconciliation step in breadth first search order (BFS) of the block-cutpoint tree, we have a valid coloring for the original graph, provided each of the blocks has a valid coloring.

Runtime complexity

• Let the size of G be n.
• Let the sizes of the blocks B1, B2, ..., Bm be n1, n2, ..., nm, respectively.

Since the worst case running time is exponential in the number of nodes, say a^n for G, the runtime complexity of the above algorithm is a^n1 + a^n2 + ... + a^nm + O(n). This translates to O(a^max(n1, n2, ..., nm)) asymptotically.

In closing
This algorithm can be applied to n-coloring, not just 3-coloring. It reduces the time complexity if there are cut vertices in the graph. The more even the size of the blocks, the more the speed-up in run time.