User russ woodroofe - MathOverflow

Answer by Russ Woodroofe for Philosophy behind Yitang Zhang's work on the Twin Primes Conjecture

2013-06-05T10:21:03Z

At a fairly non-detailed level, the Simons Foundation has a nice article on the subject, which I understand has also been picked up by Wired:

https://www.simonsfoundation.org/features/science-news/unheralded-mathematician-bridges-the-prime-gap/

To summarize very briefly, he is building on work by Goldston, Pintz, and Yıldırım. The article describes his innovation as "... to use not the GPY sieve but a modified version of it, in which the sieve filters not by every number, but only by numbers that have no large prime factors."

A lot of smart people were working very hard on this problem, and surely the overview article makes it sound a lot easier than it actually was! But the article does make one feel one understands a little of the overview or "philosophy" of the proof.

Answer by Russ Woodroofe for Motivation for Frankl's conjecture?

2013-05-22T16:12:22Z

Frankl originally stated the dual of the problem as written here, i.e., in terms of intersections instead of unions. This seems to have been in the 1979 edition of the Handbook of Combinatorics [edit: No such edition exists, and I'm not sure of the original source. See comments below], which isn't that easy to find, but the current edition is up on Google Books, and he states it in this form at the beginning of his (updated) chapter on Extremal Set Systems as Conjecture 2.1: For an intersection-closed family of subsets of $[n]$, there is an element that is contained in at most half the subsets.

I always assumed that the conjecture was following in the spirit of Erdos-Ko-Rado type theorems. Let me expand below:

The Erdos-Ko-Rado Theorem bounds the size of a family of small sets $\mathcal{F}$ with pairwise nonempty intersection (see http://en.wikipedia.org/wiki/Erdős–Ko–Rado_theorem for details). An extension of this due to Hilton-Milner says that a maximum-size family of small subsets of $[n]$ with pairwise nonempty intersection has an element contained in all of the subsets.

In the intersection-closed family $\mathcal{G}$ taken by considering all intersections of sets from $\mathcal{F}$ (satisfying the Erdos-Ko-Rado/Hilton-Milner conditions), this says that there is an element contained in all subsets from $\mathcal{G}$. If one makes it this far, it's reasonable to ask how few a number of subsets an element may be contained in, which is exactly what Frankl's Conjecture concerns.

Answer by Russ Woodroofe for Another colored balls puzzle

2013-05-13T21:11:11Z

I think you can verify Greg Martin's answer using indicator variables and linearity of expectation.

Let the random variable $X_i$ be the number of steps where one of the balls has the $i$th color before the $i$th color either disappears or becomes the only color.

The expected value of $X_i$ is as in the Gambler's Ruin, that is, $1 \cdot (n-1) = n-1$.

Each step involves two colors, hence the time to a single color is $\frac{1}{2} \sum X_i$.

The $\binom{n}{2}$ answer follows.

Answer by Russ Woodroofe for Generalization of join of simplicial complexes

2013-05-07T15:12:49Z

Well, the deleted join has been studied. Somewhat informally, that's where you take the join of a simplicial complex $\Delta$ with itself, then delete the faces $\sigma_1 \cup \sigma_2$ in $\Delta * \Delta$ such that $\sigma_1 \cap \sigma_2 \neq \emptyset$ in $\Delta$. The deleted join is nice from the Borsuk-Ulam point of view, because it admits a free $\mathbb{Z}_2$ action by exchanging the two copies of $\Delta$.

A related construction is the Bier sphere, where you replace the second copy of $\Delta$ with the combinatorial Alexander dual.

Matousek discusses both deleted joins and Bier spheres in his book Using the Borsuk-Ulam Theorem.

Answer by Russ Woodroofe for Does every simplicial polytope have a topology-preserving contractible edge?

2013-05-05T21:36:06Z

I brought this thread to the attention of Eran Nevo, who gave some more references, and pointed out that the answer to the converse of your question (2) is "no".

In his thesis, which I gave the arXiv link to above, and in the paper version of this "Higher minors and Van Kampen's obstruction", Nevo defines a strongly edge decomposable sphere to be a sphere which can be reduced to the simplex by edge contractions. He shows that in any PL-manifold (in any dimension), an edge is contractible if and only if it satisfies the link condition.

Then Satoshi Murai in "Algebraic shifting of strongly edge decomposable spheres" shows that any squeezed sphere is strongly edge decomposable. (Murai also has an earlier paper which is related, "Generic initial ideals and squeezed spheres".) Since there are more squeezed $d$-spheres than polytopes for $d \geq 5$, there are non-polytopal spheres where an edge contraction leaves a polytopal sphere. Though I didn't see $d=4$ settled explicitly one way or the other in the papers I looked at, I suspect that there are non-polytopal squeezed 4-spheres as well (and probably this is known). Every squeezed $3$-sphere is polytopal.

Another paper which is somewhat relevant is Babson and Nevo "Lefschetz properties and basic constructions on simplicial spheres".

I also thought a bit about the forward direction of your question (2). If $vw$ is a contractible edge in the boundary of the convex hull of $V$, it looks plausible to me that the edge contraction should correspond to passing to (boundary of) the convex hull of $V \setminus \lbrace v,w \rbrace \cup x$, where $x$ is a point on $vw$. For as you 'slide' $v$ and $w$ together, the link condition seems to prevent new faces from being created. (Obviously, there is a lot to be checked with this idea!)

Answer by Russ Woodroofe for Testing simplicial complexes for shellability

2013-04-24T01:00:56Z

As you point out (relayed from Frank Lutz), it seems likely that checking shellability is NP-hard.

But all is not lost:

A complex that is shellable usually has lots of shellings, and it's often quick to find them by recursively trying to extend a partial shelling. The above-mentioned answer mentions some ways that this can be made more efficient.
A (pure) complex that is not shellable often has a negative component in its $h$-vector, a certain re-encoding of the $f$-vector. See
http://en.wikipedia.org/wiki/H-vector
For non-pure complexes, you can check the so-called $h$-triangle -- see Björner and Wachs, "Shellable nonpure complexes and posets I".
Since shellable complexes (more generally sequentially Cohen-Macaulay complexes) have positive $h$-triangles, this gives a quick way of eliminating some complexes that are not shellable.

You could get a little more involved with (2), and check for positive $h$-triangles of every link in the complex, since a link in a shellable complex is shellable.

In practice, when I've had complexes that I've wanted to computationally check shellability on, I've generally found the combination of the two approaches to give me an answer. You can either first check for obvious non-shellability with (2), and if everything is positive apply (1); or else first check shellability with (1), and if the computation appears to hang, then look for a negative entry in the $h$-triangle.
(But this works for me partly because the complexes I look at usually arise from some kind of "nice" combinatorial object or process.)

Answer by Russ Woodroofe for Examples of interesting false proofs

2013-03-19T19:38:10Z

I'm fond of the following false proof of the Strong Law of Large Numbers. Let $X$ be a random variable with expected value $\mu$ and variance $\sigma^2$, and let $X_1, X_2, \dots$ be i.i.d. copies of $X$. Then $$\operatorname{Var} ( \frac{1}{n} \sum_{i=1}^n X_i ) = \frac{1}{n^2} \cdot n \sigma^2 = \frac{\sigma^2}{n} \rightarrow 0 \textrm{ as } n\rightarrow\infty $$ and since a random variable with variance 0 takes on a single value with probability 1, we must have $$\lim_{n\rightarrow\infty} \frac{1}{n} \sum_{i=1}^n X_i = \mu \textrm{ almost surely.}$$ (It's a memorable heuristic reason to tell undergraduate probability students, even if not a true argument.)

Answer by Russ Woodroofe for lattice of subalgebras of a finite commutative algebra

2013-01-30T03:16:55Z

(Building on Goldstern's comment:) If fields are ok, (and if you allow infinite algebras -- see comment by Mariano Suárez-Alvarez below) then the distributivity certainly does not hold.

Take e.g. a finite degree extension $F$ of $\mathbb{Q}$ with Galois group $G$. Subalgebras of $F$ are subfields, by undergraduate field theory, so the subalgebra lattice over $\mathbb{Q}$ is the field extension lattice of $F:\mathbb{Q}$. (I'm assuming that you're taking all your algebras over a fixed field, here $\mathbb{Q}$.) By the Galois correspondence, the field extension lattice is anti-isomorphic to the subgroup lattice of the Galois group.

And subgroup lattices certainly need not be distributive. Indeed, by a theorem of Ore, the subgroup lattice $L(G)$ of a finite group $G$ is distributive iff $G$ is cyclic.

Answer by Russ Woodroofe for Is the topological concept of collapsible useful?

2013-01-23T21:51:18Z

If you're willing for "useful" to apply to a field other than topology itself: collapses are quite important in combinatorics. Elementary collapses correspond (via Euler characteristics) to matching up equi-numerous objects counted with opposite signs in inclusion-exclusion type problems.

Discrete Morse theory is the generalized version of this. The basic idea in discrete Morse theory is that one can collapse faces of adjacent dimension in skeleta of a simplicial complex, then glue on higher dimensional faces in a way respecting the collapsing (without changing homotopy type). Discrete Morse theory has been a quite important tool in topological combinatorics for the past 10 or 15 years. See the papers of Forman: "Morse theory for cell complexes" introduced the topic (though I should mention that the basic idea was discovered by Ken Brown in "The geometry of rewriting systems: a proof of the Anick-Groves-Squier Theorem"), or "Topics in combinatorial differential topology and geometry" is a survey article.

Discrete Morse theory can also be seen as a generalization of the theory of shellings (also based on a collapsing idea), which has been important in topological and algebraic combinatorics since the late 70s/early 80s.

Answer by Russ Woodroofe for maximal subgroups of finite simple groups

2012-11-17T19:49:01Z

The Atlas of Finite Group Representations has information on the maximal subgroups of some particular finite simple groups. This is at least a handy place to start. See

http://brauer.maths.qmul.ac.uk/Atlas/v3/lin/L253/#maxes

for an example. The front page is at

http://brauer.maths.qmul.ac.uk/Atlas/v3/

Answer by Russ Woodroofe for Visualizing large posets

2012-10-16T01:07:26Z

I'm seeing this question very late, but have two possibly useful suggestions for drawing posets:

My favorite way to automatically draw large graphs with unknown structure is GraphViz. See http://www.graphviz.org/
With some work, this can be made to give poset diagrams. That's one of the good options for output of Stembridge's Poset package for Maple, as mentioned in one of the other answers. (But GraphViz is open source software, which seems like a significant advantage to me.) Looking at the source code of Stembridge's package might be a good place to start in figuring out which GraphViz options to look at.
GAP with the XGap (for Unix/Xwindows) or my own Gap.app (for Mac) front-end has code which allows manipulating Hasse diagrams of posets. I have found it useful for making good diagrams of small to medium size posets. I realize that the question asks about large posets, but include this for completeness.
For good results, GAP requires you to specify the position of the vertices (and automatically draws the edges for you), so it helps if you have some idea of the structure of the poset.
(I can share an example or two of presenting poset diagrams with GAP, if it would be helpful.)

Answer by Russ Woodroofe for Computer aided homology computations

2012-09-12T16:31:11Z

The Homology package for GAP (by Dumas, Heckenbach, Saunders, and Welker) doesn't sound exactly like what you want, as it focuses on simplicial homology, but the techniques it uses might be helpful for you to look at.

It uses the LinBox C++ libraries for handling the linear algebra, and this might be useful in rolling your own. Available at http://www.linalg.org .

Answer by Russ Woodroofe for Constructing a simplicial set homology-equivalent to a given CW complex

2012-07-06T23:25:31Z

(the following is an expanded version of what was previously a comment)

I don't see why you think homotopy equivalence is an unreasonable requirement. Indeed, Theorem 2C.5 of Hatcher's Algebraic Topology says that every finite CW complex is homotopy equivalent to a finite simplicial complex.

His proof does give a standard `method' for turning a CW complex into a homotopy equivalent simplicial complex. It appears to me that it can be turned into an an actual algorithm.
The two main steps that you'd have to implement are: find a simplicial approximation of each attaching map, then find a simplicial subdivision of the mapping cone.

I'll remark that as far as simplicial analogues of mapping cones go, Jonathan Barmak has a nice technique for posets in this paper, where he essentially takes a subcomplex of the join of two posets. Perhaps his technique could be generalized to all simplicial complexes.

Answer by Russ Woodroofe for Using MAGMA for Group Theory

2012-03-28T03:00:12Z

Although you say you'd prefer not to use GAP, producing a Hasse diagram is very easy in GAP, at least with the right packages.
You'll need the xgap GAP package; and either the xgap binaries, which requires an X Windows system (easiest done with Linux or a similar Unix-like system), or else Gap.app, which requires a Mac.
Once you have these installed, start xgap/Gap.app, and follow these steps:

Type "GraphicSubgroupLattice(SymmetricGroup(4));"
In the window that pops up, go to the Subgroups | All Subgroups menu.

The Hasse diagram of the subgroup lattice will appear.

It's also quite easy to show parts of the subgroup lattice -- essentially, you can take any list of subgroups and show the inclusion relations. To do this:

Type "GraphicSubgroupLattice(G);" as before.
Compute the list of subgroups you want to display. It should be the output of the last GAP command.
Go to the Subgroups | Insert Vertices menu.

The Hasse diagram of the subposet consisting of subgroups from your list will appear.

There's probably a comparably easy way to show Hasse diagrams in MAGMA. (But I'm telling you what I know...)

Xgap is available from:
http://www.gap-system.org/Packages/xgap.html
Gap.app is available from:
http://cocoagap.sourceforge.net/

Answer by Russ Woodroofe for Proving that the complement of a bipartite graph has chromatic number equal to clique number

2012-02-25T03:43:37Z

According to Wikipedia
http://en.wikipedia.org/wiki/König's_theorem_(graph_theory)#Connections_with_perfect_graphs
the statement that $\chi(\overline{G}) = \omega(\overline{G})$ for all bipartite $G$ is actually equivalent to König's Theorem.

Answer by Russ Woodroofe for A flag complex is contractible iff the underlying graph is....?

2012-01-27T19:28:26Z

A nice graph theory lemma for showing homotopy equivalence that builds on the "clique starring" already discussed is stated as Lemma 3.2 of Alexander Engström's paper arXiv:math/0508148. I'll rephrase in terms of the language the question was asked in (clique complexes rather than independence complexes).

Lemma: If $v$ and $w$ are vertices of a graph $G$ with $N[v] \subseteq N[w]$, then $C(G)$ is homotopy equivalent to $C(G \setminus v)$.
(Here $N[v]$ is the closed neighborhood of $v$, i.e., $v$ and all its neighbors.)

The proof technique is that of elementary collapses. See http://en.wikipedia.org/wiki/Collapse_(topology).
Even if the lemma of Engström doesn't give you what you need, the broader technique of collapsing can be quite useful. Collapses are the "engine" of discrete Morse theory, for example.
It's not too hard to write a computer program (or some are available) that does automatic collapsing, and you could generate a large number of examples this way. If you can collapse a complex to a point, then the complex is contractible. The converse is not true, but the program might at least give you a smaller complex to examine by hand.

On the other hand, as Benjamin Steinberg points out, the barycentric subdivision of any simplicial complex is flag, so classifying contractible flag complexes should be as hard as classifying contractible simplicial (and more generally CW) complexes.

Answer by Russ Woodroofe for Reference request on Leray numbers

2011-12-04T21:09:15Z

For question 1, the earliest reference I know is:

Ralf Fröberg, On Stanley-Reisner rings, Topics in algebra, Part 2 (Warsaw, 1988), Banach Center Publ., vol. 26, PWN, Warsaw, 1990, pp. 57–70.

(This actually proves an equivalent result on linear resolutions.) It seems to be the kind of thing that gets rediscovered several times from different perspectives, however, and it's possible that there's an earlier reference that I don't know about.

For question 3, the connection is immediate from Hochster's Formula, which is in:

Melvin Hochster, Cohen–Macaulay rings, combinatorics, and simplicial complexes, Ring theory, II (Proc. Second Conf., Univ. Oklahoma, Norman, Okla., 1975) (B. R. McDonald and R. Morris, eds.), Lecture Notes in Pure and Applied Mathematics Vol. 26, Marcel Dekker, New York, 1977, pp. 171–223.

The first place I know that the connection is explicitly observed is the article of Kalai and Meshulam, "Intersections of Leray complexes and regularity of monomial ideals".

I don't have any firm information on question 2. (But the result is close to immediate, once you ask it in that language.)

Comment by Russ Woodroofe

2013-05-30T00:46:56Z

If you're happy with an approximation, you could use Stirling's Formula to approximate the factorials. As the other comments have noted, exact computation is likely to be fairly slow...

Comment by Russ Woodroofe

2013-05-23T18:11:12Z

The nonnesting (or possibly noncrossing) arc diagrams, items (p) and (q) on Stanley's list, look like a promising object to find a bijection with. One would just need to find a good way of labeling the vertices with nonnegative integers that describes the arc pattern...

Comment by Russ Woodroofe

2013-05-22T19:14:27Z

@quid: I edited to correct and avoid confusion. Perhaps someone else will know more about the history of the conjecture, and why it is credited to Frankl rather than Duffus.

Comment by Russ Woodroofe

2013-05-22T16:36:06Z

@quid: Maybe not. I certainly didn't track it down! I saw a reference (Doug West's page on the conjecture, IIRC) which gave a year of 1979 and referred to the Handbook of Combinatorics. But it's possible that the conjecture was made at a conference/similar, and not written down until much later; this would make giving a reference quite difficult.

Comment by Russ Woodroofe

2013-05-22T16:33:16Z

@Gerhard: yes, that's embarrassing. Fixed it.

Comment by Russ Woodroofe

2013-05-22T16:16:08Z

Doh! I misread it as finding one ball total from the bins. (The question is vague as to whether the bins are chosen with or without replacement.)

Comment by Russ Woodroofe

2013-05-17T19:48:00Z

How are your matroids represented? If you have them represented as a set of circuits, then there's a clear algorithm that will check your condition in time $m^2$ (where $m$ is the total number of circuits). But I believe passing from the maximal independent set representation to the circuit representation to be NP-hard...

Comment by Russ Woodroofe

2013-05-14T17:29:58Z

A very similar problem has already been posted at mathoverflow.net/questions/41939/… but the method of choosing balls is a little different.

Comment by Russ Woodroofe

2013-05-14T15:00:57Z

@Jon: Yes, that's a clearer explanation of how $X_i$ is defined.

Comment by Russ Woodroofe

2013-05-13T22:29:54Z

This is an example of the general technique of using indicator variables to calculate an expected value. Some more (easier) examples are worked out at mikespivey.wordpress.com/2011/12/01/… or in your favorite Intro Probability textbook.

Comment by Russ Woodroofe

2013-05-13T22:26:49Z

@Greg Martin: Every step in the real game involves 2 colors, say $i$ and $j$, and is counted by $X_i$ and $X_j$. Thus, the number of steps in the real game is half the sum of the $X_i$'s. (But as you note, for any fixed $i$, there are steps in the real game that are ignored by $X_i$.) Linearity of expectation then says that the expectation of the sum is the sum of the expectations.

Comment by Russ Woodroofe

2013-05-07T20:18:30Z

If I understand what you're looking for correctly, it suffices to delete the faces consisting of one point from every $X_i$. Since one can specify a simplicial complex either by the maximal faces or else by the minimal non-faces, this complex is well-defined. (You're just adding some new minimal non-faces to the join.) The induced subcomplex on such a vertex subset (consisting of one point from each complex) will be a simplex boundary, hence a sphere. I haven't seen these studied anywhere, but that doesn't mean that they haven't been.

Comment by Russ Woodroofe

2013-05-03T05:28:51Z

It's been long enough that you've probably either solved the problem or lost interest, but since no one else has mentioned it, I'll point out that the property you mention is almost that of semimodularity. That is, if you require the diamond and disallow the pentagon (in your two allowed diagrams given two elements covering a common element) it is exactly semimodularity. Semimodularity is well-studied -- see e.g. the book by Manfred Stern.

Comment by Russ Woodroofe

2013-05-02T17:57:12Z

I'll mention for general interest that Eran Nevo studied edge contractions in his thesis, which is available on the arXiv: arxiv.org/pdf/0709.3265.pdf . He says more about the consequences of an edge contraction than the existence of one, but you might find the algebraic shifting arguments in there interesting.

Comment by Russ Woodroofe

2013-03-31T13:41:24Z

@Igor: The cover letter is where you get to tell the story of why you'd fit well into this particular job. (Or at least to show that you've read the advertisement.) That's what Alexander is talking about, I think. I didn't like jumping through that hoop when I was on the market, but ignoring it is not advised. I have heard of other schools using the cover letter as the basis for an early winnowing.