Code related to paper "On the size Ramsey number of all cycles versus a path"

Here is a python program making use of the networkx package which recursively checks each coloring of (P_N)^3 for either a red cycle or a blue path of a given density. When the program is run, you will be prompted for a density (e.g. ".5" or ".751"). Each line has one of the following two forms
  • depth; coloring; blue path; density; "b"
  • depth; coloring; red cycle; cycle length; "r"
The colorings of the up-neighbors are described using the encoding
  • 0: RRR
  • 1: BRR
  • 2: RBR
  • 3: RRB
  • 4: BBR
  • 5: BRB
  • 6: RBB
  • 7: BBB
Example: Let us interpret the line of output
6 ; [6, 6, 3, 7, 3, 4, 2] ; [0, 2, 5, 3, 6] ; 0.666666666667 ; b
  • 6: up(v) has been assigned for all vertices v in {0,1,2,3,4,5,6}.
  • [6, 6, 3, 7, 3, 4, 2]: up(0) = 6 which means up(0) = RBB. So edge 01 is R, edge 02 is B, edge 03 is B. Similarly up(1)=RBB, up(2)=RRB, etc
  • [0, 2, 5, 3, 6]: 02536 is a blue path which begins at 0 and ends at 6. Since up(6) is not RRR or RRB, this is a valid path.
  • 0.666666666667: the density of the path 02536 is 4/6 = 2/3.
  • b: in this case a blue path was found
Some outputs from the program are available here
  • out-p5.txt (20 KB) Output which verifies a density of ".5"
  • out-p75.txt (1.7 MB) Output which verifies a density of ".75"
  • out-p76.txt (34.2 MB) Output which verifies a density of ".76" (takes about 19 minutes to run on my MacBook Air). This is the "proof" of Lemma 4.1
An interactive program which can help verify the proof of Lemma 2.2 is available by contacting me.