e08_graph_conjecturing.sagews

#the example from the Conjecturing Project website
load('conjecturing.py')
def max_degree(g):
    return max(g.degree())
invariants = [Graph.size, Graph.order, max_degree]
objects = [graphs.CompleteGraph(n) for n in [3,4,5]]
conjecture(objects, invariants, 0)

[size(x) <= 2*order(x), size(x) <= max_degree(x)^2 - 1, size(x) <= 1/2*max_degree(x)*order(x)]

#defining the complete graphs on 3,4,5, vertices
k3=graphs.CompleteGraph(3)
k4=graphs.CompleteGraph(4)
k5=graphs.CompleteGraph(5)

k3.show()
k4.show()
k5.show()

#a new run, with named graphs, only 2 invariants, with size as the invariant that appears on the left
load('conjecturing.py')
def max_degree(g):
    return max(g.degree())
invariants = [Graph.size, Graph.order]
objects = [k3,k4,k5]
conjecture(objects, invariants, invariants.index(Graph.size))

[size(x) <= 2*order(x), size(x) <= (order(x) - 1)^2 - 1, size(x) <= floor(sinh(1/2*order(x) + 1/2))]

#found:
#Prop. If g is complete with order n, then size of g is n(n-1)/2
#CE = counterexample
#k6 is a CE to: size(x) <= 2*order(x)

load('conjecturing.py')

def max_degree(g):
    return max(g.degree())

k3=graphs.CompleteGraph(3)
k4=graphs.CompleteGraph(4)
k5=graphs.CompleteGraph(5)
k6=graphs.CompleteGraph(6)

invariants = [Graph.size, Graph.order]
objects = [k3,k4,k5,k6]
conjecture(objects, invariants, invariants.index(Graph.size))

[size(x) <= floor(sinh(1/2*order(x) + 1/2)), size(x) <= (order(x) - 1)^2 - 1, size(x) <= 2*order(x) + 3]

#conjecture: size(x) <= 2*order(x) + 3, is false for a complete graph of order 7
#k7 is a CE
#add K7 and generate new conjectures
load('conjecturing.py')

def max_degree(g):
    return max(g.degree())

k3=graphs.CompleteGraph(3)
k4=graphs.CompleteGraph(4)
k5=graphs.CompleteGraph(5)
k6=graphs.CompleteGraph(6)
k7=graphs.CompleteGraph(7)

invariants = [Graph.size, Graph.order]
objects = [k3,k4,k5,k6,k7]
conjecture(objects, invariants, invariants.index(Graph.size))

[size(x) <= floor(sinh(1/2*order(x) + 1/2)), size(x) <= (order(x) - 1)^2 - 1, size(x) <= floor(sinh(sqrt(2)*sqrt(order(x))))]

#conjecture: size(x) <= 2*order(x) + 3, is false for a complete graph of order 7
#k7 is a CE
#add K7 and generate new conjectures
load('conjecturing.py')

def max_degree(g):
    return max(g.degree())


k3=graphs.CompleteGraph(3)
k4=graphs.CompleteGraph(4)
k5=graphs.CompleteGraph(5)
k6=graphs.CompleteGraph(6)
k7=graphs.CompleteGraph(7)

invariants = [Graph.size, Graph.order]
objects = [k3,k4,k5,k6,k7]
conjecture(objects, invariants, invariants.index(Graph.size))

[size(x) <= floor(sinh(1/2*order(x) + 1/2)), size(x) <= (order(x) - 1)^2 - 1, size(x) <= floor(sinh(sqrt(2)*sqrt(order(x))))]

#k2 is a CE to size(x) <= (order(x) - 1)^2 - 1
#claim: size(x) <= (order(x) - 1)^2 - 1 is true for connected graphs with order >= 3
#proved: size(x) <= (order(x) - 1)^2 is true for connected graphs

load('conjecturing.py')

def max_degree(g):
    return max(g.degree())

k3=graphs.CompleteGraph(3)
k4=graphs.CompleteGraph(4)
k5=graphs.CompleteGraph(5)
k6=graphs.CompleteGraph(6)
k7=graphs.CompleteGraph(7)
k2=graphs.CompleteGraph(2)

invariants = [Graph.size, Graph.order]
objects = [k3,k4,k5,k6,k7,k2]
conjecture(objects, invariants, invariants.index(Graph.size))

[size(x) <= (order(x) - 1)^2, size(x) <= floor(sinh(order(x) - 1)), size(x) <= floor(sinh(1/2*order(x) + 1/2)), size(x) <= floor(sinh(sqrt(2)*sqrt(order(x))))]

#lets add a new graph with the hope that we can get some non-sinh conjectures
#want path with order 3, p3
p3 = Graph(3)
p3.add_edge(0,1)
p3.add_edge(1,2)

p3.show()

load('conjecturing.py')

def max_degree(g):
    return max(g.degree())

k3=graphs.CompleteGraph(3)
k4=graphs.CompleteGraph(4)
k5=graphs.CompleteGraph(5)
k6=graphs.CompleteGraph(6)
k7=graphs.CompleteGraph(7)
k2=graphs.CompleteGraph(2)

#PATH ON 3 VERTICES
p3 = Graph(3)
p3.add_edge(0,1)
p3.add_edge(1,2)

#path on 4 vertices
p4 = Graph(4)
p4.add_edge(0,1)
p4.add_edge(1,2)
p4.add_edge(2,3)

#star with 3 rays, s3 (some graph theorists call this s4)
s3=Graph(4)
s3.add_edge(0,1)
s3.add_edge(0,2)
s3.add_edge(0,3)

invariants = [Graph.size, Graph.order]
objects = [k3,k4,k5,k6,k7,k2,p3,p4,s3]
conjecture(objects, invariants, invariants.index(Graph.size))

[size(x) <= (order(x) - 1)^2, size(x) <= floor(sinh(order(x) - 1)), size(x) <= floor(sinh(1/2*order(x) + 1/2)), size(x) <= floor(sinh(sqrt(2)*sqrt(order(x))))]

s=graphs.StarGraph(3)
s.show()

#we've proved:
#for any graph with order n, size <= size of the complete graph with orner n = n(n-1)/2
#size of any graph order n <= (n-1)^2
#(stronger) for any graph with order n>2, size <= (n-1)^2-1

#lower bound conjectures
load('conjecturing.py')

def max_degree(g):
    return max(g.degree())

k3=graphs.CompleteGraph(3)
k4=graphs.CompleteGraph(4)
k5=graphs.CompleteGraph(5)
k6=graphs.CompleteGraph(6)
k7=graphs.CompleteGraph(7)
k2=graphs.CompleteGraph(2)

#PATH ON 3 VERTICES
p3 = Graph(3)
p3.add_edge(0,1)
p3.add_edge(1,2)

#path on 4 vertices
p4 = Graph(4)
p4.add_edge(0,1)
p4.add_edge(1,2)
p4.add_edge(2,3)

#star with 3 rays, s3 (some graph theorists call this s4)
s3=Graph(4)
s3.add_edge(0,1)
s3.add_edge(0,2)
s3.add_edge(0,3)

invariants = [Graph.size, Graph.order]
objects = [k3,k4,k5]
conjecture(objects, invariants, invariants.index(Graph.size),upperBound=False)

[size(x) >= order(x), size(x) >= 10^ceil(cos(order(x))), size(x) >= ceil(tan(log(order(x))))]

#lower bound conjectures
load('conjecturing.py')

def max_degree(g):
    return max(g.degree())

k3=graphs.CompleteGraph(3)
k4=graphs.CompleteGraph(4)
k5=graphs.CompleteGraph(5)
k6=graphs.CompleteGraph(6)
k7=graphs.CompleteGraph(7)
k2=graphs.CompleteGraph(2)

#PATH ON 3 VERTICES
p3 = Graph(3)
p3.add_edge(0,1)
p3.add_edge(1,2)

#path on 4 vertices
p4 = Graph(4)
p4.add_edge(0,1)
p4.add_edge(1,2)
p4.add_edge(2,3)

#star with 3 rays, s3 (some graph theorists call this s4)
s3=Graph(4)
s3.add_edge(0,1)
s3.add_edge(0,2)
s3.add_edge(0,3)

invariants = [Graph.size, Graph.order]
objects = [k3,k4,k5,k2]
conjecture(objects, invariants, invariants.index(Graph.size),upperBound=False)

[size(x) >= order(x) - 1, size(x) >= 2*order(x) - 3, size(x) >= ceil(tan(log(order(x)))), size(x) >= 10^ceil(cos(order(x)))]

#NEW CONJECTURES for size, order, min degree, max degree
(1) SIZE <= 1/2(MAX_DEGREE)(ORDER)
(2) SIZE <=

#proved: size(x) <= (order(x) - 1)^2 is true for connected graphs
#add this fact as part of our "theory"


load('conjecturing.py')

def max_degree(g):
    return max(g.degree())

#theorem1 is a graph invariant
theorem1 = lambda g: (g.order()-1)^2

k3=graphs.CompleteGraph(3)
k4=graphs.CompleteGraph(4)
k5=graphs.CompleteGraph(5)
k6=graphs.CompleteGraph(6)
k7=graphs.CompleteGraph(7)
k2=graphs.CompleteGraph(2)

theorems = [theorem1]

invariants = [Graph.size, Graph.order]
objects = [k3,k4,k5,k6,k7,k2]
conjecture(objects, invariants, invariants.index(Graph.size),theory=theorems)

[size(x) <= floor(sinh(order(x) - 1)), size(x) <= floor(sinh(1/2*order(x) + 1/2)), size(x) <= floor(sinh(sqrt(2)*sqrt(order(x))))]

theorem1(k3)

3

theorem1(k4)

8

theorem1(k2)

0

#claim: size >= 1/2(min_degree)(order)
#we'll add this to the "theory"
#lower bound conjectures
load('conjecturing.py')

def max_degree(g):
    return max(g.degree())

def min_degree(g):
    return min(g.degree())


k3=graphs.CompleteGraph(3)
k4=graphs.CompleteGraph(4)
k5=graphs.CompleteGraph(5)
p3 = graphs.PathGraph(3)

half_min_deg_times_order = lambda g: (1/2)*(min_degree(g))*g.order()
theory = [half_min_deg_times_order]

invariants = [Graph.size, Graph.order, max_degree, min_degree]
objects = [k3,k4,k5,p3]
conjecture(objects, invariants, invariants.index(Graph.size),upperBound=False,theory = theory)

[size(x) >= max_degree(x), size(x) >= min_degree(x) + 1, size(x) >= (max_degree(x) - 1)^2 + 1, size(x) >= ceil(tan(log(order(x))))]

3+4

7

#claim: size <= 1/2(max_degree)(order)
#we'll add this to the "theory"
#get new upper bound conjectures
#when the objects are k3,k4,k5 the theoretical upper bound is exactly the size
#either size = 1/2*max_degree*order for all connected graphs, or there's a graph where equality doesn't hold
#note: its not equality for p3, we'll add that

load('conjecturing.py')

def max_degree(g):
    return max(g.degree())

def min_degree(g):
    return min(g.degree())


k3=graphs.CompleteGraph(3)
k4=graphs.CompleteGraph(4)
k5=graphs.CompleteGraph(5)
p3 = graphs.PathGraph(3)

theorem1 = lambda g: (1/2)*(max_degree(g))*g.order()
theory = [theorem1]

invariants = [Graph.size, Graph.order, max_degree, min_degree]
objects = [k3,k4,k5,p3]
conjecture(objects, invariants, invariants.index(Graph.size),theory = theory)

[size(x) <= 1/2*(min_degree(x) + 1)*max_degree(x), size(x) <= max_degree(x)^min_degree(x), size(x) <= (min_degree(x) + 1)^(max_degree(x) - 1)]

#experiments for integers
load('conjecturing.py')

def distinct_prime_factors(n):
    return len(factor(n))

def total_number_of_factors(n):
    return (sum([factor(n)[i][1] for i in range(len(factor(n)))]))

def number_of_digits(n):
    return len(n.digits())

distinct_prime_factors(6)
distinct_prime_factors(60)

2 3

total_number_of_factors(6)
total_number_of_factors(60)

2 4

number_of_digits(6)
number_of_digits(60)

1 2

#experiments for integers
load('conjecturing.py')

def distinct_prime_factors(n):
    return len(factor(n))

def total_number_of_factors(n):
    return (sum([factor(n)[i][1] for i in range(len(factor(n)))]))

def number_of_digits(n):
    return len(n.digits())

def number(n):
    return n

objects = [6,30,60,1000]
invariants = [distinct_prime_factors,total_number_of_factors,number_of_digits,number]

conjecture(objects,invariants,invariants.index(number))

[number(x) <= ceil(e^number_of_digits(x))^2 - total_number_of_factors(x), number(x) <= 10^(distinct_prime_factors(x) + 1), number(x) <= (number_of_digits(x) + 1)^total_number_of_factors(x) + distinct_prime_factors(x), number(x) <= 10^number_of_digits(x) - 2*distinct_prime_factors(x)]

#9 is a CE to the 4th conjecture
#add 9 to the objects, re-run
#experiments for integers
load('conjecturing.py')

def distinct_prime_factors(n):
    return len(factor(n))

def total_number_of_factors(n):
    return (sum([factor(n)[i][1] for i in range(len(factor(n)))]))

def number_of_digits(n):
    return len(n.digits())

def number(n):
    return n

objects = [6,30,60,1000,9]
invariants = [distinct_prime_factors,total_number_of_factors,number_of_digits,number]

conjecture(objects,invariants,invariants.index(number))

[number(x) <= 10^number_of_digits(x) - 1, number(x) <= 10^(distinct_prime_factors(x) + 1), number(x) <= 10^floor(1/2*total_number_of_factors(x))*distinct_prime_factors(x), number(x) <= -distinct_prime_factors(x)^2 + 10^number_of_digits(x), number(x) <= floor((cosh(number_of_digits(x)) + total_number_of_factors(x))^2)]

#101 is prime and a counterexample to the 2nd conjecture

load('conjecturing.py')

def distinct_prime_factors(n):
    return len(factor(n))

def total_number_of_factors(n):
    return (sum([factor(n)[i][1] for i in range(len(factor(n)))]))

def number_of_digits(n):
    return len(n.digits())

def number(n):
    return n

objects = [6,30,60,1000,9,101]
invariants = [distinct_prime_factors,total_number_of_factors,number_of_digits,number]

conjecture(objects,invariants,invariants.index(number))

[number(x) <= 10^number_of_digits(x) - 1, number(x) <= 10^(distinct_prime_factors(x) + 1) + 1, number(x) <= -distinct_prime_factors(x)^2 + 10^number_of_digits(x), number(x) <= floor((cosh(number_of_digits(x)) + total_number_of_factors(x))^2), number(x) <= 10^(1/2*number_of_digits(x) + 1), number(x) <= e^(2*total_number_of_factors(x)/arccosh(distinct_prime_factors(x)))]