3+4

7

is_prime(47)

True

is_prime(12345678910987654321)

True

is_prime(1111111111111111111)

True

k3 = graphs.CompleteGraph(3)

k3

Complete graph: Graph on 3 vertices

k3.show()

k3.is_hamiltonian()

True

k3.is_clique??

File: /ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py Source: def is_clique(self, vertices=None, directed_clique=False): """ Tests whether a set of vertices is a clique A clique is a set of vertices such that there is an edge between any two vertices. INPUT: - ``vertices`` - Vertices can be a single vertex or an iterable container of vertices, e.g. a list, set, graph, file or numeric array. If not passed, defaults to the entire graph. - ``directed_clique`` - (default False) If set to False, only consider the underlying undirected graph. If set to True and the graph is directed, only return True if all possible edges in _both_ directions exist. EXAMPLES:: sage: g = graphs.CompleteGraph(4) sage: g.is_clique([1,2,3]) True sage: g.is_clique() True sage: h = graphs.CycleGraph(4) sage: h.is_clique([1,2]) True sage: h.is_clique([1,2,3]) False sage: h.is_clique() False sage: i = graphs.CompleteGraph(4).to_directed() sage: i.delete_edge([0,1]) sage: i.is_clique() True sage: i.is_clique(directed_clique=True) False """ if directed_clique and self._directed: subgraph=self.subgraph(vertices, immutable = False) subgraph.allow_loops(False) subgraph.allow_multiple_edges(False) n=subgraph.order() return subgraph.size()==n*(n-1) else: if vertices is None: subgraph = self else: subgraph=self.subgraph(vertices) if self._directed: subgraph = subgraph.to_simple() n=subgraph.order() return subgraph.size()==n*(n-1)/2

load("conjecturing.py")

propertyBasedConjecture?

File: /home/user/conjecturing.py Signature : propertyBasedConjecture(objects, properties, mainProperty, time=5, debug=False, verbose=False, sufficient=True, operators=None, theory=None, precomputed=None) Docstring : Runs the conjecturing program for properties with the provided objects, properties and main property. This method requires the program "expressions" to be in the current working directory of Sage. INPUT: * "objects" - a list of objects about which conjectures should be made. * "properties" - a list of functions (callable objects) which take a single argument and return a boolean value. Each function should be able to produce a value for each of the elements of objects. * "mainProperty" - an integer that is the index of one of the elements of properties. All conjectures will then be a bound for the property that corresponds to this index. * "sufficient" - if given, this boolean value specifies whether sufficient or necessary conditions for the main property should be generated. If "True", then sufficient conditions are generated. If "False", then necessary conditions are generated. The default value is "True" * "time" - if given, this integer specifies the number of seconds before the conjecturing program times out and returns the best conjectures it has at that point. The default value is 5. * "theory" - if given, specifies a list of known bounds. If this is "None", then no known bounds are used. Otherwise each conjecture will have to be more significant than the conditions in this list. The default value is "None". * "operators" - if given, specifies a set of operators that can be used. If this is "None", then all known operators are used. Otherwise only the specified operators are used. It is advised to use the method "allPropertyBasedOperators()" to get a set containing all operators and then removing the operators which are not needed. The default value is "None". * "debug" - if given, this boolean value specifies whether the output of the program "expressions" to "stderr" is printed. The default value is "False". * "verbose" - if given, this boolean value specifies whether the program "expressions" is ran in verbose mode. Note that this has nu purpose if "debug" is not also set to "True". The default value is "False". EXAMPLES: A very simple example uses just two properties of integers and generates sufficient conditions for an integer to be prime based on the integer 3: >>> propertyBasedConjecture([3], [is_prime,is_even], 0) [(~(is_even))->(is_prime)] We can also generate necessary condition conjectures: >>> propertyBasedConjecture([3], [is_prime,is_even], 0, sufficient=False) [(is_prime)->(~(is_even))] In some cases strange conjectures might be produced or one conjecture you might be expecting does not show up. In this case you can use the "debug" and "verbose" option to find out what is going on behind the scene. By enabling "debug" the program prints the reason it stopped generating conjectures (time limit, no better conjectures possible, ...) and gives some statistics about the number of conjectures it looked at: >>> propertyBasedConjecture([3], [is_prime,is_even], 0, debug=True) > Generation process was stopped by the conjecturing heuristic. > Found 2 unlabeled trees. > Found 2 labeled trees. > Found 2 valid expressions. [(~(is_even))->(is_prime)] By also enabling "verbose", you can discover which values are actually given to the program: >>> propertyBasedConjecture([3], [is_prime,is_even], 0, debug=True, verbose=True) Using the following command ./expressions -pcv --dalmatian --all-operators --time 5 --invariant-names --output stack --sufficient --allowed-skips 0 > Invariant 1 Invariant 2 > 1) TRUE FALSE > Generating trees with 0 unary nodes and 0 binary nodes. > Saving expression > is_prime <- is_even > Status: 1 unlabeled tree, 1 labeled tree, 1 expression > Generating trees with 1 unary node and 0 binary nodes. > Conjecture is more significant for object 1. > Saving expression > is_prime <- ~(is_even) > Conjecture 2 is more significant for object 1. > Status: 2 unlabeled trees, 2 labeled trees, 2 expressions > Generation process was stopped by the conjecturing heuristic. > Found 2 unlabeled trees. > Found 2 labeled trees. > Found 2 valid expressions. [(~(is_even))->(is_prime)]

#Sample Run 1. graph_objects = [k3] properties = [Graph.is_hamiltonian, Graph.is_clique] property_of_interest = 0 propertyBasedConjecture(graphs, properties, property_of_interest)

[(is_clique)->(is_hamiltonian)]

reset("graphs")

pete = graphs.PetersenGraph() pete.show()

pete.is_hamiltonian()

False

pete.is_apex

c5 = graphs.CycleGraph(5) c5.show()

k3_4 = graphs.CompleteBipartiteGraph(3,4) k3_4.show()

k5_5 = graphs.CompleteBipartiteGraph(5,5) k5_5.show()

#Observation. (is_clique)->(is_hamiltonian) is True #Sample Run 2. Add more graphs. #Sample Run 1. graph_objects = [k3,pete,c5,k5_5,k3_4] properties = [Graph.is_hamiltonian, Graph.is_clique, Graph.is_regular,Graph.is_cycle, Graph.is_bipartite] property_of_interest = 0 propertyBasedConjecture(graph_objects, properties, property_of_interest)

[((is_bipartite)&(is_regular))->(is_hamiltonian), (is_cycle)->(is_hamiltonian)]

#generate all connected graphs on 4 vertices for g in graphs(4): if g.is_connected(): g.show()

#test is the first conjecture is true for the connected graphs on 4 vertices #((is_bipartite)&(is_regular)) #1st approach #want a counterexample (CE): a connected graph g that is bipartite, regular, and NOT hamiltonian for g in graphs(4): if g.is_connected() and g.is_bipartite() and g.is_regular() and not g.is_hamiltonian(): g.show()

#test is the first conjecture is true for the connected graphs on 5 vertices #((is_bipartite)&(is_regular)) #1st approach #want a counterexample (CE): a connected graph g that is bipartite, regular, and NOT hamiltonian for g in graphs(5): if g.is_connected() and g.is_bipartite() and g.is_regular() and not g.is_hamiltonian(): g.show()

#test is the first conjecture is true for the connected graphs on 6 vertices #((is_bipartite)&(is_regular)) #1st approach #want a counterexample (CE): a connected graph g that is bipartite, regular, and NOT hamiltonian for g in graphs(6): if g.is_connected() and g.is_bipartite() and g.is_regular() and not g.is_hamiltonian(): g.show()

#2nd way to run a test for all connected graphs on 6 vertices #note: conjs[0] = ((is_bipartite)&(is_regular))->(is_hamiltonian) for g in graphs(6): if g.is_connected(): if conjs[0](g) == False: g.show()

#2nd way to run a test for all connected graphs on 2 vertices #note: conjs[0] = ((is_bipartite)&(is_regular))->(is_hamiltonian) for g in graphs(2): if g.is_connected(): if conjs[0](g) == False: g.show() g.graph6_string()

'A_'

#how to convert from the graph6 string representation back to a useable graph useable = Graph("A_") useable.show()

#test is the first conjecture is true for the connected graphs on 7 vertices #((is_bipartite)&(is_regular)) #1st approach #want a counterexample (CE): a connected graph g that is bipartite, regular, and NOT hamiltonian for g in graphs(7): if g.is_connected() and g.is_bipartite() and g.is_regular() and not g.is_hamiltonian(): g.show()

#test is the first conjecture is true for the connected graphs on 8 vertices #((is_bipartite)&(is_regular)) #1st approach #want a counterexample (CE): a connected graph g that is bipartite, regular, and NOT hamiltonian for g in graphs(8): if g.is_connected() and g.is_bipartite() and g.is_regular() and not g.is_hamiltonian(): g.show()

#Observation. (is_clique)->(is_hamiltonian) is True #Sample Run 2 rerun. Add more graphs. #Sample Run 1. graph_objects = [k3,pete,c5,k5_5,k3_4] properties = [Graph.is_hamiltonian, Graph.is_clique, Graph.is_regular,Graph.is_cycle, Graph.is_bipartite] property_of_interest = 0 conjs = propertyBasedConjecture(graph_objects, properties, property_of_interest) for c in conjs: print c

((is_bipartite)&(is_regular))->(is_hamiltonian)
(is_cycle)->(is_hamiltonian)

#Observation: #2nd way to run a test for all connected graphs on 6 vertices #note: conjs[0] = (is_cycle)->(is_hamiltonian) is TRUE

conjs[0]

((is_bipartite)&(is_regular))->(is_hamiltonian)

conjs[0](k3)

True

conjs[0](k2)

False

k2 = graphs.CompleteGraph(2) k2.show() k2.size()

1

EH = graphs.EllinghamHorton54Graph() EH.show()

EH.is_hamiltonian()

False

EH.is_bipartite()

True

EH.degree()

[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]

EH.is_regular()

True

conjs[0](EH)

False

#EH is a CE to ((is_bipartite)&(is_regular))->(is_hamiltonian) #Sample Run 1. #Sample Run 3. Add EH graph (Ellingham-Horton-54) graph_objects = [k3,pete,c5,k5_5,k3_4,EH] properties = [Graph.is_hamiltonian, Graph.is_clique, Graph.is_regular,Graph.is_cycle, Graph.is_bipartite] property_of_interest = 0 conjs = propertyBasedConjecture(graph_objects, properties, property_of_interest) for c in conjs: print c

(is_cycle)->(is_hamiltonian)

k3.is

#no good conjectures. what should we do?!?!?! #one idea: add more properties #the produced conjecture IS sharp for ythe hamiltonian graphs that are cycles #no conjecture applies to the hamiltonian K5_5 graph graph_objects = [k3,pete,c5,k5_5,k3_4,EH] 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] property_of_interest = 0 conjs = propertyBasedConjecture(graph_objects, properties, property_of_interest) for c in conjs: print c

((is_strongly_regular)&(is_bipartite))->(is_hamiltonian)
(is_cycle)->(is_hamiltonian)

Graph.is_strongly_regular?

File: /ext/sage/sage-8.1/src/sage/graphs/base/static_dense_graph.pyx Signature : Graph.is_strongly_regular(g, parameters=False) Docstring : Tests whether "self" is strongly regular. A simple graph G is said to be strongly regular with parameters (n, k, lambda, mu) if and only if: * G has n vertices. * G is k-regular. * Any two adjacent vertices of G have lambda common neighbors. * Any two non-adjacent vertices of G have mu common neighbors. By convention, the complete graphs, the graphs with no edges and the empty graph are not strongly regular. See https://en.wikipedia.org/wiki/Strongly regular graph INPUT: * "parameters" (boolean) -- whether to return the quadruple (n, k,lambda,mu). If "parameters = False" (default), this method only returns "True" and "False" answers. If "parameters=True", the "True" answers are replaced by quadruples (n, k,lambda,mu). See definition above. EXAMPLES: Petersen's graph is strongly regular: sage: g = graphs.PetersenGraph() sage: g.is_strongly_regular() True sage: g.is_strongly_regular(parameters = True) (10, 3, 0, 1) And Clebsch's graph is too: sage: g = graphs.ClebschGraph() sage: g.is_strongly_regular() True sage: g.is_strongly_regular(parameters = True) (16, 5, 0, 2) But Chvatal's graph is not: sage: g = graphs.ChvatalGraph() sage: g.is_strongly_regular() False Complete graphs are not strongly regular. (https://trac.sagemath.org/14297) sage: g = graphs.CompleteGraph(5) sage: g.is_strongly_regular() False Completements of complete graphs are not strongly regular: sage: g = graphs.CompleteGraph(5).complement() sage: g.is_strongly_regular() False The empty graph is not strongly regular: sage: g = graphs.EmptyGraph() sage: g.is_strongly_regular() False If the input graph has loops or multiedges an exception is raised: sage: Graph([(1,1),(2,2)]).is_strongly_regular() Traceback (most recent call last): ... ValueError: This method is not known to work on graphs with loops. Perhaps this method can be updated to handle them, but in the meantime if you want to use it please disallow loops using allow_loops(). sage: Graph([(1,2),(1,2)]).is_strongly_regular() Traceback (most recent call last): ... ValueError: This method is not known to work on graphs with multiedges. Perhaps this method can be updated to handle them, but in the meantime if you want to use it please disallow multiedges using allow_multiple_edges().