We saw that systems of polynomial equations can be used to studying GRAPHS. We stated an application to finding independent sets:An independent set of a graph is a set of vertices no two of them are adjacent. Polynomials can be used for finding independent sets of vertices.Theorem: A graph G has an independent set of size k if and only if the following systemof equations has a solution:x_i^2 - x_i = 0 for each vertex i = 1 .. n andx_i*x_j = 0 for every (i,j) in the edge setx_1 + x_2 + .. x_n = k###############################################################################Similarly we can do it for the k-coloring problem : Theorem: The vertices of a graph G can be colored with k colors in such a waythat no two adjacent vertices are of the same color if and only if the following systemof equations has a solution (in fact each solution of the system gives rise to k! colorings).x_i^k-1 = 0 for each vertex i=1...n andx_i^(k-1)+x_i^(k-2)x_j+x_i^(k-3)x_j^2+....+x_j^(k-1) = 0 for each edge of the graph.###############################################################################The graph isomorphism problem is one of the most famous problems in ModernComputer science. It deals with deciding when two graphs are actually the samesame graph with different labels. It is a famous open problem to find a polynomialtime algorithm, or prove that none exists, for this problem.Using Groebner bases we can decide whether two graphs are isomorphic.This is true if a certain system of polynomial equations is true. We first load the graph theory package. With the package we can answer millions of different questions!!!with(GraphTheory);We can generate a random graph with specified number of vertices and even output its adjacency matrix or draw a picture.with(RandomGraphs); G:=RandomGraph(5,8); Vertices(G); Edges(G);AG:=AdjacencyMatrix(G);DrawGraph(G);IsPlanar(G);
with(LinearAlgebra);Now we generate another graph by permuting the vertices of G using the permutation matrix QQ:=Matrix([[0,1,0,0,0], [0,0,1,0,0], [0,0,0,1,0], [0,0,0,0,1], [1,0,0,0,0]]);AH:=Multiply(Multiply(Q,AG),MatrixInverse(Q)); AG;AG - AH;Every permutation can be represented by a permutation matrix it satisfies that each row sum and column sum is equal to oneand that the entries are zeros and ones only.These conditions can be setup by a system of equations below (highest degree is 2).In what follows we codify a system of equations that will detect when two graphs are isomorphic:P denotes a generic matrix of permutations and F will store all the polynomials we need to solve.F:={}:P:=Matrix([[x[1,1],x[1,2],x[1,3],x[1,4],x[1,5]],[x[2,1],x[2,2],x[2,3],x[2,4],x[2,5]],[x[3,1],x[3,2],x[3,3],x[3,4],x[3,5]],[x[4,1],x[4,2],x[4,3],x[4,4],x[4,5]],[x[5,1],x[5,2],x[5,3],x[5,4],x[5,5]]]);R:=convert(Multiply(P,Vector([1,1,1,1,1])),list):S:=convert(Multiply(Transpose(P),Vector([1,1,1,1,1])),list):R;S;for i from 1 to 5 do F:=F union {op(i,R)-1,op(i,S)-1}:od:for i from 1 to 5 do for j from 1 to 5 do F:=F union {P[i,j]^2-P[i,j]}: od:od:F;If the graphs G,H are isomorphic there must exist a permutation matrix whose multiplication PA_GP^{-1}=A_HThese provide us with a bunch of linear equations that need to be satisfied.OO:=Add(Multiply(P,AG),Multiply(AH,P),1,-1);for i from 1 to 5 do for j from 1 to 5 do F:=F union {OO[i,j]}: od:od:Now we use Groebner bases for deciding whether these two graphsare isomorphic. The polynomial system is feasible if and only if the graphs are isomorphic.with(Groebner);GG:=Basis(convert(F,list),plex(x[1,1],x[1,2],x[1,3],x[1,4],x[1,5],x[2,1],x[2,2]\134,x[2,3],x[2,4],x[2,5],x[3,1],x[3,2],x[3,3],x[3,4],x[3,5],x[4,1],x[4,2],x[4,3],x\134[4,4],x[4,5],x[5,1],x[5,2],x[5,3],x[5,4],x[5,5]));map(m->LeadingMonomial(m,plex(x[1,1],x[1,2],x[1,3],x[1,4],x[1,5],x[2,1],x[2,2],x[2,3],x[2,4],x[2,5],x[3,1],x[3,2],x[3,3],x[3,4],x[3,5],x[4,1],x[4,2],x[4,3],x[4,4],x[4,5],x[5,1],x[5,2],x[5,3],x[5,4],x[5,5])),GG);Mathematical Logic is important not just in the foundations of mathematics, but also in computerscience, circuit design, artificial intelligence, programming languages, etc. Many problems in logic can be encoded using polynomial ideals too!!A proof system in logic consists of axioms and inference rules. By applying those rulesrepeatedly we obtain theorems. Here we deal with propositional logic. We only have variablesthat are true or false and we use the logic connectives: NOT, OR, AND, IMPLIES. Thereare no quantifiers! An example of an axiom is that x OR (NOT x) is always true. In a typical proof system aims one proves that a certain set of formulas S is unsatisfiable= impossible to makeall formulas in S true by giving appropiate values to its variables. Example: x AND (NOT x) is an unsatisfiable system.If the system is unsatisfiable we wish to find a refutation, a proof that it is unsatisfiable by deriving the simplest contradiction=false.There are many proof systems around: Tableaux, Horn clause resolution, Davis-Putnam procedure, Frege-Hilbert proofs, etc.The key question is: How long is a shortest refutation of a given unsatisfiable set of logic formulas? How hard is it to finda short refutation if one exists? Example: The pigeonhole principle says that it is impossible to fit n+1 pigeons into n pigeonholes without a collision.Haken proved that any resolution or proof of this impossibility requires exponential length at least 2^{cn} for some constant c.Here we represent propositional logic as polynomial relations: We associate to the value true=0 and false=1, similarly we associate to a formula a polynomial as follows:NOT f <----> 1-ff OR g <----> f*gf AND g <----> 1-(1-f)*(1-g)f IMPLIES g <----> (1-f)*gLemma: Every propositional formula corresponds to a polynomial. The rules of inferences are precisely the rules of membershipin the ideal: Namely if f, g are valid then af+bg and (x_i) *f are valid as well. Thus the valid formulas are precisely themembers of the ideal.Example: { x OR y, z OR w, u OR v, (NOT x) OR (NOT z), (NOT x) OR (NOT u), (NOT y) OR (NOT u), (NOT y) OR (NOT w), (NOT y) OR (NOT v), (NOT w) OR (NOT v)}can be transfered to a system of equations (see below)Lemma: The associated system of equations together with the conditions that each variable must be either zero or one will have a solution if and only if the logical formula is satisfied.restart; with(Groebner);F:=[x^2-x,y^2-y,z^2-z,w^2-w, u^2-u, v^2-v, x*y, z*w, u*v, (1-x)*(1-z), (1-x)*(1-u), (1-y)*(1-u), (1-y)*(1-w), (1-y)*(1-v), (1-w)*(1-v)];Basis(F,plex(x,y,z,w,u,v),characteristic=2);A system of polynomials can be refuted if we can prove that 1 is in the ideal they generate! This can be done by usingGroebner bases. These systems were introduced by Clegg, Edmonds, and Impagliazzo in 1996. Similarly, remember the Hilbert Nullstellensatz guarantees that the system has no solution (unsatisfiable) if and only if 1is in the ideal! The Nullstellesatz gives another way to prove that logical systems are infeasible.TTdSMApJNVJUQUJMRV9TQVZFLzM5ODQ0MTg0WCwlKWFueXRoaW5nRzYjJSpzeW1tZXRyaWNHNiJbZ2whIiYiISEjMCImIiYiIiEiIiJGKUYpRilGKEYpRilGKEYoRihGKUYoRilGKEYnTTdSMApJNVJUQUJMRV9TQVZFLzM5ODUwNDI0WCwlKWFueXRoaW5nRzYiRiVbZ2whIiUhISEjOiImIiYiIiFGJkYmRiYiIiJGJ0YmRiZGJkYmRiZGJ0YmRiZGJkYmRiZGJ0YmRiZGJkYmRiZGJ0YmRiU=TTdSMApJNVJUQUJMRV9TQVZFLzM5ODU3MDI0WCwlKWFueXRoaW5nRzYiRiVbZ2whIiUhISEjOiImIiYiIiEiIiJGJ0YmRidGJ0YmRiZGJ0YnRidGJkYmRidGJ0YmRidGJ0YmRidGJ0YnRidGJ0YmRiU=TTdSMApJNVJUQUJMRV9TQVZFLzM5ODQ0MTg0WCwlKWFueXRoaW5nRzYjJSpzeW1tZXRyaWNHNiJbZ2whIiYiISEjMCImIiYiIiEiIiJGKUYpRilGKEYpRilGKEYoRihGKUYoRilGKEYnTTdSMApJNVJUQUJMRV9TQVZFLzM5ODU3NjI0WCwlKWFueXRoaW5nRzYiRiVbZ2whIiUiISEjOiImIiYiIiFGJkYmIiIiRiZGJkYmRidGJiEiIkYmRidGJkYoRiZGJ0YmRihGJkYmRiZGKEYmRiZGJkYlTTdSMApJNVJUQUJMRV9TQVZFLzM5ODU3NzQ0WCwlKWFueXRoaW5nRzYiRiVbZ2whIiUhISEjOiImIiYmJSJ4RzYkIiIiRikmRic2JCIiI0YpJkYnNiQiIiRGKSZGJzYkIiIlRikmRic2JCIiJkYpJkYnNiRGKUYsJkYnNiRGLEYsJkYnNiRGL0YsJkYnNiRGMkYsJkYnNiRGNUYsJkYnNiRGKUYvJkYnNiRGLEYvJkYnNiRGL0YvJkYnNiRGMkYvJkYnNiRGNUYvJkYnNiRGKUYyJkYnNiRGLEYyJkYnNiRGL0YyJkYnNiRGMkYyJkYnNiRGNUYyJkYnNiRGKUY1JkYnNiRGLEY1JkYnNiRGL0Y1JkYnNiRGMkY1JkYnNiRGNUY1RiU=TTdSMApJNVJUQUJMRV9TQVZFLzM5ODYwOTg0WCwlKWFueXRoaW5nRzYiRiVbZ2whIiUhISEjOiImIiYsMCYlInhHNiQiIiIiIiNGKiZGKDYkRioiIiRGKiZGKDYkRioiIiVGKiZGKDYkRioiIiZGKiZGKDYkRitGKiEiIiZGKDYkRi5GKkY3JkYoNiRGNEYqRjcsMCZGKDYkRitGK0YqJkYoNiRGK0YuRiomRig2JEYrRjFGKiZGKDYkRitGNEYqJkYoNiRGKkYqRjcmRig2JEYxRipGN0Y6RjcsMCZGKDYkRi5GK0YqJkYoNiRGLkYuRiomRig2JEYuRjFGKiZGKDYkRi5GNEYqRkVGN0ZHRjdGOkY3LDAmRig2JEYxRitGKiZGKDYkRjFGLkYqJkYoNiRGMUYxRiomRig2JEYxRjRGKkY1RjdGOEY3RjpGNywyJkYoNiRGNEYrRiomRig2JEY0Ri5GKiZGKDYkRjRGMUYqJkYoNiRGNEY0RipGRUY3RjVGN0Y4RjdGR0Y3LC5GRUYqRixGKkYvRipGPUY3RkpGN0ZmbkY3LC5GNUYqRj9GKkZBRipGJ0Y3RlNGN0ZmbkY3LC5GOEYqRkxGKkZORipGJ0Y3RlNGN0ZmbkY3LC5GR0YqRlVGKkZXRipGPUY3RkpGN0ZmbkY3LDBGOkYqRmhuRipGam5GKkYnRjdGPUY3RkpGN0ZTRjcsLkZFRipGJ0YqRjJGKkY/RjdGTEY3RmhuRjcsLkY1RipGPUYqRkNGKkYsRjdGVUY3RmhuRjcsLkY4RipGSkYqRlBGKkYsRjdGVUY3RmhuRjcsLkZHRipGU0YqRllGKkY/RjdGTEY3RmhuRjcsMEY6RipGZm5GKkZcb0YqRixGN0Y/RjdGTEY3RlVGNywuRkVGKkYnRipGMkYqRkFGN0ZORjdGam5GNywuRjVGKkY9RipGQ0YqRi9GN0ZXRjdGam5GNywuRjhGKkZKRipGUEYqRi9GN0ZXRjdGam5GNywuRkdGKkZTRipGWUYqRkFGN0ZORjdGam5GNywwRjpGKkZmbkYqRlxvRipGL0Y3RkFGN0ZORjdGV0Y3LC5GRUYqRixGKkYvRipGQ0Y3RlBGN0Zcb0Y3LC5GNUYqRj9GKkZBRipGMkY3RllGN0Zcb0Y3LC5GOEYqRkxGKkZORipGMkY3RllGN0Zcb0Y3LC5GR0YqRlVGKkZXRipGQ0Y3RlBGN0Zcb0Y3LDBGOkYqRmhuRipGam5GKkYyRjdGQ0Y3RlBGN0ZZRjdGJQ==