About the problem

Ramsey numbers measure how large a graph must be before it is guaranteed to contain a particular structure. The Ramsey number \(R(s, t)\) is the minimum \(n\) such that for every 2-edge-coloring of the edges of the complete graph on \(n\) vertices with colors red and blue, there is either a set of \(s\) vertices all joined by red edges or a set of \(t\) vertices all joined by blue edges.

Already for \(k \geq 5\) the exact value of \(R(k, k)\) is unknown. Currently, the best bounds for \(k=5\) and \(k=6\) are \(43 \leq R(5, 5) \leq 46\) and \(102 \leq R(6, 6) \leq 160\). The lower bound \(R(6, 6) \geq 102\) is due to Kalbfleisch and is from 1966. This problem asks for an improvement to that lower bound, namely, a 2-edge-coloring of the complete graph on 102 vertices with no set of 6 vertices which are joined by all red or all blue edges. The main risk with asking for this construction is that the Ramsey number \(R(6, 6)\) is equal to 102.

For an anecdotal sense of the difficulty of determining the Ramsey number \(R(6, 6)\), we can turn to a famous anecdote widely attributed to the mathematician Paul Erdős. If all-powerful aliens arrived on earth and demanded to know the value of \(R(5, 5)\) in a year or else, then, he said, we should assemble all the world’s mathematicians and computers, and try our hardest to determine \(R(5, 5)\). If, however, they demanded to know the value of \(R(6, 6)\), we should instead assemble all the world’s military might, and try our hardest to fight off the aliens.

Read more about Ramsey numbers and about recent research on asymptotic upper bounds for Ramsey numbers in this Quanta article.

Prompt

The Ramsey number R(s, t) is the smallest integer n such that any 2-coloring of the edges of the complete graph K_n contains either a red clique of size s or a blue clique of size t. The current best known bounds for R(6, 6) are:

  102 ≤ R(6, 6) ≤ 160

To show R(6, 6) > 102, it suffices to exhibit a 2-coloring of the edges of K_n (for some n ≥ 102) such that there is no monochromatic K_6 — that is, no set of 6 vertices whose induced edges are all the same color.

## Task

Find such a 2-coloring. Specifically, provide:
- An integer n ≥ 102.
- A set of "red" edges of K_n (vertices labeled 1 through n). All remaining edges of K_n are "blue".

The coloring must contain no monochromatic K_6 in either color.

## Submission format

Write your answer to a file named `submission.json`, as a JSON object with the following fields:

```json
{
  "n": <int>,
  "red_edges": [[u, v], ...]
}
```

- `n`: the number of vertices; must be at least 102.
- `red_edges`: a list of edges `[u, v]` with 1 ≤ u < v ≤ n. Each edge appears at most once. All edges of K_n not listed here are blue.