Olympiad Combinatorics

Write the incidences as a $0/1$ matrix with a row for each $x$ and a column for each $Y$. The total number of $1$s is the sum of the row sums and also the sum of the column sums; that is all double counting is. Its power is in choosing $\mathcal S$: count the objects the problem cares about (triangles, common neighbours, pairs of committee members) through something you can control on the other side. The convexity step is Jensen for $f(x) = \tfrac{x(x - 1)}{2}$, whose second derivative is $1 > 0$; it turns a sum of $\binom{d_i}{2}$ into a statement about the average degree alone.

Count pairs $(x, A)$ with $x \in A$. Grouped by $A$, the count is the requested sum. Grouped by $x$: each element lies in exactly $2^{n-1}$ subsets (the other $n - 1$ elements are free). So the sum is $n\,2^{n-1}$; for $n = 5$ it is $80$. A check from the other side: sizes $0, \ldots, 5$ occur $1, 5, 10, 10, 5, 1$ times, and $0 + 5 + 20 + 30 + 20 + 5 = 80$.

How to find it. A sum over sets of a size is a count of (element, set) memberships. Swap the order of summation.

Step 1 — a triangle that is not cyclic is transitive, and a transitive triangle has exactly one player who beat both others. So count pairs (player, two players she beat): grouped by player, there are $\sum_i\binom{s_i}{2}$; grouped by triangle, every transitive triangle contributes exactly $1$ and every cyclic one $0$. Hence the number of transitive triangles is $\sum\binom{s_i}{2}$ and the rest, $\binom n3 - \sum\binom{s_i}2$, are cyclic.

Step 2 — the $s_i$ sum to $\binom n2$ (each game produces one win), so their average is $\tfrac{n - 1}{2}$. By convexity $\sum\binom{s_i}{2} \ge n\binom{(n-1)/2}{2}$. For $n = 7$ the average is $3$, so $\sum\binom{s_i}2 \ge 7\cdot3 = 21$ and there are at most $35 - 21 = 14$ cyclic triangles.

Step 3 — the bound is attained: seat the players around a circle and let each beat the next three clockwise. Everyone has $3$ wins, so exactly $14$ triangles are cyclic.

How to find it. Cyclic triangles are hard to count; transitive ones have a distinguished vertex. Count the complement through the vertex that makes it special.

Step 1 — count “cherries”: triples $(w, \{u, v\})$ with $u, v$ distinct neighbours of $w$. Grouped by $w$, there are $\sum_w\binom{d_w}{2}$.

Step 2 — grouped by the pair $\{u, v\}$: two distinct vertices $w, w'$ both adjacent to $u$ and $v$ would give the $4$-cycle $u\,w\,v\,w'$. So each pair has at most one common neighbour, and $\sum_w\binom{d_w}{2} \le \binom n2$.

Step 3 — with $e$ edges the average degree is $\tfrac{2e}{n}$, and convexity gives $n\binom{2e/n}{2} \le \binom n2$, i.e. $\tfrac{2e}{n}\left(\tfrac{2e}{n} - 1\right) \le n - 1$. Multiply by $n^2$: $4e^2 - 2en - n^2(n - 1) \le 0$. The larger root of this quadratic in $e$ is $\tfrac{2n + \sqrt{4n^2 + 16n^2(n - 1)}}{8} = \tfrac n4\left(1 + \sqrt{4n - 3}\right)$, so $e$ is at most that. $\blacksquare$ For $n = 10$ the bound is $\tfrac{10}{4}(1 + \sqrt{37}) \approx 17.7$, so at most $17$ edges.

How to find it. A forbidden subgraph with two paths of length two between the same ends: count paths of length two. The forbidden structure is exactly a statement about the other side of the count.

Pick a vertex $v$ of $K_6$. Of its $5$ edges, at least $3$ share a color — pigeonhole, $5 = 2\cdot2 + 1$ — say red edges to $a, b, c$. If any edge among $a, b, c$ is red, it closes a red triangle with $v$; if none is, $abc$ is a blue triangle. For $K_5$, color the five sides of a pentagon red and the five diagonals blue: each color class is a $5$-cycle, and a $5$-cycle has no triangle. The same step with three colors: a vertex of $K_{17}$ has $16 = 3\cdot5 + 1$ edges, so $6$ share a color; either that color appears among the $6$ neighbours (a triangle) or they span a $K_6$ in two colors.

Step 1 — if a vertex $v$ had three edges of one color, say red to $a, b, c$, the argument of the box gives a red triangle through $v$ or a blue triangle $abc$. So each vertex has at most two edges of each color, and with four edges, exactly two of each.

Step 2 — the red graph is then $2$-regular on $5$ vertices: a union of cycles covering all vertices. A triangle is forbidden, and a $5$-vertex $2$-regular graph without a $3$-cycle cannot split as $3 + 2$ (no $2$-cycles exist), so it is a single $5$-cycle. The blue graph is its complement, also a $5$-cycle. $\blacksquare$

How to find it. Run the proof of $R(3, 3) \le 6$ backwards: every inequality in it must be tight, and tightness pins the structure.

Step 1 — call a pair of edges at a common vertex a bichromatic angle if they have different colors. A vertex with $r$ red and $5 - r$ blue edges carries $r(5 - r) \le 2\cdot3 = 6$ bichromatic angles, so there are at most $6\cdot6 = 36$ in all.

Step 2 — count the same angles by triangles. A monochromatic triangle contains none; a triangle with two edges of one color and one of the other contains exactly $2$ (at the two ends of the odd edge). So twice the number of non-monochromatic triangles is at most $36$: at most $18$ of them.

Step 3 — $K_6$ has $\binom63 = 20$ triangles, so at least $20 - 18 = 2$ are monochromatic. $\blacksquare$ The bound is sharp: color $K_{3,3}$ red and the two remaining triangles blue.

How to find it. Monochromatic triangles are what you want; bichromatic angles are what you can count at a vertex. Relate the two by counting angles triangle by triangle.

Step 1 — model: vertices are scientists, edges colored by topic, a $3$-coloring of $K_{17}$. Fix a scientist $v$. Her $16$ edges carry three colors, so some color, say topic $1$, is used at least $\lceil 16/3\rceil = 6$ times, to $w_1, \ldots, w_6$.

Step 2 — if two of the $w_i$ correspond about topic $1$, they form a topic-$1$ triangle with $v$.

Step 3 — otherwise all $\binom62 = 15$ edges among $w_1, \ldots, w_6$ use only topics $2$ and $3$: a two-coloring of $K_6$, which by the box contains a monochromatic triangle. $\blacksquare$ (Sixteen scientists are not enough: a $3$-coloring of $K_{16}$ without a monochromatic triangle exists — Greenwood and Gleason, 1955.)

How to find it. Reduce the number of colors by one: a large monochromatic neighbourhood either closes a triangle in that color or is a smaller Ramsey problem in the remaining colors.