Exercise Sheet 5  Combinatorics

2014/15

{Ex. 28 \atop a)} Prove that R(3, 4) ≤ 10, and with an extra thought: R(3, 4) ≤ 9. Hint: as started in class: Start with 10 vertices. Any vertex V has 9 neighbours. suppose V has 6 (or more) neighbours connected along red edges. Then by R(3, 3) = 6 there must be either a red K_{4} or a blue K_{3}. Hence V has at most 5 red adjacent edges. Suppose V has at least 4 neighbours, connected along blue edges, then again either there is a red K_{4} or a blue K_{3}.

This proves R(3, 4) ≤ 10.

Now, analyzing the proof above, and starting with 9 vertices. What can you say about the colour of the adjacent edges? In particular prove that it is not possible that all vertices have exactly five adjacent red edges. Hence conclude that R(3, 4) ≤ 9.

c) Let G be a graph defined on 8 vertices. The vertices are numbered from 0 to 7. Colour the edge (x, y) blue if

x − y mod 8 ∈ {1, 4, 7}.

(Here x − y mod 8 is assumed to be respresented by a number from 0 to 7). The edge (x, y) is coloured red if

x − y mod 8 ∈ {0, 2, 3, 5, 6}.

Show that G has no red K_{4} and no blue K_{3}. Use this to show that R(3, 4) ≥ 9.

Ex. 29 Now taking the idea of proof of the bound R(3, 4) ≤ 10 above, and prove that R(s, t) ≤ R(s − 1, t) + R(s, t − 1). Comparing with the binomial coefficients evaluate a concrete upper bound (for example using Stirling’s formula) for s = t and s = 2t, as t goes to infinity.

{Ex. 30 \atop a)} Prove that R(4, 4) ≤ 18, (easy).

b) Let X = {0, 1, 2, ..., 16} be the set of residues mod 17 and let G be the complete graph on X. Given x, y ∈ X with x < y, colour the edge {x, y} red if y − x is equal to a square number modulo 17, and blue otherwise. (For example, {2, 10} is red because 10−2 mod 5^{2} mod 17.) b1) Find all square numbers modulo 17. b2) Show that if x, y, u ∈ X then {x, y}, {x + u, y + u} and {xu^{2}, yu^{2}} all have the same colour. (Note that one can assume that u ≠ 0). b3) Prove that G has no monochromatic 4-set. [Hint: use (b2) to reduce the number of cases that have to be considered.] b4) What does this imply about R(4, 4)?

{Ex. 31 \atop a)} Show that an arbitrary 2-colouring of an 4 × 7 board contains the four corners of a a monochromatic (axis-parallel) rectangle. What about colouring of an 4 × 6 board?

b) Show that there exist m and n such that: an arbitrary 2-colouring of an m × n board contains the 9 squares of a monochromatic (axe-parallel) 3 × 3 subgrid. For example, columns 1,2,5 in lines 1,3,4 define such a grid).

XX00X
00XXX
XXXXX
XXX0X

For information: In his book “Timaios” Plato proves that there are at most 5 regular solids. The proof is a simple folding technique from plane to three-space. He does not discuss why (for example) a solid like the icosahedron, folded just on one corner, actually exists.

http://12koerbe.de/pan/timaios6.htm Timaois auf Deutsch

and

http://www.math.tugraz.at/~elsholtz/WWW/lectures/ss00/kogeo/platon1.pdf

For information Book XIII of “The Elements” of Euclid shows the existence of the Platonic solids, by constructions. For example, the lengths of the sides of the icosahedron and dodecahedron are calculated.

http://aleph0.clarku.edu/~djoyce/java/elements/bookXIII/bookXIII.html

The classical translation with commentary is by Thomas Heath (based on the best available source, a comparison of various handwritten manuscripts, which are actually slightly different versions of the text, due to Heiberg)

http://www.wilbourhall.org/pdfs/Heath_Euclid_III.pdf (large file!), start-

ing at page 481.

Ex. 32 A much simpler construction of the icosahedron is due to Luca Pacioli (14451517): Look it up: (pages 22 and 24) of John Stillwell, Mathematics and Its History

http://books.google.at/books?id=3bE_AAAAQBAJ&printsec=frontcover&hl=de#v=onepage&q&f=false
or http://en.wikipedia.org/wiki/Golden_rectangle

The construction starts with three (orthogonally placed) “golden” rectangles, of side ratio \frac{\sqrt{5}+1}{2} : 1. Prove that the resulting triangles (see triangle ABC in Stillwell’s book) are equilateral, and then observe by symmetry that all triangles are of the same type. Let τ = \frac{\sqrt{5}+1}{2} = 1.61 … The twelve vertices of the icosahedron (with edge length 2) are:

(0, ±τ, ±1), (±1, 0, ±τ), (±τ, ±1, 0).

The twenty midpoints of the faces (and therefore, also the corners of a dodecahedron are:

\frac{τ^{2}}{3} (0, ±\frac{1}{τ}, ±τ), \frac{τ^{2}}{3} (±τ, 0, ±\frac{1}{τ}), \frac{τ^{2}}{3} (±\frac{1}{τ}, ±τ, 0), \frac{τ^{2}}{3} (±1, ±1, ±1)

The thirty midpoints of edges are:

(±τ, 0, 0), (0, ±τ, 0), (0, 0, ±τ), \frac{1}{2}(±τ^{2}, ±1, ±τ), \frac{1}{2}(±τ, ±τ^{2}, ±1), \frac{1}{2}(±1, ±τ, ±τ^{2}).

In principle, one can work out the 60 rotation matrices. All you need to recall is a formula of this matrix, given the axis, and given the rotation angle: If (n_{1}, n_{2}, n_{3}) with n_{1}^{2} + n_{2}^{2} + n_{3}^{2} = 1 is the rotation axis:

( \begin{matrix}cos θ + n_{1}^{2}(1 − cos θ) & n_{1}n_{2}(1 − cos θ) − n_{3} sin θ & n_{1}n_{3}(1 − cos θ) + n_{2} sin θ) \\ n_{1}n_{2}(1 − cos θ) + n_{3} sin θ & cos θ + n_{2}^{2}(1 − cos θ) & n_{2}n_{3}(1 − cos θ) − n_{1} sin θ \\ n_{1}n_{3}(1 − cos θ) − n_{2} sin θ & n_{2}n_{3}(1 − cos θ) + n_{1} sin θ & cos θ + n_{3}^{2}(1 − cos θ) \end{matrix} ) .

One more thing: from Pacioli’s construction one can easily see that one can circumscribe a cube around the icosahedron, just use the 6 sides of the “golden” rectangles. For a picture see here:

http://www.georgehart.com/virtual-polyhedra/ex-pr1.html

Similarly one can inscribe cubes, and the rotations correspond to the even permutations of cubes inside (or outside) in five distinct positions, (giving the 60 even permutations of A_{5}). Information: The classification of the finite subgroups of the group of rotations SO_{3} is due to Felix Klein. You can view at his famous book “Vorlesungen über das Ikosaeder und die Auflösung der Gleichungen vom fünften

Grade” here: https://archive.org/stream/vorlesungenber00kleiuoft#page/n5/mode/2up

starting on page 16 the group of rotations of the icosahedron is studied, and the isomorphy to the group A_{5} is shown. (There is much information above, for the purpose of the exercise in class: Just do (at least) Pacioli’s construction, and and write down 3 corresponding rotation matrices, one of order 2,3, and 5.) If you have time try to understand why there are cubes inside the icosahedron/dodecahedron (maybe also search for pictures on the internet).

Ex. 33 A_{5} is smallest nonabelian “simple” group. A group is simple if it has only trivial “normal subgroups”. Prove that A_{5} is simple by studying the even permutations. (A permutation is even, if the number of transpositions describing the permutation is even.

(123) = (13)(12) is even.) List all conjugacy classes, (they are related to those of S_{5}, even though in some cases a class in S_{n} splits into two classes in A_{n}). Note that a normal subgroup must contain the union of (complete!) conjugacy classes, and that there is no combination of these which could possibly be a subgroup of A_{5}, according to Lagrange’s theorem.

An alternative, geometric proof! A Simple Proof for the Simplicity of A_{5} Benno Artmann, American Math. Monthly 95, no 4. (1988) 344–349.

http://www.jstor.org/stable/2323573 (For this link you need to be logged

into TU/library account). The author proves that all rotations of order 2 are conjugate, and generate A_{5}. The same for rotations of order 3. For order 5, rotations by 2π/5 and 4π/5 are not conjugate, but they all generate A_{5}.