User gwyn whieldon - MathOverflow

Software Reference Request: Three Dimensional Staircase Visualizers for Monomial Ideals

2012-12-14T00:51:04Z

Is anyone familiar with software that already exists to visualize monomial ideals in three variables as their staircase diagrams, in the sense of Combinatorial Commutative Algebra? It looks like their graphics were done using TikZ, but after a reasonable search, I wasn't able to find any pre-written packages or software that would automatically produce a picture of the staircase diagram of a monomial ideal.

It was easy enough to write a few lines of code in Macaulay2 to produce the TikZ code for the two-dimensional case, but I wasn't looking forward to writing code to do the same thing in the three variable case if this already existed somewhere. If there was code to draw these things using ideals encoded in Macaulay2, Singular, or Sage format, I would love that -- but if there's any pre-done visualizer for three variable monomial ideals, I would happily compromise on format.

Alternately, if someone has software (or knows a good reference to software) which produces visualizations of the Buchberger graph for one of these monomial ideals, I'd be willing to settle for that too.

Answer by Gwyn Whieldon for Number of spanning subgraphs of $K_n$ with given number of edges and connected components

2012-06-07T19:44:59Z

It seems like, even if you are only interested in that second answer, you're going to running up against the problem of computing the number of connected graphs on $a_i$ vertices. There might be a better way to count them that this, but here's one possible formula:

Let $P_c(n)$ be the set of partitions of $n$ with $c$ parts. For a partition $P=a_1+a_2+\cdots+a_c$, define the following numbers. Let $m_r(P)$ be the number of parts of $P$ of size $r$, i.e. $$m_r(P)=\#\{a_i : a_i=r\}.$$ Let $\omega(P)=\prod_{r=1}^{n}\bigl(m_r(P)!\bigr)$. Finally, let ${\mathcal C}(a_i)$ be the number of connected graphs on $a_i$ vertices.

One formula for the number of graphs on $n$ vertices with $c$ connected components then is $$\sum_{P\in P_c(n), P=a_1+a_2+\cdots a_c} \binom{n}{a_1,a_2,...,a_c}\frac{1}{\omega(P)}\cdot\prod_{i=1}^c {\mathcal C}(a_i).$$ The multichoose coefficient $\binom{n}{a_1,a_2,...,a_c}$ comes from the number of partitions of the vertices into $c$ groups, with $\omega(P)$ correcting for the overcount factor for multiple groups of vertices of the same size. The product comes from, for a fixed partition of vertices into pieces of size $a_i$, how many connected graphs are possible on each piece.

I don't believe there are explicit formulas for these $C(a_i)$, and I'm not sure that there's a way to generalize this to answer your original question (outside of in a painful fashion summing across ways divvying up the $e$ edges across these $c$ components.)

While this doesn't say that your question is as hard as computing the Tutte polynomial itself, it makes me suspect that there isn't a closed formula. I looked for a bit as well at Stirling numbers of the second kind (which counted the number of set partitions of the vertices into $c$ pieces), but didn't see a nice way to pull those apart to count the number of connected graphs possible given a set partition. That might give you a different formula though with an approach like that.

Answer by Gwyn Whieldon for Visualizing large posets

2011-11-30T20:33:56Z

David Cook, Sonja Mapes and I have a package for Macaulay 2 which draws pictures of posets, either with or without node labels. It will produce the TikZ code to include these in papers as well.

How large though is "very large"? While there are a number of built-in enumerators in our package (lcm lattices, hyperplane arrangement lattices, noncrossing partition lattices, etc.) which can produce fairly large posets quickly, the only limitation might be how you're storing or inputting these posets.

Answer by Gwyn Whieldon for What to do when your research runs into a computationally challenging problem?

2011-07-30T22:53:41Z

Isn't this particular case easier to prove using the topology of the independence complexes of your $K_{n,m}$ and $K_{s,t}$?

$Ind(K_{n,m})$ is the disjoint union of an (n-1)-simplex and an (m-1)-simplex, and $Ind(K_{s,t})$ is the disjoint union of a (s-1)-simplex and a (t-1)-simplex. So the Stanley-Reisner complex of the disjoint union of those two graphs would be $\Delta=Ind(K_{n,m})\coprod Ind(K_{s,t})$ is the join of those two complexes, which is connected ($\dim\widetilde{H}_0(\Delta)$=0) and has $\dim\widetilde{H}_1(\Delta)=1$.

From Hochster's formula, this gives you a nonzero Betti number at homological stage n+m+s+t-2, so $pd(R/I)\geq n+m+s+t-2$. As this is the entire Stanley Reisner complex, and as the complex is connected, that's as high as the projective dimension could be.

This isn't quite the complex you wanted - but you'd just need to examine what happens to the join of the independence complexes of $K_{n,m}$ and $K_{s,t}$ after deleting the face ${v,w}$ corresponding to the edge you added between the graphs and all of the faces containing it. This complex still is connected and has $\dim \widetilde{H}_1(\Delta)=1$, so the projective dimension of both complexes is the same.

I guess a more general answer to this particular question though is - instead of computing the resolutions using edge ideals, you might consider using GAP to compute the homology of subcomplexes of your total complex of the appropriate size. These homology calculations combined with Hochster's formula are often better tools at proving projective dimension or regularity bounds than trying to resolve the ideals themselves.

Algebra Counterexample Request: Linear Quotients

2011-06-23T18:11:54Z

A result of Herzog, Hibi, and Zheng in "Monomial ideals whose powers have a linear resolution" states that:

Theorem: Let $I\subseteq\Bbbk[x_1,\ldots,x_n]$ be a monomial ideal generated in degree 2. The following conditions are equivalent:

I has a linear resolution.
I has linear quotients.
Each power of I has a linear resolution.

This, when combined with (a slightly extended version of) Froberg's characterization of degree 2 (squarefree) ideals with a linear resolution, gives a complete description of all degree 2 (monomial) ideals with linear quotients.

However, this still leaves open a characterization of monomial ideals generated in higher degree with linear resolutions/quotients/linear resolutions of their powers. Sturmfels [in "Four Counterexamples in Combinatorial Algebraic Geometry"] and Conca [in "Regularity jumps for powers of ideals"] have a number of examples of ideals $I$ with linear quotients and linear quotients of their powers $I, I^2,\ldots,I^{k-1}$, which fail to have a linear resolution for $I^k$.

The counterexample request then is this: Are there any (monomial) homogeneous ideals which have characteristic independent linear resolutions but no linear quotients under any order of the generators? The theorem above implies that such an example would have to be generated (at least partially) in degree 3 or higher.

Edit: As Professor Conca pointed out, triangulations of the projective plane provide such an example. I was hoping to find a characteristic independent counterexample, but forgot to include this in the description. The request was largely because my research partner A. Hoefel and I were searching for such characteristic independent examples to test a conjecture - but were unable to locate any in the literature (or on a few targeted searches with M2 and GAP.)

Linking to Code in a Paper

2011-05-13T19:00:50Z

I'm planning on including in my thesis (and the papers that I'd like to publish out of it) links to Macaulay 2 packages and code which verify a few results and implement an new algorithm.

The complication that's arising is that I'll be leaving graduate school shortly - and my mathematics webpage through the department isn't likely to outlast my stay as a grad student by very long.

This seems like it would be a fairly common problem, but I've been having trouble finding a way of permanently linking to code in a way that will survive changing departments. I looked into link shortening services (tinyurl, bit.ly, etc.) and data hosting, but haven't found anything that would either allow a change of endpoint of the link (when I move pages) or allowed free and easy access to the files (and wouldn't delete the files containing the code if there was inactivity for over a month.)

Have any of you run into this problem before and found an effective solution? I'd appreciate any suggestions!

Online Library of Unlabeled Connected Graphs on n Vertices

2010-11-17T18:42:21Z

Does anyone know of the link to an online library of of unlabeled, connected graphs on n vertices? I remember looking at such an archive a few years ago while at a Macaulay 2 workshop, but I've been unable to find it (or any other one) since then.

The page I remember seeing only had enumerated unlabeled graphs up to n=11,12, or 13 vertices, and the graph I'm looking for data on is much larger, so links to repositories of larger (special) graphs.

The most specific part of this request: The graph I'm looking to find a list of edges for is the 1-skeleton of the 600-cell, if anyone happens to just have that information on-hand (or readily available.)

Answer by Gwyn Whieldon for "incidental" intersections of a complete graph in the plane

2010-10-22T01:22:09Z

This problem (although phrased slightly differently) is #1.3.5 in Loren C. Larson's "Problem Solving Through Problems."

The rephrase of this is, "On a circle, n points are selected and the chords joining them in pairs are drawn. Assuming no three of the chords are concurrent (except at the endpoints), how many points of intersection are there?"

This is $\binom{n}{4}$, as any four of our points on the circle determine a (unique) intersection point, and any intersection point determines the boundary chords.

[This might've been better as a comment on Gerry's answer, but there's a whole family of similar problems to the question asker's in that chapter of the book (which are also excellent problems to give to a math club.)]

Answer by Gwyn Whieldon for Number of edges in low complexity graphs

2010-10-15T01:00:28Z

Are the minimally 3-connected graphs (edge removal pushes you into a 2-connected graph) the same as the class of 3-connected graphs with the minimal number of spanning trees? There is a nice classification of the minimal 3-connected graphs (or maximal not-3-connected graphs, I forget which direction he does it in) in Jonsson's book "Simplicial Complexes of Graphs".

I think there's also a classification of minimal 3-connected graphs inside a paper by David Fisher, Kathryn Fraughnaugh, and Larry Langley which could help ["3-connected graphs of minimal size".] At the very least, they note that all 3-connected graphs on n vertices have at least 3/2(n-2) edges, and produce graphs achieving this bound. All of your graphs with the minimal number of spanning trees must be one of these minimal 3-connected graphs (as if your hypothetical "minimal spanning tree" graph wasn't also a minimal 3-connected graph, removing edges to a minimal 3-connected graph would reduce the number of spanning trees.)

Computing Bruhat Order Covering Relations

2010-05-13T08:06:33Z

To put this in context: I am in the process of developing a package for Macaulay 2 (a commutative algebra software,) called "Permutations", which will add permutations as a type of combinatorial object that M2 will handle, hopefully integrating nicely with the (still in development) Posets package, the (still in development) Graphs package, and various current M2 functions.

One of the first things that I'd wanted to put in was functions which compute the poset of the Bruhat order on $S_n$ and compute when one permutation covers another in the Bruhat order. This was all coded and "working" - but has been producing a poset which is decidedly NOT the desired poset (among other things, the graph of the Hasse diagram isn't regular.) I'd like to ask whether the (probably somewhat naive) algorithm I was using to check covering relations seems reasonable (so the problem is just in the coding of it, not in the theory behind it) or not.

To see if $P\leq R$ in the Bruhat order:

Given a pair of permutations P and R, compute their lengths (the number of simple transpositions in their decomposition, or [as implemented right now] the sum of entries in their inversion vectors.) If length(P)=length(R)+1, then we compute $(P^{-1})*R$.

If R covers P in the Bruhat order, then length$((P^{-1})*R)=1.$

Am I missing some subtlety of the Bruhat order? I thought one permutation covered enough exactly when they differed by a single, simple transposition. This seemed to capture that - but is giving me an incorrect poset.

Coding error or theory error? I'd love to hear it.

Enumeration of Regular Graphs

2010-04-21T18:22:18Z

Fix numbers n,k. Is there a closed formula known for the number of k-regular graphs consisting of n edges? I have a method of enumerating k-regular graphs on n edges, and would like to have a number to compare the algorithm against.

Simplicial Representations of (Hyper)Graph Complexes

2010-04-01T19:38:55Z

For graph complexes, which are families of graph [on a fixed number of vertices n] closed under the deletion of edges, there is a natural simplicial complex capturing that information. Specifically, this family forms a subcomplex of the simplex on $\binom{n}{2}$ vertices, with each vertex corresponding to an edge and each face in the simplex corresponding to a particular graph [where the dimension of the face is precisely the number of edges in the graph minus 1.] The family being closed under deletion of edges translates nicely into the family (a set of faces) truly being a subcomplex. As a result, each monotone graph property corresponds to a tangible, often combinatorially interesting simplicial complex.

[For an excellent survey of results on graph complexes, see Simplicial Complexes of Graphs, by Bjorner's student, Jakob Jonsson.]

For pure dimensional hypergraphs, a similar subcomplex can be constructed. A (d-1)-dimensional pure hypergraph family will sit as a subcomplex inside a simplex of dimension $\left(\binom{n}{d}-1\right)$, now with each vertex in the simplex corresponding to a (d-1)-dimensional face - so again, any monotone (pure) hypergraph property can be examined via topology of these complexes. Unfortunately, many properties that are monotone for graphs fail to be monotone for hypergraphs (not-connectivity in codimension 1 for pure hypergraphs in dimension 2 or higher immediately springs to mind, among others.)

Hypergraphs in general, however, need not be pure, and several interesting classes of them most certainly are not. A hypergraph complex is just any family of hypergraphs closed under the deletion of edges.

Is there any standard way of simplicially representing hypergraph complexes which are not pure? There is a somewhat poor way of doing it, it seems, by considering the simplex on $2^n$ vertices and allowing each face to correspond to a hypergraph which is not necessarily a clutter (i.e. no edges in the hypergraph are properly contained inside other edges.) This is unsatisfying to put it mildly, however, and I was hoping there was an alternate way of considering hypergraph complexes as a topological space. Any ideas or literature references?

Edit: Although I'm interested in a better geometric representation of hypergraph complexes for its own sake, the first main application would be for either "matchings" (or, alternately, noncrossing partitions) on hypergraphs. A matching on a graph is just a set of edges which are pairwise disjoint. The matching complex (of a graph G) sits as a subcomplex inside the complex of all graphs above, and consists of all such sets of edges. The general matching complex on n vertices is a special case of this, with $G=K_n$, the complete graph.

For a hypergraph G, a matching can be defined equivalently - a subset of edges (now possibly with more than 2 vertices per edge) which are pairwise disjoint. The complete hypergraph (which is NOT a clutter, as its edges are all subsets) has a matching complex whose maximal faces correspond to all partitions of $[n]={1,2,...,n}$. This isn't precisely a complex of the form suggested below (one closed under the removal of a face, then the addition of any set of subfaces.) However, it is closed under the removal of a face and the addition of any disjoint set of subfaces.

Answer by Gwyn Whieldon for Triangulations coming from a poset. Or: What conditions are necessary and sufficient for a finite simplicial complex to be the order complex of a poset?

2010-04-02T02:09:34Z

To rephrase your question, what conditions are necessary and sufficient for a simplicial complex to be an order complex?

There are also a few easy necessary conditions. For one, any simplicial complex is the Stanley-Reisner complex of a square-free monomial ideal (label each vertex with a variable, and the minimal non-faces in the simplicial complex are exactly the monomial generators of the ideal.) For all order complexes, their Stanley-Reisner ideal is an edge ideal (i.e. a square free monomial ideal generated in degree 2, called an "edge ideal" because it can be thought of as corresponding to a graph G with an edge for each generator.) This is immediate, because a minimal "non-face" in the order complex is a pair of incomparable elements, so all generators must be of degree 2. This does quickly cut down on the types of simplicial complexes to consider.

Unfortunately, having a 2-generated SR-ideal is also not sufficient. There are numerous subgraphs of a graph which will prevent the Stanley-Reisner complex of its edge ideal from being an order complex. For example, if the graph has an induced cycle of length longer than 7, the complex can't arise as an order complex.

I was working a few months ago on trying to classify the structures in graphs which would prohibit their edge ideals from having SR-complexes which were order complexes, but found the other forbidden structures weren't very easy to characterize. I'd love to see some more answers to this question as well!

Comment by Gwyn Whieldon

2012-11-28T13:37:00Z

You're right, apologies.

Comment by Gwyn Whieldon

2012-06-08T17:48:05Z

I know the Mayr Meyer ideals are the standard example of doubly-exponentially complex ideals - I think that might be an example of this as well (although your definition of "size" of a polynomial isn't quite the complexity measure those're using.)

Comment by Gwyn Whieldon

2011-11-30T20:39:17Z

The package is still in development, but if you're familiar with Macaulay 2 and interested, the Posets.m2 file can be downloaded at: dl.dropbox.com/u/4621422/Posets.m2 It does make use of the Graphs.m2 package as well, which was worked on extensively this summer at the IMA workshop: dl.dropbox.com/u/4621422/Graphs.m2

Comment by Gwyn Whieldon

2011-07-31T03:01:32Z

Macaulay 2 already has basic simplicial homology functions programmed in via the SimplicialComplexes package. I think even without access to the faster homology algorithms in GAP, you could have one thread computing the resolution (which would be faster if the projective dimension is low) and another checking through the right-most possible Betti numbers/homologies of subcomplexes. ($\beta_{n-1,n}(R/I)$, then $\beta_{n-2,n-1}(R/I)$ and $\beta_{n-3,n-1}(R/I)$, then $\beta_{n-3,n-2}(R/I)$, $\beta_{n-4,n-2}(R/I)$, and $\beta_{n-5,n-2}(R/I)$, etc.)

Comment by Gwyn Whieldon

2011-07-31T02:55:17Z

So I hadn't given much thought to setting up an alternate projective dimension checker with this. I just meant that at the Macaulay 2 workshop at the IMA this previous week, David Cook (one of Uwe Nagel's students) and I were working on an interface between GAP and M2 that would let someone call functions like "homology," "cohomology", "bistellar moves", "randomize complex" etc. directly from Macaulay.

Comment by Gwyn Whieldon

2011-07-31T02:05:15Z

Still, GAP has both a package to deal with simplices ("simpcomp") and a package with fast homology calculations("homology"), so if you suspect that the projective dimension is hit at a low regularity or at a number of vertices close to the total vertex set, these are often much faster. We're still working on a "SimplicialComplexesPlus" package for Macaulay 2 that calls both of these functions in GAP directly from M2 (it's not distributed yet but it's essentially done.)

Comment by Gwyn Whieldon

2011-07-31T02:00:33Z

It was easy in the case above since the projective dimension was "hit" by a subcomplex on vertex size k+2=n (where n=total # of vertices) and the complex was connected.

Comment by Gwyn Whieldon

2011-07-31T01:59:15Z

(1) That every subcomplex on a vertex set of size k+2 through n is connected, every subcomplex on a vertex set of size k+3 through n has no first homology, every subcomplex on a vertex set of size k+4 through n has no second homology and so on. (2) That there exists some subcomplex on a vertex set of size k+1 which is disconnected, or that there exists some subcomplex on a vertex set of size k+2 which has nontrivial first homology or... Etc. This becomes difficult. (Replace "ith homology is zero on a vertex set of size j" throughout with $\dim(\widetilde{H}_i(\Delta|_{W})=0$ with $|W|=j$.)

Comment by Gwyn Whieldon

2011-07-31T01:54:17Z

True, normally the calculation requires more consideration of subcomplexes. That was the "of the appropriate size" comment. For a general edge ideal on n vertices, the projective dimension is at most n-1 (and is precisely = n-1 if the Stanley-Reisner complex is disconnected.) This follows from checking possible Betti numbers via Hochster's formula. To prove that pd(R/I)=k < n-1, you'd need to show two things: (continued)

Comment by Gwyn Whieldon

2011-07-30T22:59:05Z

Sometimes picking the right CAS system to hit the problem with is a better bet. While having multiple threads of M2 running at the same time or parallelizing the problem is a good approach, I think computing resolutions of these ideals directly (most of my work has been in bounding invariants of resolutions of edge ideals) by splitting up the computation is harder than it sounds.

Comment by Gwyn Whieldon

2011-06-24T17:21:24Z

Thank you very much! That's a great resource to have.

Comment by Gwyn Whieldon

2011-06-24T04:24:20Z

Ah, yes. I should have clarified. I did mean characteristic independent!

Comment by Gwyn Whieldon

2011-05-14T20:46:41Z

On a pop culture response to your comment that 'most people would posit that DM is "combinatorics, graph theory + CS and other applications"', there's a Numb3rs episode where a character, when asked what combinatorics is, responded with "It's a branch of computer science." ::cringe::

Comment by Gwyn Whieldon

2011-05-14T20:43:35Z

That "attachfile" package looks pretty useful.

Comment by Gwyn Whieldon

2011-05-14T20:42:02Z

The location of the link being somewhat "professional" does matter, and before posting this question I was unaware the arxiv allowed supplementary file posting along with articles. I also enjoyed the idea (from "known google" above) of including it in the tex sourcefile as well.