-- -*- coding: utf-8 -*- -------------------------------------------------------------------------------- -- Copyright 2008, 2009, 2010 Chris Francisco, Andrew Hoefel, and Adam Van Tuyl -- -- You may redistribute this program under the terms of the GNU General Public -- License as published by the Free Software Foundation, either version 2 of the -- License, or any later version. -------------------------------------------------------------------------------- needsPackage "SimplicialComplexes" newPackage("EdgeIdeals", Version => "1.0.1", Date => "August 22, 2010", Certification => { "journal name" => "The Journal of Software for Algebra and Geometry: Macaulay2", "journal URI" => "http://j-sag.org/", "article title" => "EdgeIdeals: a package for (hyper)graphs", "acceptance date" => "2009-06-27", "published article URI" => "http://j-sag.org/Volume1/jsag-1-2009.pdf", "published code URI" => "http://j-sag.org/Volume1/EdgeIdeals.m2", "repository code URI" => "svn://svn.macaulay2.com/Macaulay2/trunk/M2/Macaulay2/packages/EdgeIdeals.m2", "release at publication" => 9342, "version at publication" => "1.0.0", "volume number" => "1", "volume URI" => "http://j-sag.org/Volume1/" }, Authors => { {Name => "Chris Francisco", Email => "chris@math.okstate.edu", HomePage => "http://www.math.okstate.edu/~chris/" }, {Name => "Andrew Hoefel", Email => "handrew@mathstat.dal.ca", HomePage => "http://www.mathstat.dal.ca/~handrew/" }, {Name => "Adam Van Tuyl", Email => "avantuyl@lakeheadu.ca", HomePage => "http://flash.lakeheadu.ca/~avantuyl/" } }, Headline => "a package for edge ideals.", DebuggingMode => false ) needsPackage "GenericInitialIdeal" needsPackage "SimplicialComplexes" export { HyperGraph, hyperGraph, Graph, graph, adjacencyMatrix, allOddHoles, allEvenHoles, antiCycle, changeRing, chromaticNumber, cliqueComplex, cliqueNumber, coverIdeal, complementGraph, completeGraph, completeMultiPartite, connectedComponents, connectedGraphComponents, cycle, degreeVertex, deleteEdges, edgeIdeal, edges, getCliques, getEdge, getEdgeIndex, getGoodLeaf, getGoodLeafIndex, getMaxCliques, hasGoodLeaf, hasOddHole, hyperGraphToSimplicialComplex, incidenceMatrix, independenceComplex, independenceNumber, inducedGraph, inducedHyperGraph, isBipartite, isChordal, isCM, isConnected, isConnectedGraph, isEdge, isForest, isGoodLeaf, isGraph, isLeaf, isolatedVertices, isPerfect, isSCM, lineGraph, neighbors, numConnectedComponents, numConnectedGraphComponents, numTriangles, randomGraph, randomUniformHyperGraph, randomHyperGraph, simplicialComplexToHyperGraph, smallestCycleSize, spanningTree, vertexCoverNumber, vertexCovers, vertices, Gins, BranchLimit, TimeLimit, MaximalEdges, OriginalRing }; ---------------------------------------------------------------------------------------- -- -- TYPES -- ---------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------- -- HyperGraph ---------------------------------------------------------------------------------------- HyperGraph = new Type of HashTable; HyperGraph.synonym = "hypergraph"; hyperGraph = method(TypicalValue => HyperGraph); hyperGraph (PolynomialRing, List) := HyperGraph => (R, E) -> ( -- Output: HyperGraph over R with edges E -- Assert: R is a polynomial ring -- Assert: E is a List of Lists of variables of R or -- E is a List of square-free monomials in R if any(E, e -> class e =!= List) and any(E, e -> class class e =!= PolynomialRing) then ( print apply(E, e -> class e) ;error "Edges must be lists of variables or monomials."); V := gens R; --- check needed for square free if any(E, e-> class class e === PolynomialRing) then E = apply(E, support); E = apply(E, unique) / rsort; --- Enforces square-free if edges H := new HyperGraph from hashTable({"ring" => R, "vertices" => V, "edges" => E}); if any(H#"edges", e -> not instance(e, List)) then error "Edges must be lists."; if any(H#"edges", e -> not isSubset(e,H#"vertices")) then error "Edges must be subsets of the vertices."; if any(0..#(H#"edges") -1, I -> any(0..I-1, J-> isSubset(H#"edges"#I, H#"edges"#J) or isSubset(H#"edges"#J, H#"edges"#I)) ) then error "Edges satisfy a inclusion relation"; return H; ) hyperGraph (MonomialIdeal) := HyperGraph => (I) -> ( if not isSquareFree I then error "Ideals must be square-free."; hyperGraph(ring I, apply(flatten entries gens I, support)) ) hyperGraph (Ideal) := HyperGraph => (I) -> ( hyperGraph monomialIdeal I ) hyperGraph (List) := HyperGraph => (E) -> ( M := null; if all(E, e-> class e === List) then ( if E == {} or E == {{}} then error "Use alternate construction with PolynomialRing to input empty hyperGraph" else M = monomialIdeal apply(E, product); ); if all(E, e-> class class e === PolynomialRing) then M = monomialIdeal E; if M === null then error "Edge must be represented by a list or a monomial."; if #E =!= numgens M then error "Edges satisfy an inclusion relation."; hyperGraph M ) ---------------------------------------------------------------------------- -- Graph ---------------------------------------------------------------------------- Graph = new Type of HyperGraph; Graph.synonym = "graph"; graph = method(TypicalValue => Graph); graph (PolynomialRing, List) := Graph => (R, E) -> ( H := hyperGraph(R, E); if not isGraph(H) then error "Edges must be of size two."; new Graph from H ) graph (MonomialIdeal) := Graph => (I) -> ( H := hyperGraph(I); if not isGraph(H) then error "Ideal must have quadratic generators."; new Graph from H ) graph (Ideal) := Graph => (I) -> ( H := hyperGraph(I); if not isGraph(H) then error "Ideal must have quadratic generators."; new Graph from H ) graph List := Graph => E -> ( if E == {} then error "Use alternate construction with PolynomialRing to input empty graph"; H := hyperGraph(E); if not isGraph(H) then error "Edges must be of size two."; new Graph from H ) graph (HyperGraph) := Graph => (H) -> ( if not isGraph(H) then error "Edges must be of size two."; new Graph from H ) hyperGraph (Graph) := HyperGraph => (G) -> ( new HyperGraph from G ) ------------------------------------------------------------------- -- -- FUNCTIONS -- ------------------------------------------------------------------ -------------------------------------------------------------- -- Mathematical equality -- return true if two graphs are equal (defined over same ring, -- have same edge sets in some order). --------------------dges"; numEdges := #edges; count := 0; evenCycles := {}; while count < numEdges do ( newEdges := {{first(edges#count),newVar},{newVar,(edges#count)#1}}; tempEdges := apply(join(drop(edges,{count,count}),newEdges),i->apply(i,j->substitute(j,S))); tempGraph := graph(S,tempEdges); evenCycles = append(evenCycles,select(allOddHoles tempGraph,i->member(newVar,i))); count = count+1; ); use R; apply(unique apply(flatten evenCycles,i->select(i,j->(j != newVar))),k->apply(k,l->substitute(l,R))) ) -------------------------------------------------------------- -- allOddHoles -- returns a list of all the odd holes in a graph -------------------------------------------------------------- allOddHoles = method(); allOddHoles Graph := G -> ( coverI := coverIdeal G; apply(select(ass coverI^2,i->codim i > 3),j->flatten entries gens j) ) ------------------------------------------------------------------- -- antiCycle -- return the complement of a cycle. ------------------------------------------------------------------ antiCycle = method(TypicalValue=>Graph); antiCycle (Ring) := Graph =>(R) -> antiCycle(generators R) antiCycle (Ring, ZZ) := Graph =>(R, N) -> antiCycle(apply(N, i->R_i)) antiCycle (List) := Graph =>(L)-> ( if #L < 3 then error "Cannot construct anticycles of length less than three"; antiCycleEdgeSet := subsets(L,2) - set append(apply(#L-1, i-> {L#i,L#(i+1)}), {first L, last L}); graph(ring L#0,toList antiCycleEdgeSet) ) ------------------------------------------------------------ -- changeRing -- moves a HyperGraph into a new Ring ----------------------------------------------------------- changeRing = method(Options=>{MaximalEdges=>false}) changeRing (HyperGraph, PolynomialRing, List) := option -> (H, R, L) -> ( E := edges H; f := map(R, ring H, L); E = toList set apply(E, e-> set apply(e, v-> f v)); I := if option.MaximalEdges then ( select(toList(0..#E-1), i-> all(toList(0..#E-1), j-> j===i or not isSubset(E_i,E_j))) ) else ( select(toList(0..#E-1), i-> all(toList(0..#E-1), j-> j===i or not isSubset(E_j,E_i))) ) ; hyperGraph(R,apply(I, i->toList E_i)) ); --------------------------------------------------------------- -- chromaticNumber -- returns the chromatic number of a (hyper)graph -- NOTE: based upon work in progress by Francisco-Ha-Van Tuyl --------------------------------------------------------------- chromaticNumber = method(); chromaticNumber HyperGraph := H -> ( E := edges H; s := toList(apply(E,e->#e)); if ((class H === HyperGraph) and (member(1,s))) then error "A hypergraph with an edge of cardinality one does not have a chromatic number"; Chi := 2; -- assumes graph has at least one edge m := product H#"vertices"; j := coverIdeal H; while ((m^(Chi-1) % j^Chi) != 0) do ( Chi = Chi + 1; ); Chi ) --------------------------------------------------------------- -- cliqueComplex -- return the simplicial complex whose faces are the cliques of a graph --------------------------------------------------------------- cliqueComplex = method(); cliqueComplex Graph := G -> independenceComplex complementGraph G; ------------------------------------------------- -- cliqueNumber -- return the clique number of a graph ------------------------------------------------ cliqueNumber = method(); cliqueNumber Graph := G -> ( #(last getClomplementGraph HyperGraph := H -> ( hcedge := apply(H#"edges",e-> toList (set(H#"vertices") - set e)); -- create edge set of hypergraph hyperGraph(H#"ring",toList hcedge) ) ---------------------------------------------------------------------- -- completeGraph -- return graph of complete n-graph ---------------------------------------------------------------------- completeGraph = method(); completeGraph (Ring) := Graph =>(R) -> completeGraph(generators R) completeGraph (Ring, ZZ) := Graph =>(R, N) -> completeGraph(apply(N, i->R_i)) completeGraph (List) := Graph =>(L)-> ( if #L === 0 then error "Cannot construct complete graph on no vertices"; E := for i from 0 to #L -2 list for j from i+1 to #L-1 list L#i * L# j; graph(ring first L, flatten E) ) -------------------------------------------------------------------------- -- completeMultiPartite -- return the complete multi-partite graph -------------------------------------------------------------------------- completeMultiPartite = method(); completeMultiPartite (Ring, ZZ, ZZ) := Graph =>(R,N,M) -> completeMultiPartite(R, toList apply(N, i->M)) completeMultiPartite (Ring, List) := Graph =>(R, L) -> ( if all(L, l -> class l === ZZ) then ( if sum L > #gens(R) then error "Too few variables in ring to make complete multipartite graph"; N := 0; L = for i from 0 to #L-1 list ( E := toList apply(L#i, j -> R_(j+N)); N = N+L#i; E ); ); if all(L, l -> class l === List) then ( K := flatten for i from 0 to #L-2 list flatten for j from i+1 to #L-1 list flatten for x in L#i list for y in L#j list {x,y}; return graph(R, K); ) else error "completeMultipartite must be passed a list of partition sizes or a list of partitions."; ) ----------------------------------------------------------------------- -- connectedComponents -- returns all the connected components of a hypergraph ---------------------------------------------------------------------- connectedComponents = method(); connectedComponents HyperGraph := H -> ( V := select(H#"vertices", v-> any(H#"edges", e -> member(v,e))); while #V > 0 list ( C := {V#0}; i := 0; while i < #C do ( ingElement) := (H,V) -> ( use H#"ring"; N := index V; if N === null then error "Variable is not a vertex of the given HyperGraph"; number(H#"edges", E-> member(V,E)) ) ---------------------------------------------------------------------------------- -- deleteEdges -- remove edges from a (hyper)graph ---------------------------------------------------------------------------------- deleteEdges = method(); deleteEdges (HyperGraph,List) := (H,E) -> ( if all(E, e -> class class e === PolynomialRing) then E = apply(E, support); if (isSubset(set E,set H#"edges") =!= true) then error "Second argument must be a subset of the edges, entered as a list"; hyperGraph(ring H, toList(set(H#"edges")-set(E))) ) --deleteEdges (Graph,List) := (H,E) -> (graph deleteEdges (hyperGraph(H),E)) ---------------------------------------------------------------------- -- edgeIdeal -- return the edge ideal of a graph or hypergraph ---------------------------------------------------------------------- edgeIdeal = method(); edgeIdeal HyperGraph := H -> ( if H#"edges" == {} then return monomialIdeal(0_(H#"ring")); if H#"edges" == {{}} then return monomialIdeal(1_(H#"ring")); monomialIdeal apply(H#"edges",product)) ------------------------------------------------------------ -- edges -- returns edges of a (hyper)graph ------------------------------------------------------------ edges = method(); edges HyperGraph := H -> H#"edges"; ---------------------------------------------------------------- -- getCliques -- return all cliques of the graph ---------------------------------------------------------------- getCliques = method(); getCliques (Graph,ZZ) := (G,d) -> ( subs := apply(subsets(G#"vertices",d),i->subsets(i,2)); cliqueIdeals := apply(subs,i->ideal apply(i,j->product j)); edgeId := edgeIdeal G; apply(select(cliqueIdeals,i->isSubset(i,edgeId)),j->support j) ) getCliques Graph := G -> ( numVerts := #(G#"vertices"); cliques := {}; count := 2; while count <= numVerts do ( newCliques:=getCliques(G,count); if newCliques == {} then return flatten cliques; cliques = append(cliques,newCliques); count = count+1; ); flatten cliques ) ------------------------------------------------------------ -- getEdge -- returns a specific edge ------------------------------------------------------------ getEdge = method(); getEdge (HyperGraph, ZZ) := (H,N) -> H#"edges"#N; ------------------------------------------------------------ -- getEdgeIndex -- returns position of a given edge in a list of edges ------------------------------------------------------------ getEdgeIndex = method(); getEdgeIndex (HyperGraph, List) := (H,E) -> ( if class class E === PolynomialRing then E = support E; N := select(0..#(H#"edges")-1, N -> set H#"edges"#N === set E); if #N === 0 then return -1; first N ) getEdgeIndex (HyperGraph, RingElement) := (H,E) -> ( getEdgeIndex(H, support E) ) ----------------------------------------------------------- -- getGoodLeaf -- return a "Good Leaf" of a hypergraph ---------------------------------------------------------- getGoodLeaf = method(); getGoodLeaf HyperGraph := H -> ( H#"edges"#(getGoodLeafIndex H) ) ------------------------------------------------------------ -- getGoodLeafIndex -- return the index of a "Good Leaf" in a hypergraph ------------------------------------------------------------ getGoodLeafIndex = method(); getGoodLeafIndex HyperGraph := H -> ( GL := select(0..#(H#"edges")-1, N -> isGoodLeaf(H,N)); if #GL == 0 then return -1; first GL ); -------------------------------------------------------------------------- -- getMaxCliques -- return all cliques----------------------------------------------------------------------- -- hasGoodLeaf -- checks if a hypergraph has any "Good Leaves" ---------------------------------------------------------------------------- hasGoodLeaf = method(); hasGoodLeaf HyperGraph := H -> any(0..#(H#"edges")-1, N -> isGoodLeaf(H,N)) ------------------------------------------------------------------------------ -- hasOddHole -- checks if a graph has an odd hole (not triangle) ----------------------------------------------------------------------------- hasOddHole = method(); hasOddHole Graph := G -> ( coverI := coverIdeal G; any(ass coverI^2,i->codim i > 3) ) -------------------------------------------------- -- hyperGraphToSimplicialComplex -- make a simplicialComplex from a (hyper)graph --------------------------------------------------- hyperGraphToSimplicialComplex = method() hyperGraphToSimplicialComplex HyperGraph := H -> ( if H#"edges" == {} then return simplicialComplex monomialIdeal 1_(ring H); simplicialComplex flatten entries gens edgeIdeal H ) ----------------------------------------------------------------------------- -- incidenceMatrix -- return the incidence matrix of a graph ----------------------------------------------------------------------------- incidenceMatrix = method(); incidenceMatrix HyperGraph := H -> ( v:= H#"vertices"; e := H#"edges"; m := apply(#v,i-> apply(#e,j-> if member(v_i,e_j) then 1 else 0)); matrix m ) ------------------------------------------------------------------------------- -- independenceComplex -- returns the simplicial complex whose faces are the independent sets of a (hyper)graph -------------------------------------------------------------------------------- independenceComplex = method(); independenceComplex HyperGraph := H -> (simplicialComplex edgeIdeal H) ------------------------------------------------------------------ -- independenceNumber -- return the independence number, the size of the largest independent set of a vertices ------------------------------------------------------------------ independenceNumber = method(); independenceNumber Graph:= G -> ( dim edgeIdeal G ) -------------------------------------------------------------------------------- -- inducedGraph -- given a set of vertices, return induced graph on those vertices -------------------------------------------------------------------------------- --if OriginalRing is true, then the graph stays in the larger ring. --by default, the ring of the induced graph is the smaller ring. --this avoids having lots of isolated vertices in the resulting hypergraph. inducedGraph = method(Options=>{OriginalRing=>false}); inducedGraph (Graph,List) := opts -> (H,S) -> ( graph inducedHyperGraph(H,S,OriginalRing=>opts#OriginalRing) ) -------------------------------------------------------------------------------- -- inducedHyperGraph -- given a set of vertices, return induced hypergraph on those vertices -------------------------------------------------------------------------------- --if OriginalRing is true, then the hypergraph stays in the larger ring. --by icNumber G == 2); -- checks if chromatic number is 2 ------------------------------------------------------------- -- isChordal -- check if a graph is a chordal graph ------------------------------------------------------------- isChordal = method(); -- based upon Froberg's characterization of chordal graphs isChordal Graph := G -> ( I := edgeIdeal complementGraph G; graphR := G#"ring"; if I == ideal(0_graphR) then return true; D := min flatten degrees I; B := coker gens I; R := regularity(B); if D-1 =!= R then return false; true ) ------------------------------------------------------------- -- isCM -- checks if a (hyper)graph is Cohen-Macaulay ------------------------------------------------------------ isCM = method(); isCM HyperGraph := H -> ( I := edgeIdeal H; codim I == pdim coker gens I ) -- R := H#"ring"; -- M := R^1 / edgeIdeal H; -- Q := R^1 / ideal gens R; -- D := dim M; -- Ext^D(Q,M) !=0 and Ext^(D-1)(Q,M) == 0 -- ) ------------------------------------------------------------ -- isConnected -- checks if a graph is connected -- (the graph is connected <=> A, the adjacency the matrix, -- and I, the identity matrix of size n, has the -- property that (A+I)^{n-1} has no zero entries) ------------------------------------------------------------ isConnected = method(); isConnected HyperGraph := H -> numConnectedComponents H == 1 ------------------------------------------------------------ -- isConnectedGraph -- checks if a graph is connected -- isolated vertices are considered separate components ------------------------------------------------------------ isConnectedGraph = method(); isConnectedGraph HyperGraph := H -> numConnectedGraphComponents H == 1 ------------------------------------------------------------ -- isEdge -- checks if a set is an edge of a (hyper)graph ------------------------------------------------------------ isEdge = method(); isEdge (HyperGraph, List) := (H,E) -> ( if class class E === PolynomialRing then E = support E; any(H#"edges", G->set G === set E) ) isEdge (HyperGraph, RingElement) := (H,E) -> ( isEdge(H, support E) ) ------------------------------------------------------------- -- isForest -- checks if a (hyper)graph is a tree ------------------------------------------------------------ isForest = method(); isForest Graph := G -> (smallestCycleSize G == infinity); isForest HyperGraph := H -> ( E := toList(0..#(H#"edges") -1); while #E =!= 0 do ( L := select(E, i-> isGoodLeaf(H,i)); if #L === 0 then return false; H = hyperGraph(H#"ring", drop(H#"edges", {first L, first L})); E = toList(0..#(H#"edges") -1); ); true ) ------------------------------------------------------------- -- isGoodLeaf -- checks if the n-th edge of a hypergraph is a "Good Leaf" ---------------------------------------------------------- isGoodLeaf = method(); isGoodLeaf (HyperGraph, ZZ) := (H,N) -> ( intersectEdges := (A,B) -> set H#"edges"#A * set H#"edges"#B; overlaps := apply(select(0..#(H#"edges")-1, M -> M =!= N), M -> intersectEdges(M,N)); overlaps = sort toList overlaps; --Check if the overlaps are totally ordered all(1..(#overlaps -1), I -> overlaps#(I-1) <= overlaps#I) ); ------------------------------------------------------------ -- isGraph -- checks if a hypergraph is a graph ------------------------------------------------------------ isGraph = method(); isGraph HyperGraph := Boolean => (H) -> ( H#"edges" == {} or all(H#"edges", e-> #e === 2 ) ) -------------------------------------------------------------- -- isLeaf -- checks if the n-th edge of the (hyper)graph is a leaf -------------------------------------------------------------- isLeaf = method(); isLeaf (HyperGraph, ZZ) := (H,N) -> ( intersectEdges := (A,B) -> set H#"edges"#A * set H#"edges"#B; overlaps := apply(select(0..(#(H#"edges")-1), M -> M =!= N), M -> intersectEdges(M,N)); overlapUnion := sum toList overlaps; any(overlaps, branch -> isSubset(overlapUnion,branch)) ) isLeaf (Graph, ZZ) := (G,N) -> ( any(G#"edges"#N, V -> degreeVertex(G,V) === 1) ---Note N refers to an edge index ) isLeaf (HyperGraph, RingElement) := (H,V) -> ( E := select(0..#(H#"edges")-1, I -> member(V, H#"edges"#I)); #E == 1 and isLeaf(H, E#0) ) -------------------------------------------------------------- -- isolatedVertices -- returns vertices contained in no edges -------------------------------------------------------------- isolatedVertices = method(); isolatedVertices (HyperGraph) := (H) -> ( edgeUnion := sum apply(H#"edges", set); if #(H#"edges")==0 then return H#"vertices" else select(H#"vertices", v -> not member(v, edgeUnion)) ) ------------------------------------------------------------ -- isPerfect -- checks if a graph is a perfect graph ------------------------------------------------------------ isPerfect = method(); isPerfect Graph := G -> ( if hasOddHole G then return false; if hasOddHole complementGraph G then return false; true ) ------------------------------------------------------------ -- isSCM -- checks if (hyper)graph is Sequentially Cohen-Macaulay ------------------------------------------------------------- --uses GenericInitialIdeals package for the gin --if the user selects the Gins option isSCM= method(Options=>{Gins=>false}); isSCM HyperGraph := opts -> H -> ( J := dual edgeIdeal H; if opts#Gins then ( g := gin J; return (#(flatten entries mingens g) == #(flatten entries mingens J)); ); degs := sort unique apply(flatten entries gens J,i->first degree i); numDegs := #degs; count := 0; while count < numDegs do ( Jdeg:=monomialIdeal super basis(degs#count,J); if regularity Jdeg != degs#count then return false; count = count+1; ); true ) ------------------------------------------------------------------ -- lineGraph -- return the graph with E(G) as its vertices where two -- vertices are adjacent when their associated edges are adjacent in G. ------------------------------------------------------------------ lineGraph = method(); lineGraph HyperGraph := H -> ( x := local x; R := QQ[x_0..x_(#edges(H)-1)]; E := apply(H#"edges", set); L := select(subsets(numgens R, 2), e -> #(E#(e#0) * E#(e#1)) > 0); graph(R, apply(L,e->apply(e, i-> x_i))) ) ----------------------------------------------------------- -- neighbors -- returns all the neighbors of a vertex or a set ----------------------------------------------------------- neighbors = method(); neighbors (HyperGraph, ZZ) := (H, N) -> neighbors(H, H#"ring"_N) neighbors (HyperGraph, RingElement) := (H,V) -> ( unique select(flatten select(H#"edges", E-> member(V,E)), U-> U =!= V) ) neighbors (HyperGraph, List) := (H,L) -> ( if any(L, N-> class N === ZZ) then L = apply(L, N-> H#"ring"_N); unique select(flatten apply(L, V-> neighbors(H,V)), U -> not member(U, L)) ) ------------------------------------------------------------ -- numConnectedComponents -- the number of connected components of a (hyper)Graph ------------------------------------------------------------ numConnectedComponents = method(); numConnectedComponents HyperGraph:= H -> ( if (H#"edges" == {}) or (H#"edges"== {{}}) then return 0; (rank HH_0 hyperGraphToSimplicialComplex H)+1 ) ------------------------------------------------------------ -- numConnectedGraphComponents -- the number of connected components of a (hyper)Graph -- this includes isolated vertices ------------------------------------------------------------ numConnectedGraphComponents = method(); numConnectedGraphComponents HyperGraph := H -> ( if (H#"edges" == {}) or (H#"edges"== {{}}) then ( return #isolatedVertices(H); ); numConnectedComponents(H) + #isolatedVertices(H) ) ----------------------------------------------------------- -- numTriangles -- returns the number of triangles in a graph ----------------------------------------------------------- numTriangles = method(); numTriangles Graph := G -> ( number(ass (coverIdeal G)^2,i->codim i==3) ) ----------------------------------------------------------- -- randomGraph -- returns a graph with a given vertex set and randomly chosen -- edges with the user determining the number of edges ----------------------------------------------------------- randomGraph = method(); randomGraph (PolynomialRing,ZZ) := (R,num) -> ( graph randomUniformHyperGraph(R,2,num) ) ----------------------------------------------------------- -- rhe eg} and {\tt h} are equal Description Text This function determines if two HyperGraphs are mathematically equal. Two HyperGraphs are equal if they are defined over the same ring, have the same variables, and have the same set of edges. In particular, the order of the edges and the order of variables within each edge do not matter. Example R = QQ[a..f]; g = hyperGraph {{a,b,c},{b,c,d},{d,e,f}}; h = hyperGraph {{b,c,d},{a,b,c},{f,e,d}}; k = hyperGraph {{a,b},{b,c,d},{d,e,f}}; g == h g == k /// ------------------------------------------------------------ -- DOCUMENTATION adjacencyMatrix ------------------------------------------------------------ doc /// Key adjacencyMatrix (adjacencyMatrix, Graph) Headline returns the adjacency Matrix of a graph Usage M = adjacencyMatrix G Inputs G:Graph Outputs M:Matrix the adjacency matrix of the graph Description Text This function returns the adjacency matrix of the given graph {\tt G}. The (i,j)^{th} position of the matrix is 1 if there is an edge between the i^{th} vertex and j^{th} vertex, and 0 otherwise. The rows and columns are indexed by the variables of the ring and use the ordering of the variables for determining the order of the rows and columns. Example S = QQ[a..f]; G = graph {a*b,a*c,b*c,c*d,d*e,e*f,f*a,a*d} t = adjacencyMatrix G T = QQ[f,e,d,c,b,a]; G = graph {a*b,a*c,b*c,c*d,d*e,e*f,f*a,a*d} t = adjacencyMatrix G -- although the same graph, matrix is different since variables have different ordering SeeAlso incidenceMatrix vertices /// ------------------------------------------------------------ -- DOCUMENTATION allEvenHoles ------------------------------------------------------------ doc /// Key allEvenHoles (allEvenHoles, Graph) Headline returns all even holes in a graph Usage L = allEvenHoles G Inputs G:Graph Outputs L:List returns all even holes contained in {\tt G}. Description Text The method is based on work of Francisco-Ha-Van Tuyl, looking at the associated primes of the square of the Alexander dual of the edge ideal. An even hole is an even induced cycle (necessarily of length at least four). The algorithm for allEvenHoles uses an observation of Mermin. Fix an edge, and split this edge into two different edges, introducing a new vertex. Find all the odd holes in that graph. Do that for each edge in the graph, one at a time, and pick out all the odd holes containing the additional vertex. Dropping this vertex from each of the odd holes gives all the even holes in the original graph. See C.A. Francisco, H.T. Ha, A. Van Tuyl, "Algebraic methods for detecting odd holes in a graph." (2008) Preprint. {\tt arXiv:0806.1159v1}. Example R = QQ[a..f]; G = cycle(R,6); allEvenHoles G H = graph(monomialIdeal(a*b,b*c,c*d,d*e,e*f,a*f,a*d)) --6-cycle with a chord allEvenHoles H --two 4-cycles SeeAlso allOddHoles hasOddHole /// ------------------------------------------------------------ -- DOCUMENTATION allOddHoles ------------------------------------------------------------ doc /// Key allOddHoles (allOddHoles, Graph) Headline returns all odd holes in a graph Usage L = allOddHoles G Inputs G:Graph Outputs L:List returns all odd holes contained in {\tt G}. Description Text An odd hole is an odd induced cycle of length at least 5. The method is based on work of Francisco-Ha-Van Tuyl, looking at the associated primes of the square of the Alexander dual of the edge ideal. See C.A. Francisco, H.T. Ha, A. Van Tuyl, "Algebraic methods for detecting odd holes in a graph." (2008) Preprint. {\tt arXiv:0806.1159v1}. Example R = QQ[x_1..x_6]; G = graph({x_1*x_2,x_2*x_3,x_3*x_4,x_4*x_5,x_1*x_5,x_1*x_6,x_5*x_6}) --5-cycle and a triangle allOddHoles G --only the 5-cycle should appear H = graph({x_1*x_2,x_2*x_3,x_3*x_4,x_4*x_5,x_1*x_5,x_1*x_6,x_5*x_6,x_1*x_4}) --no odd holes allOddHoles H SeeAlso allEvenHoles hasOddHole /// ------------------------------------------------------------ -- DOCUMENTATION antiCycle ------------------------------------------------------------ doc /// Key antiCycle (antiCycle, Ring) (antiCycle, Rrsus his function produces a simplicial complex from a (hyper)graph. The facets of the simplicial complex are given by the edge set of the (hyper)graph. This function is the inverse of @TO simplicialComplexToHyperGraph @ and enables users to make use of functions in the package @TO "SimplicialComplexes::SimplicialComplexes" @. Example R = QQ[x_1..x_6]; G = graph({x_1*x_2,x_2*x_3,x_3*x_4,x_4*x_5,x_1*x_5,x_1*x_6,x_5*x_6}) --5-cycle and a triangle DeltaG = hyperGraphToSimplicialComplex G hyperGraphDeltaG = simplicialComplexToHyperGraph DeltaG GPrime = graph(hyperGraphDeltaG) G === GPrime SeeAlso simplicialComplexToHyperGraph "Constructor Overview" /// ------------------------------------------------------------ -- DOCUMENTATION incidenceMatrix ------------------------------------------------------------ doc /// Key incidenceMatrix (incidenceMatrix, HyperGraph) Headline returns the incidence matrix of a hypergraph Usage M = incidenceMatrix H Inputs H:HyperGraph Outputs M:Matrix the incidence matrix of the hypergraph Description Text This function returns the incidence matrix of the given hypergraph {\tt H}. The rows of the matrix are indexed by the variables of the hypergraph, and the columns are indexed by the edges. The (i,j)^{th} entry in the matrix is 1 if vertex i is contained in edge j, and is 0 otherwise. The order of the rows and columns are determined by the internal order of the vertices and edges. See @TO edges@ and @TO vertices@. Example S = QQ[a..f]; g = hyperGraph {a*b*c*d,c*e,e*f} incidenceMatrix g T = QQ[f,e,d,c,b,a]; h = hyperGraph {a*b*c*d,c*e,e*f} incidenceMatrix h -- although the same graph, matrix is different since variables have different ordering SeeAlso adjacencyMatrix edges vertices /// ------------------------------------------------------------ -- DOCUMENTATION independenceComplex ------------------------------------------------------------ doc /// Key independenceComplex (independenceComplex, HyperGraph) Headline returns the independence complex of a (hyper)graph Usage D = independenceComplex H Inputs H:HyperGraph Outputs D:SimplicialComplex the independence complex associated to the (hyper)graph Description Text This function associates to a (hyper)graph a simplicial complex whose faces correspond to the independent sets of the (hyper)graph. See, for example, the paper of A. Van Tuyl and R. Villarreal "Shellable graphs and sequentially Cohen-Macaulay bipartite graphs," Journal of Combinatorial Theory, Series A 115 (2008) 799-814. Example S = QQ[a..e]; g = graph {a*b,b*c,c*d,d*e,e*a} -- the 5-cycle independenceComplex g h = hyperGraph {a*b*c,b*c*d,d*e} independenceComplex h Text Equivalently, the independence complex is the simplicial complex associated to the edge ideal of the (hyper)graph {\tt H} via the Stanley-Reisner correspondence. Example S = QQ[a..e]; g = graph {a*b,b*c,a*c,d*e,a*e} Delta1 = independenceComplex g Delta2 = simplicialComplex edgeIdeal g Delta1 == Delta2 SeeAlso independenceNumber /// ------------------------------------------------------------ -- DOCUMENTATION independenceNumber ------------------------------------------------------------ doc /// Key independenceNumber (independenceNumber, Graph) Headline determines the independence number of a graph Usage d = independenceNumber G Inputs G:Graph Outputs d:ZZ the independence number of {\tt G} Description Text This function returns the maximum number of independent vertices in a graph. This number can be found by computing the dimension of the simplicial complex whose faces are the independent sets (see @TO independenceComplex @) and adding 1 to this number. Example R = QQ[a..e]; c4 = graph {a*b,b*c,c*d,d*a} -- 4-cycle plus an isolated vertex!!!! c5 = graph {a*b,b*c,c*d,d*e,e*a} --ly if the sizes of the edges fail to pass the LYM-inequality: $1/(n choose D_1) + 1/(n choose D_2) + ... + 1/(n choose D_m) \leq 1$ where $n$ is the number of variables in {\tt R} and $m$ is the length of {\tt D}. Note that even if {\tt D} passes this inequality, it is not necessarily true that there is some hypergraph with edge sizes given by {\tt D}. See D. Lubell's "A short proof of Sperner's lemma," J. Combin. Theory, 1:299 (1966). SeeAlso randomGraph randomUniformHyperGraph BranchLimit TimeLimit "Constructor Overview" /// ------------------------------------------------------------ -- DOCUMENTATION randomUniformHyperGraph ------------------------------------------------------------ doc /// Key randomUniformHyperGraph (randomUniformHyperGraph,PolynomialRing,ZZ,ZZ) Headline returns a random uniform hypergraph Usage H = randomUniformHyperGraph(R,c,d) Inputs R:PolynomialRing which gives the vertex set of {\tt H} c:ZZ the cardinality of the edge sets d:ZZ the number of edges in {\tt H} Outputs H:HyperGraph a hypergraph with {\tt d} edges of cardinality {\tt c} on vertex set determined by {\tt R} Description Text This function allows one to create a uniform hypergraph on an underlying vertex set with a given number of randomly chosen edges of given cardinality. Example R = QQ[x_1..x_9]; randomUniformHyperGraph(R,3,4) randomUniformHyperGraph(R,4,2) SeeAlso randomGraph randomHyperGraph "Constructor Overview" /// ------------------------------------------------------------ -- DOCUMENTATION ring ------------------------------------------------------------ doc /// Key (ring, HyperGraph) Headline gives the ring of a (hyper)graph Usage R = ring H Inputs H:HyperGraph Outputs R:Ring Description Text Every (hyper)graph is defined over some polynomial ring. This method returns the ring of a hypergraph. Example S = QQ[a..d]; g = cycle S; h = inducedHyperGraph(g,{a,b,c}); describe ring g describe ring h SeeAlso edges vertices /// --------------------------------------------------------- -- DOCUMENTATION simplicialComplexToHyperGraph ---------------------------------------------------------- doc /// Key simplicialComplexToHyperGraph (simplicialComplexToHyperGraph, SimplicialComplex) Headline makes a (hyper)graph from a simplicial complex Usage H = simplicialComplexToHyperGraph(D) Inputs D:SimplicialComplex the input Outputs H:HyperGraph whose edges are the facets of D Description Text This function makes a @TO HyperGraph@ from a @TO SimplicialComplex@. The edges of the HyperGraph are given by the facets of the SimplicialComplex. This is the inverse of the function @TO hyperGraphToSimplicialComplex @. Example S = QQ[a..f]; Delta = simplicialComplex {a*b*c,b*c*d,c*d*e,d*e*f} H = simplicialComplexToHyperGraph Delta SeeAlso hyperGraphToSimplicialComplex "Constructor Overview" /// --------------------------------------------------------- -- DOCUMENTATION smallestCycleSize ---------------------------------------------------------- doc /// Key smallestCycleSize (smallestCycleSize, Graph) Headline returns the size of the smallest induced cycle of a graph Usage s = smallestCycleSize(G) Inputs G:Graph the input Outputs s:ZZ the size of the smallest induced cycle Description Text This function returns the size of the smallest induced cycle of a graph. It is based upon Theorem 2.1 in the paper "Restricting linear syzygies: algebra and geometry" by Eisenbud, Green, Hulek, and Popsecu. This theorem states that if G is graph, then the edge ideal of the complement of G satisfies property N_{2,p}, that is, the resolution of I(G^c) is linear up to the p-th step, if and only if the smallest induced cycle of G has length p+3. The algorithm looks at the resolution of the edge ideal of the complement to determine the size of the smallest cycle. Example T = QQ[x_1..x_9]; g = graph {x_1*x_2,x_2*x_3,x_3*x_4,x_4*x_5,x_5*x_6,x_6*x_7,x_7*x_8,x_8*x_9,x_9*x_1} -- a 9-cycle smallestCycleSize g h = graph {x_1*x_2,x_2*x_3,x_3*x_4,x_4*x_5,x_5*x_6,x_6*x_7,x_7*x_8,x_8*x_9} -- a tree (no cycles)