Day3.sagews

load("conjecturing.py")

k3 = graphs.CompleteGraph(3)
#[(is_clique)->(is_hamiltonian)] is TRUE
k3_4 = graphs.CompleteBipartiteGraph(3,4)
k5_5 = graphs.CompleteBipartiteGraph(5,5)
#(is_cycle)->(is_hamiltonian) is TRUE
k2 = graphs.CompleteGraph(2)
EH = graphs.EllinghamHorton54Graph()
#CLAIM: ((is_strongly_regular)&(is_bipartite))->(is_hamiltonian) is true for n>2
#NB presented a proof: we need to write this up!
pete = graphs.PetersenGraph()
c5 = graphs.CycleGraph(5)
fish = Graph([(0,1),(1,2),(2,3),(3,4),(4,5),(5,2),(2,0)])
c5_tail = graphs.CycleGraph(5)
#c5_tail.add_vertex()
c5_tail.add_edge(0,5)
bow_tie = Graph(5)
bow_tie.add_edges([(0,1),(1,2),(2,3),(3,4),(4,2),(2,0)])
c7 = graphs.CycleGraph(7)
c7_chord = graphs.CycleGraph(7)
c7_chord.add_edge(0,2)
glasses = Graph(7)
glasses.add_edges([(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,3),(3,0)])
p3 = graphs.PathGraph(3)
k5 = graphs.CompleteGraph(5)

triangle_with_tail = graphs.CompleteGraph(3)
triangle_with_tail.add_edge(0,3)
blanusa2 = graphs.BlanusaSecondSnarkGraph()

c5_tail.show()

#Run8 from Day 2
#add fish, c5_tail & theorem 1
graph_objects = [k3,pete,c5,k5_5,k3_4,EH,c7_chord,bow_tie,k5,p3,glasses,fish,c5_tail]

properties = [Graph.is_hamiltonian, Graph.is_clique, Graph.is_regular,Graph.is_cycle,Graph.is_bipartite,Graph.is_chordal,Graph.is_strongly_regular,Graph.is_eulerian, Graph.is_triangle_free, Graph.is_distance_regular, Graph.is_perfect, Graph.is_planar]

property_of_interest = 0

theorem1 = lambda g: g.is_bipartite() and g.is_strongly_regular()

theorems = [Graph.is_cycle, Graph.is_clique, theorem1]

conjs = propertyBasedConjecture(graph_objects, properties, property_of_interest, theory = theorems)
for c in conjs:
    print c

(((is_triangle_free)|(is_eulerian))->(is_clique))->(is_hamiltonian) (((is_eulerian)->(is_bipartite))^(is_triangle_free))->(is_hamiltonian) (((is_triangle_free)|(is_eulerian))->((is_strongly_regular)&(is_bipartite)))->(is_hamiltonian)

#CLAIM: triangle with a tail is a CE to 1st and 2nd conjectures (conjs[0] and conjs[1])
triangle_with_tail = graphs.CompleteGraph(3)
triangle_with_tail.add_edge(0,3)
triangle_with_tail.show()

#CLAIM: 

conjs[0](triangle_with_tail)

False

conjs[1](triangle_with_tail)

False

conjs[2](triangle_with_tail)

False

#Run 1 of Day 3
#add triangle_with_tail
graph_objects = [k3,pete,c5,k5_5,k3_4,EH,c7_chord,bow_tie,k5,p3,glasses,fish,c5_tail,triangle_with_tail]

properties = [Graph.is_hamiltonian, Graph.is_clique, Graph.is_regular,Graph.is_cycle,Graph.is_bipartite,Graph.is_chordal,Graph.is_strongly_regular,Graph.is_eulerian, Graph.is_triangle_free, Graph.is_distance_regular, Graph.is_perfect, Graph.is_planar]

property_of_interest = 0

theorem1 = lambda g: g.is_bipartite() and g.is_strongly_regular()

theorems = [Graph.is_cycle, Graph.is_clique, theorem1]

conjs = propertyBasedConjecture(graph_objects, properties, property_of_interest, theory = theorems)
for c in conjs:
    print c

((((is_eulerian)|(is_chordal))|(is_triangle_free))->(is_clique))->(is_hamiltonian) ((((is_chordal)|(is_bipartite))->(is_strongly_regular))&((is_perfect)^(is_eulerian)))->(is_hamiltonian)

#TO GET BETTER CONJECTURES WE NEED MORE PROPERTIES
#wE WILL LOAD THESE FROM GT.SAGE
load("gt.sage")
#NOTE: 2 properties have broken definitions and need to be fixed
#we'll load a fixed version gt-nb.sage from neal's own work
load("gt-nb.sage")

loaded utilities loaded invariants loaded properties loaded theorems loaded graphs Remember to load DIMACS and Sloane graphs if you want them loaded utilities loaded invariants loaded properties loaded theorems loaded graphs Remember to load DIMACS and Sloane graphs if you want them

#what are the names of the lists which contain invariants, graphs, and properties?
len(properties)

92

for p in properties:
    print p.__name__

is_regular is_planar is_forest is_eulerian is_connected is_clique is_circular_planar is_chordal is_bipartite is_cartesian_product is_distance_regular is_even_hole_free is_gallai_tree is_line_graph is_overfull is_perfect is_split is_strongly_regular is_triangle_free is_weakly_chordal is_dirac is_ore is_haggkvist_nicoghossian is_generalized_dirac is_van_den_heuvel is_two_connected is_three_connected is_lindquester is_claw_free has_perfect_matching has_radius_equal_diameter is_not_forest is_fan is_cubic diameter_equals_twice_radius diameter_equals_radius is_locally_connected matching_covered is_locally_dirac is_locally_bipartite is_locally_two_connected is_interval has_paw is_paw_free has_p4 is_p4_free has_dart is_dart_free has_kite is_kite_free has_H is_H_free has_residue_equals_two order_leq_twice_max_degree alpha_leq_order_over_two is_factor_critical is_independence_irreducible has_twin is_twin_free diameter_equals_two girth_greater_than_2log is_cycle pairs_have_unique_common_neighbor has_star_center is_complement_of_chordal has_c4 is_c4_free is_subcubic is_quasi_regular is_bad has_k4 is_k4_free is_hamiltonian is_vertex_transitive is_edge_transitive has_residue_equals_alpha is_odd_hole_free is_semi_symmetric is_line_graph is_planar_transitive is_class1 is_class2 is_anti_tutte is_anti_tutte2 has_lovasz_theta_equals_cc has_lovasz_theta_equals_alpha is_chvatal_erdos is_heliotropic_plant is_geotropic_plant is_traceable is_chordal_or_not_perfect has_alpha_residue_equal_two

is_dirac?

File: /home/user/<string>
Signature : is_dirac(g)
Docstring :

EH.order()

54

for p in properties:
    print p.__name__, p(EH)

is_regular True is_planar False is_forest False is_eulerian False is_connected True is_clique False is_circular_planar False is_chordal False is_bipartite True is_cartesian_product False is_distance_regular False is_even_hole_free False is_gallai_tree False is_line_graph False is_overfull False is_perfect True is_split False is_strongly_regular False is_triangle_free True is_weakly_chordal False is_dirac False is_ore False is_haggkvist_nicoghossian False is_generalized_dirac False is_van_den_heuvel True is_two_connected True is_three_connected True is_lindquester False is_claw_free False has_perfect_matching True has_radius_equal_diameter False is_not_forest True is_fan False is_cubic True diameter_equals_twice_radius False diameter_equals_radius False is_locally_connected False matching_covered True is_locally_dirac False is_locally_bipartite True is_locally_two_connected False is_interval False has_paw False is_paw_free True has_p4 True is_p4_free False has_dart False is_dart_free True has_kite False is_kite_free True has_H True is_H_free False has_residue_equals_two False order_leq_twice_max_degree False alpha_leq_order_over_two True is_factor_critical False is_independence_irreducible False has_twin True is_twin_free False diameter_equals_two False girth_greater_than_2log False is_cycle False pairs_have_unique_common_neighbor False has_star_center False is_complement_of_chordal False has_c4 False is_c4_free True is_subcubic True is_quasi_regular True is_bad False has_k4 False is_k4_free True is_hamiltonian False is_vertex_transitive False is_edge_transitive False has_residue_equals_alpha False is_odd_hole_free True is_semi_symmetric False is_line_graph False is_planar_transitive False is_class1 True is_class2 False is_anti_tutte False is_anti_tutte2 False has_lovasz_theta_equals_cc True has_lovasz_theta_equals_alpha True is_chvatal_erdos False is_heliotropic_plant False is_geotropic_plant False is_traceable True is_chordal_or_not_perfect False has_alpha_residue_equal_two False

properties.index(Graph.is_hamiltonian)

72

#Run 2 of Day 3
#add triangle_with_tail
graph_objects = [k3,pete,c5,k5_5,k3_4,EH,c7_chord,bow_tie,k5,p3,glasses,fish,c5_tail,triangle_with_tail]

#properties = [Graph.is_hamiltonian, Graph.is_clique, Graph.is_regular,Graph.is_cycle,Graph.is_bipartite,Graph.is_chordal,Graph.is_strongly_regular,Graph.is_eulerian, Graph.is_triangle_free, Graph.is_distance_regular, Graph.is_perfect, Graph.is_planar]

#the properties list used in the conjecturing program will be the on from gt.sage

property_of_interest = properties.index(Graph.is_hamiltonian)

theorem1 = lambda g: g.is_bipartite() and g.is_strongly_regular()

theorems = [Graph.is_cycle, Graph.is_clique, theorem1]

conjs = propertyBasedConjecture(graph_objects, properties, property_of_interest, theory = theorems)
for c in conjs:
    print c

((has_radius_equal_diameter)&(is_van_den_heuvel))->(is_hamiltonian)

c7_chord.radius()

3

is_van_den_heuvel??

   File: /home/user/<string>
Unable to read source code (source code not available)

#NOTE: Conjecture: (has_radius_equal_diameter)&(is_van_den_heuvel))->(is_hamiltonian)
#involves a known necessary condition for hamiltonicity
#NOTE: radius=diameter is not a sufficient condition by itsefl, pete for instance is a CE
conjs[0]

((has_radius_equal_diameter)&(is_van_den_heuvel))->(is_hamiltonian)

conjs[0](pete)

True

#NOTE there is a list of pre-coded graphs that's worth testing conjecture against
len(graph_objects)
#that's the CURRENT list of graph_objects
#there's also a list called "graph_objects" in gt.sage
load("gt-nb.sage")

14 loaded utilities loaded invariants loaded properties loaded theorems loaded graphs Remember to load DIMACS and Sloane graphs if you want them

len(graph_objects)

522

#ARE all graphs in gt.sage connected? YES!
for g in graph_objects:
    if not g.is_connected():
        print g

k3.graph6_string()

'Bw'

for g in graph_objects:
    if g.order() < 40:
        if not conjs[0](g):
            print g.graph6_string()
            print g.name()
            g.show()
            break

QpDHGOBCG?G@?@??o@G?a?AC@AG Blanusa Second Snark Graph

blanusa2 = graphs.BlanusaSecondSnarkGraph()
blanusa2.is_hamiltonian()

False

#blanusa2 is a CE to the last conjecture
#Run 3 of Day 3

current_graph_objects = [k3,pete,c5,k5_5,k3_4,EH,c7_chord,bow_tie,k5,p3,glasses,fish,c5_tail,triangle_with_tail]
current_graph_objects.append(blanusa2)

#properties = [Graph.is_hamiltonian, Graph.is_clique, Graph.is_regular,Graph.is_cycle,Graph.is_bipartite,Graph.is_chordal,Graph.is_strongly_regular,Graph.is_eulerian, Graph.is_triangle_free, Graph.is_distance_regular, Graph.is_perfect, Graph.is_planar]

#the properties list used in the conjecturing program will be the on from gt.sage

property_of_interest = properties.index(Graph.is_hamiltonian)

theorem1 = lambda g: g.is_bipartite() and g.is_strongly_regular()

theorems = [Graph.is_cycle, Graph.is_clique, theorem1]

conjs = propertyBasedConjecture(current_graph_objects, properties, property_of_interest, theory = theorems)
for c in conjs:
    print c

conjs

conjs

3+4

7

load("gt-nb.sage")

loaded utilities loaded invariants loaded properties loaded theorems loaded graphs Remember to load DIMACS and Sloane graphs if you want them

graph_objects.index(frucht)

Error in lines 1-1 Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1043, in execute exec compile(block+'\n', '', 'single', flags=compile_flags) in namespace, locals File "", line 1, in <module> NameError: name 'frucht' is not defined

frucht = graphs.FruchtGraph()
frucht.is_hamiltonian()

True

frucht.show()

#NOTE: no sufficient condition conjectures found for the only non-covered current graph: c7_chord
#add frucht graph & heawood
heawood = graphs.HeawoodGraph()
heawood.is_hamiltonian()

True

heawood.show()

#Run 4 of Day 3

current_graph_objects = [k3,pete,c5,k5_5,k3_4,EH,c7_chord,bow_tie,k5,p3,glasses,fish,c5_tail,triangle_with_tail]
current_graph_objects.append(blanusa2)
current_graph_objects.append(frucht)
current_graph_objects.append(heawood)

#properties = [Graph.is_hamiltonian, Graph.is_clique, Graph.is_regular,Graph.is_cycle,Graph.is_bipartite,Graph.is_chordal,Graph.is_strongly_regular,Graph.is_eulerian, Graph.is_triangle_free, Graph.is_distance_regular, Graph.is_perfect, Graph.is_planar]

#the properties list used in the conjecturing program will be the on from gt.sage

property_of_interest = properties.index(Graph.is_hamiltonian)

theorem1 = lambda g: g.is_bipartite() and g.is_strongly_regular()

theorems = [Graph.is_cycle, Graph.is_clique, theorem1]

conjs = propertyBasedConjecture(current_graph_objects, properties, property_of_interest, theory = theorems)
for c in conjs:
    print c

((is_planar)&(is_regular))->(is_hamiltonian) ((is_gallai_tree)^(is_chordal))->(is_hamiltonian) ((is_perfect)&(is_distance_regular))->(is_hamiltonian)

duplex = Graph("Iv?GOKFY?")
duplex.show()

for g in graph_objects:
    if g.is_isomorphic(duplex):
        print g.name()
        g.show()

CGT Page 13, Bottom

#Run 5 of Day 3
#duplex is a counterexample to: planar & regular implies hamiltonian

current_graph_objects = [k3,pete,c5,k5_5,k3_4,EH,c7_chord,bow_tie,k5,p3,glasses,fish,c5_tail,triangle_with_tail]
current_graph_objects.append(blanusa2)
current_graph_objects.append(frucht)
current_graph_objects.append(heawood)
current_graph_objects.append(duplex)

#properties = [Graph.is_hamiltonian, Graph.is_clique, Graph.is_regular,Graph.is_cycle,Graph.is_bipartite,Graph.is_chordal,Graph.is_strongly_regular,Graph.is_eulerian, Graph.is_triangle_free, Graph.is_distance_regular, Graph.is_perfect, Graph.is_planar]

#the properties list used in the conjecturing program will be the on from gt.sage

property_of_interest = properties.index(Graph.is_hamiltonian)

theorem1 = lambda g: g.is_bipartite() and g.is_strongly_regular()

theorems = [Graph.is_cycle, Graph.is_clique, theorem1]

conjs = propertyBasedConjecture(current_graph_objects, properties, property_of_interest, theory = theorems)
for c in conjs:
    print c

((is_van_den_heuvel)&(is_planar))->(is_hamiltonian) ((is_perfect)&(is_distance_regular))->(is_hamiltonian)

blanusa2.is_distance_regular()

False

save(conjs,'conjectures17may1118am')

Error in lines 1-1 Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1043, in execute exec compile(block+'\n', '', 'single', flags=compile_flags) in namespace, locals File "", line 1, in <module> File "sage/structure/sage_object.pyx", line 1143, in sage.structure.sage_object.save (build/cythonized/sage/structure/sage_object.c:13738) s = cPickle.dumps(obj, protocol=2) TypeError: expected string or Unicode object, NoneType found

#distreg = [g for g in graph_objects if (g.is_distance_regular())]
for g in distreg:
    print g, g.is_perfect()
perfdistreg = [g for g in distreg if (g.is_perfect())]              

Biggs-Smith graph False Brouwer-Haemers False Clebsch graph False Coxeter Graph False Desargues Graph True Foster Graph True Gosset Graph False Hall-Janko graph False Heawood graph True Higman-Sims graph False Hoffman-Singleton graph False Janko-Kharaghani-Tonchev False Klein 7-regular Graph False Pappus Graph True Perkel Graph False Petersen graph False Shrikhande graph False Sims-Gewirtz Graph False Sylvester Graph False Thomsen graph True Tutte 12-Cage True Tutte-Coxeter graph True Wells graph False Hexahedron True Dodecahedron False Octahedron True Icosahedron False Cameron Graph False M22 Graph False McLaughlin False Local McLaughlin Graph

len(perfdistreg)

Error in lines 1-1 Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1043, in execute exec compile(block+'\n', '', 'single', flags=compile_flags) in namespace, locals File "", line 1, in <module> NameError: name 'perfdistreg' is not defined