User nathan reading - MathOverflow

To what extent is convexity a local property?

2010-04-21T14:42:20Z

A polyhedron is the intersection of a finite collection of halfspaces. These halfspaces are not assumed to be linear, i.e. their bounding hyperplanes are not assumed to contain the origin. The support Supp(M) of a collection M of polyhedra is the union of the polyhedra in M. I can prove the following theorem:

Theorem. Let M be a finite set of n-dimensional polyhedra in Rⁿ. Suppose:
(i) The interior of Supp(M) is path-connected; and
(ii) For every x in the boundary of Supp(M), there exists a closed halfspace H⁺ bounded by a hyperplane H such that x is in H, and such that H⁺ contains every P in M such that x is in P.
Then Supp(M) is convex.

(Acknowledgment: I proved a characterization of coarsenings of a given polyhedral complex and Ezra Miller remarked that part of my argument amounted to some sort of local criterion for convexity. The theorem above is that criterion.)

The point here is that you only need to check, at each point x of the boundary, that Supp(M) looks sufficiently like a convex set near x, and (ii) says exactly what "sufficiently like a convex set" means in this case.

The question is:

Is this a special case of some general theorem that says that convexity is somehow a local condition?

I suspect that I'm asking for a reference to something known. One convexity person that I asked about felt that it is "highly likely..., that this result is a special case of a result in functional analysis, once properly understood." The same person suggested that there might be a connection to the theory of tight manifolds in topology. For that reason I have added the tags fa.functional-analysis and gt.geometric-topology. My apologies if these tags turn out not to be appropriate.

Answer by Nathan Reading for Efficient enumeration of Bruhat intervals

2012-03-20T19:37:46Z

There is a recursive way to do this that will probably do better for intervals in the middle than the two methods that you said you are unhappy with. Check out Section 5 of N. Reading, "The cd-index of Bruhat Interals:"

http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r74

Basically, here's how it goes: Suppose the interval is $[u,w]$. We choose a reduced word for $w$ and use it to guide a recursive construction. The recursion starts from the singleton interval $[u',w']=[e,e]$ at the identity and, for every letter $s$ in the reduced word, we have a way of constructing either $[u',w's]$ or $[u's,w's]$ from $[u',w']$ by performing a simple global operation (either "doubling" the interval or doing something slightly more complicated) and then killing off certain elements.

There is a lot of computation still, but here is why it is better, for example, than checking all $2^{l(w)}$ subwords of w to find the interval $[1,w]$: In effect, you start with one element, but multiply by $2$ a total of $l(w)$ times, but at each step you get rid of elements you don't want, rather than producing $2^{l(w)}$ elements and then deleting the ones you don't want. You get a similar savings for general intervals $[u,w]$ (which can be much "fatter" than $2^{l(w)-l(u)}$ elements).

Answer by Nathan Reading for Are there Hamilton paths in Cayley graphs of Coxeter groups?

2012-03-20T19:04:07Z

I don't know about Hamilton cycles in this Cayley graph (although someone surely does, and I have a sneaking suspicion that I have heard about them and forgotten). So I'm not answering the question really, but I think this is the answer you want:

To efficiently "traverse" a finite Coxeter group (i.e. visit every element with low memory overhead), then you probably can't do better than the method in John Stembridge's article:

Computational Aspects of Root Systems, Coxeter Groups, and Weyl characters, in "Interactions of Combinatorics and Representation Theory" (pp. 1-38) MSJ Memoirs 11, Math. Soc. Japan, Tokyo, 2001.

You can get it on his website: http://www.math.lsa.umich.edu/~jrs

Look at Section 4. His traversal uses the Cayley graph explicitly, so it will be very compatible with what you're trying to do.

Stembridge has maple packages available for Coxeter group calculations:

http://www.math.lsa.umich.edu/~jrs/maple.html

I don't remember if maple code for the traversal is available on that website.

Comment by Nathan Reading

2012-09-25T13:27:10Z

But definitely publish papers that you will later include in your thesis. Just pay attention both to the journal's policies, as Hersh points out, and also to your university's requirements. None of this should be a problem, as long as you pay attention, because publishing a paper that later goes into your thesis is a very standard practice.

Comment by Nathan Reading

2012-09-25T13:23:59Z

You might also look into your own university's policies. When I was making these decisions, I noticed that my university (U. Minnesota) required me to have written permission from the publisher of the journal article to include the article in the thesis. I suspect that if I had ignored this requirement, nothing bad would have happened. But one would hate to have an over-zealous administrator tell you at the last minute that your thesis cannot be accepted.

Comment by Nathan Reading

2012-06-16T02:05:30Z

A good person to ask would be Muge Taskin (former student of Vic Reiner, now at Boğaziçi University in Turkey). She doesn't appear to be a MathOverflow user but you can find her website through Vic's page, under students. I have a vague recollection of asking Muge this question and getting an affirmative answer. But I may be remembering wrong.

Comment by Nathan Reading

2010-04-22T13:02:19Z

Thanks. You were right about the pre-80's book being the best bet. The Valentine reference that Ivanov pointed out has this and some variations.