If you’ve followed this far, and are tired of all the numbers, and want to find out why I did it, go here. But for any who are basking in the afterglow of the use of probability to certainly prove existence (non-constructively), I offer a few more resources to assist further investigation.

**Spreadsheet**

First of all, I have made available for public viewing a Google Spreadsheet with formulas to compute all of the various quantities for any and all N and M. There are even logarithmic versions of the formulas, so that in the event that some values overflow the size limits of the spreadsheet software (about 10^{308}), the logarithmic formulas will show the exponent (the “ten-to-the-what” number). A few logistic notes: you will need a “Google Account” to view the spreadsheet. If you have a gmail address, then you have a Google Account, and you can use your gmail login & password. If you don’t have gmail, you can still sign up (free) for a Google Account — just follow the instructions. Where the spreadsheet says “Play with these:”, you will not be able to play with these, unless you File…Copy Spreadsheet… to get your own editable copy. At the time of this writing, Google Spreadsheets’ File…Export…XLS is broken, but assuming it gets fixed at some point, you should be able to save a local copy of the spreadsheet for MS Excel.

One interesting use for the spreadsheet is to investigate the K_{4} problem. What is the largest N for which the average number of monochromatic K_{4} is less than 1 (so that by our previous logic, at least one of those colorings has Zero monochromatic K_{4})? Beyond that size, how long would it take to exhaustively search all colorings, in search of the smallest N which forces all colorings to have at least one monochromatic K_{4}?

**Script**

In addition, I wrote a Perl script to perform exhaustive enumeration of all colorings for small K_{N}, categorizing the breakdown of how many colorings had various numbers of monochromatic K_{M} (for N={3,4,5,6,7,8}, and for M={3,4}).

The printouts from this perl script are appended to this post; since I can’t currently find a way to make WordPress reproduce code nicely, I am not planning to post the script itself, but if you are interested, I would be ecstatic to share it with you. It should run as-is on any PC (with free ActiveState Perl installed), Mac (OS X includes Perl out-of-the-box), or Unix/Linux machine.

The numbers reported by the script provide a wealth of empirical verification for the computations we discussed. For instance, we know that the number of colorings of K_{N} is 2^C(N,2), and for N=5 that is 2^10=1024 colorings, but the script actually went through and inspected all the colorings, and reported at the end “Hey, I looked at 1024 colorings”. I want to briefly discuss one interesting number in the script results, and then I’ll just give some additional questions to guide exploration through the numbers.

The script reported that it found 12 colorings of K_{5} with zero mono-K_{4}. Why 12? Recall the canonical two-word answer of “two cycles”: there are as many suitable colorings as there are distinct ways to choose one complete cycle to be red (automatically leaving the remaining edges to form a complete cycle of blue edges). How many ways to build the cycle of 5 edges/5 vertices which will be red? That’s the same as the number of ways to order 5 things, or 5!, right? But that’s 120, and the script only found 12. So our first guess of 5! includes an overcounting factor of 10, which we need to explain. First of all, by counting every single ordering of 5 objects, we are overcounting by being linear, not cyclic. What I mean is that orderings have a first element, but cycles just keep going round and round. So the cycle 1->2->3->4->5->1 is the same cycle as 3->4->5->1->2->3 (is the same if you start with 2 or 4 or 5), even though the ordering 12345 is not the same as the ordering 34512. So that’s an overcounting factor of 5. The other way we are overcounting is by being directional. Orderings run only forwards, but cycles are the same forwards or backwards. It makes no difference if we color the cycle 1->3->5->2->4->1 red, or if we color the cycle 1->2->4->5->3->1 red (even though permutations 13524 and 14253 are different). So accounting for forwards/backwards is another factor of two. Every red cycle is counted 5*2=10 times to get to a total of 5!=120 orderings, thus the number of distinct colorings of K_{5} with no mono-K_{3} (and the number of possible correct answers to Puzzle I) is 120/10=12.

Here are some more questions about the exhaustive search results:

- Do the numbers of colorings in the second column always add up to the total number of colorings? (Has the script actually enumerated all the colorings?)
- Does the script report the correct number of total edge-checks?
- How do you compute the average number of mono-K
_{5}from the data in the two columns? Does that computed average always match the stated average at the end of each section? Does the stated average always match the average that would be predicted from our formula? (C(N,M)/2^C(M,2)) - Why does each table of two columns end with a count of two colorings?
- How many edges-checks-per-second can the script perform?
- How long did the whole script take to run?
- How long would the script take to exhaustively search colorings of K
_{9}for mono-K_{4}? - Given that mathematicians know that the threshold for K
_{4}is between 17 and 18, how long would it take to verify that every single coloring of K_{18}, has at least one mono-K_{4}? - Given agreed-upon limits of the age of the universe, did mathematicians use exhaustive search to determine that all colorings of K
_{18}have at least one mono-K_{4}?

**Program**

It so happens that I also wrote a small C program to perform the exhaustive searches more efficiently, and it kind of morphed into a random-search program (instead of methodically testing **all** colorings, **randomly** choose colorings until one is found with no mono-K_{M}, then move on to the next N). Below the script output, I also include the program output (and I’ll be glad to send the source code to anybody who asks). Mysteriously, it finds no-mono-K_{4} examples for N=7,8,9,10,11 instantly, and then just spins on N=12. I’m not sure whether my program has a bug, or if it just ran into combinatorial crunch.

**Script Output**

For each combination of N and M, the script outputs a two-column table of

- A number of monochromatic K
_{M} - The number of colorings which had that many monochromatic K
_{4}

`Checking all edge-colorings of K_3 for monochromatic K_3:`

0 6

1 2

8 colorings

24 edges checked

2 mono K_3 found

Average: 0.25

Time: 0 wallclock secs ( 0.00 usr + 0.00 sys = 0.00 CPU)

---------------------------------------------------------

Checking all edge-colorings of K_3 for monochromatic K_4:

0 8

8 colorings

0 edges checked

2 mono K_4 found

Average: 0.25

Time: 0 wallclock secs ( 0.00 usr + 0.00 sys = 0.00 CPU)

---------------------------------------------------------

Checking all edge-colorings of K_4 for monochromatic K_3:

0 18

1 32

2 12

4 2

64 colorings

768 edges checked

66 mono K_3 found

Average: 1.03125

Time: 0 wallclock secs ( 0.01 usr + 0.00 sys = 0.01 CPU)

---------------------------------------------------------

Checking all edge-colorings of K_4 for monochromatic K_4:

0 62

1 2

64 colorings

384 edges checked

68 mono K_4 found

Average: 1.0625

Time: 0 wallclock secs ( 0.00 usr + 0.00 sys = 0.00 CPU)

---------------------------------------------------------

Checking all edge-colorings of K_5 for monochromatic K_3:

0 12

1 260

2 270

3 300

4 100

5 60

7 20

10 2

1024 colorings

30720 edges checked

2628 mono K_3 found

Average: 2.56640625

Time: 0 wallclock secs ( 0.15 usr + 0.00 sys = 0.15 CPU)

---------------------------------------------------------

Checking all edge-colorings of K_5 for monochromatic K_4:

0 892

1 110

2 20

5 2

1024 colorings

30720 edges checked

2788 mono K_4 found

Average: 2.72265625

Time: 0 wallclock secs ( 0.16 usr + 0.00 sys = 0.16 CPU)

---------------------------------------------------------

Checking all edge-colorings of K_6 for monochromatic K_3:

2 1760

3 5760

4 7500

5 6264

6 5040

7 3360

8 1530

9 720

10 432

11 160

12 90

13 120

16 30

20 2

32768 colorings

1966080 edges checked

166628 mono K_3 found

Average: 5.0850830078125

Time: 7 wallclock secs ( 7.09 usr + 0.00 sys = 7.09 CPU)

---------------------------------------------------------

Checking all edge-colorings of K_6 for monochromatic K_4:

0 22484

1 7080

2 2370

3 400

4 90

5 192

6 120

9 30

15 2

32768 colorings

2949120 edges checked

181988 mono K_4 found

Average: 5.5538330078125

Time: 10 wallclock secs ( 9.24 usr + 0.00 sys = 9.24 CPU)

---------------------------------------------------------

Checking all edge-colorings of K_7 for monochromatic K_3:

4 11340

5 135310

6 235620

7 373470

8 311360

9 351330

10 200634

11 203700

12 103320

13 76020

14 37450

15 25956

16 10080

17 9100

18 5460

19 2730

20 1148

21 1470

22 840

23 350

25 210

26 210

30 42

35 2

2097152 colorings

220200960 edges checked

18532068 mono K_3 found

Average: 8.83677864074707

Time: 664 wallclock secs (663.95 usr + 0.00 sys = 663.95 CPU)

---------------------------------------------------------

Checking all edge-colorings of K_7 for monochromatic K_4:

0 923012

1 611170

2 323750

3 120400

4 38920

5 29218

6 27720

7 7980

8 2730

9 5460

10 3570

11 1260

13 910

15 308

16 490

19 210

25 42

35 2

2097152 colorings

440401920 edges checked

20825828 mono K_4 found

Average: 9.93052864074707

Time: 1006 wallclock secs (1005.67 usr + 0.00 sys = 1005.67 CPU)

---------------------------------------------------------

Checking all edge-colorings of K_8 for monochromatic K_3:

8 1944530

9 9723840

10 21059640

11 29300992

12 34460580

13 36252720

14 32492200

15 27418272

16 22640226

17 16787120

18 12047280

19 8581440

20 5552372

21 3585168

22 2376360

23 1466080

24 910140

25 638400

26 414568

27 255360

28 183120

29 108640

30 82488

31 63840

32 23870

33 18480

34 19320

35 11328

36 7476

37 1680

38 1400

39 3360

40 1680

41 672

44 420

45 336

50 56

56 2

268435456 colorings

45097156608 edges checked

3778922212 mono K_3 found

Average: 14.0775822550058

Time: 119776 wallclock secs (119704.48 usr + 0.26 sys = 119704.74 CPU)

---------------------------------------------------------

Checking all edge-colorings of K_8 for monochromatic K_4:

0 55881692

1 71212120

2 56447090

3 34768720

4 17969910

5 10381224

6 8135680

7 4612320

8 2629900

9 1753360

10 1654744

11 1051680

12 421680

13 468160

14 217840

15 206808

16 183610

17 122640

18 63140

19 63840

20 84784

21 20160

23 30520

24 5040

25 11424

26 16800

27 3360

28 840

29 8820

32 3360

35 2256

36 560

39 560

41 420

45 336

55 56

70 2

268435456 colorings

112742891520 edges checked

4366124772 mono K_4 found

Average: 16.2650822550058

Time: 210230 wallclock secs (210069.38 usr + 0.18 sys = 210069.56 CPU)

**Program Output**

Note that each found graph demonstrates a coloring of K_{N} with no monochromatic K_{M}. The format of presenting the graph is to define which edges are to be colored red (0) or blue (1). For instance, the answer right thar for K_{7} is a 7×7 brick, where that first 0 is in row 1, column 2, indicating that the edge {1,2} should be colored 0 (red). The – characters simply indicate that there is no edge between a vertex and itself (e.g. {1,1}), and the reverse-edges (e.g. {2,1}) don’t need to have colors assigned, because they are fully defined by the 0 and 1 in the upper triangle.

`Randomly searching edge-colorings of K_7 for no monochromatic K_4`

Coloring with no mono K_4 found in 0 seconds (1 tries):

-010111

--01001

---1110

----001

-----01

------0

-------

Randomly searching edge-colorings of K_8 for no monochromatic K_4

Coloring with no mono K_4 found in 0 seconds (9 tries):

-1000001

--001111

---00110

----1111

-----010

------01

-------1

--------

Randomly searching edge-colorings of K_9 for no monochromatic K_4

Coloring with no mono K_4 found in 0 seconds (16 tries):

-00110011

--1010101

---111000

----01100

-----1001

------000

-------10

--------0

---------

Randomly searching edge-colorings of K_10 for no monochromatic K_4

Coloring with no mono K_4 found in 0 seconds (131 tries):

-110011011

--10110001

---1101000

----100010

-----00111

------1010

-------100

--------01

---------1

----------

Randomly searching edge-colorings of K_11 for no monochromatic K_4

Coloring with no mono K_4 found in 0 seconds (3141 tries):

-1101101001

--010010011

---00101000

----0000111

-----110101

------10010

-------0011

--------101

---------10

----------0

-----------

Randomly searching edge-colorings of K_12 for no monochromatic K_4

As noted above, the program just sits & spins at this point, and I’m not sure if I have a bug, or if N=12 is just the point at which combinatorial explosion takes effect.

## Leave a Reply