Puzzle III.4: Epilogue

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 10308), 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 K4 problem. What is the largest N for which the average number of monochromatic K4 is less than 1 (so that by our previous logic, at least one of those colorings has Zero monochromatic K4)? 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 K4?

Script

In addition, I wrote a Perl script to perform exhaustive enumeration of all colorings for small KN, categorizing the breakdown of how many colorings had various numbers of monochromatic KM (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 KN 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 K5 with zero mono-K4. 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 K5 with no mono-K3 (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-K5 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 K9 for mono-K4?
  • Given that mathematicians know that the threshold for K4 is between 17 and 18, how long would it take to verify that every single coloring of K18, has at least one mono-K4?
  • Given agreed-upon limits of the age of the universe, did mathematicians use exhaustive search to determine that all colorings of K18 have at least one mono-K4?

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-KM, 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-K4 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 KM
  • The number of colorings which had that many monochromatic K4

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 KN with no monochromatic KM. 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 K7 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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: