co.combinatorics - Mathematical solution for a two-player single-suit trick taking game?

The question on games and mathematics that appeared recently on mathoverflow
(Which popular games are the most mathematical?)
reminded me of a problem I encountered some time ago : starting with the insane
dream of completely solving the game of bridge with a nice mathematical theory,
I ended up considering extremely simplified versions of bridge. One of them was
as follows : there are only 2 players instead of 4, and instead of the usual
deck there are only 2n cards numbered from 1 to 2n. Each player holds half
of the deck, so this is a "complete information" game : each player knows exactly
what is in his opponent's hand. There are no bids, just a sequence of n moves
where each player drops a card ; as in bridge the strongest card wins the trick
and the winner of the game is the player with the largest number of tricks
in the end (take n odd to avoid draws). Also, the winner of the preceding
trick is the first to play (for the very first move the first player is determined
by some rule, random or other ; this is immaterial to the subsequent discussion).

This looks like a very basic kind of game, especially amenable to
mathematization : for example the set of all initial positions is nicely indexed
by the subsets $I$ of $lbrace 1,2, ldots , 2nrbrace$ whose cardinality is $n$
(say $I$ is the set of cards held by the first player). I was
however unable to answer the following questions :

• Is there an algorithm which, given the initial position, finds out which player
  will win if each one plays optimally ? What is the best strategy ?

  
  
  
  • Has this game already been studied by combinatorialists ?
  
  

gr.group theory - nilpotent matrices over polynomial rings

I am looking for an analogue of the Jordan normal form for nilpotent matrices over the
polynomial ring ${mathbb Z}[x_1, dots, x_n]$. More precisely, is there a description for the orbits of action by conjugation of $GL_m({mathbb Z}[x_1, dots, x_n])$ on $M_{m times m}({mathbb Z}[x_1, dots, x_n])$?

evolution - Is there any reason for the variation in mitochondrial DNA size?

Shorter DNA would allows easier synthesis, but more introns could allow for more different transcription factors to influence gene expression.

Human mitochondria probably does not need to be as adaptable as mitochondria in yeast, since the a human cell's environment tends to be more stable. This could provide a viable reason as to why human mitochondria does not need as many introns, but this is only how I imagine things. I have no proof or experience to validate any of this - its just a possiblility.

game theory - Baccarat and the way to win it

Counting cards is possible, but extremely ineffective in baccarat.

In blackjack with n decks, you might model the game as starting out with a house advantage of 0.5%-1% while each card might affect the house advantage by +- 0.5%/m, where m≤n is the number of 52 card decks left in the shoe. So, it's not terribly unlikely that you reach a situation in which the deck is in your favor, although casinos try to shuffle before too many cards are dealt. If you try to monitor the deck's composition and bet more when it is in your favor, then you are counting cards, and you can obtain an advantage. Favorable decks are common enough that you can win at blackjack (until the casino notices and bars you) while varying your bet size by a relatively small amount, e.g., a factor of 4, although this depends on many other specifics such as how far into the decks are dealt before the decks are shuffled.

The problem with baccarat is that card removal has a much lower effect on the house edge. This means you would often have no advantage at any point in the shoe, and you would wait for a vary small advantage. I don't think anyone does it seriously, unlike blackjack.

See The Wizard of Odds on counting in baccarat which contains this comment:

"I hope this section shows that for all practical purposes baccarat is not a countable game. For more information on a similar experiment I would recomment The Theory of Blackjack by Peter A. Griffin. Although the book is mainly devoted to blackjack he has part of a chapter titled 'Can Baccarat Be Beaten?' on pages 216 to 223. Griffin concludes by saying that even in Atlantic City, with a more liberal shuffle point than Las Vegas, the player betting $1000 in positive expectation hands can expect to profit 70 cents an hour."

This assumes you are making no bets, but are keeping perfect count, and then jump in with the occasional $1000 bets on 1 hand out of 500.

Comprehensive reference for synthetic euclidean geometry

(I'm french so sorry for my poor English)

I think the best way to teach Euclidean space to children is to just make it simple:

Two parallel lines will never meet. Like on a map that you can show them.

Then the best way to explain a non-Euclidean space to children is with a Earth globe. You show them the meridians and the longitudes. How the meridians are meeting at the poles even if while watching outside, the Earth seems plane. The globe is the best thing to explain that to a child I think. Just put his finger on the North pole.

How could you expect a child to understand that a triangle doesn't have 180 degrees of corners in a non-Euclidean space ?

Maybe i'm too simplist for you but that's what I think.

co.combinatorics - Why do wedges of spheres often appear in combinatorics?

One way to approach this question quantitatively is suggested by probability. One can put various measures on the space of all simplicial complexes on $n$ vertices. One perhaps fairly natural measure is to take a random graph and then take the clique complex. This doesn't give us all complexes on $n$ vertices but every complex is homeomorphic to the clique complex of some graph, so we are covering everything up to homeomorphism as $n to infty$.

The main point of my paper Topology of random clique complexes is that almost all simplicial complexes arising this way are fairly simple topologically. In particular is shown that for a typical $d$-dimensional clique complex, the homology groups $H_k$ all vanish when $k > lfloor d/2 rfloor$ and when $k< d/4$, and that almost all of whatever homology remains is concentrated in the middle dimension $k=lfloor d/2 rfloor$.

It is currently an open problem to decide whether the homology is vanishing (or merely small) between $k=d/4$ and $k=d/2$. If one could establish this, then one would be well on the way to showing that almost all flag complexes are homotopy to a wedge of spheres; indeed the last thing to do would be to rule out torsion in middle homology with integer coefficients.

I don't have a good feel for whether either of these things is even true, but I do think that this paper gives good anecdotal evidence that most flag complexes are somewhat simple topologically, and is a step in the direction of answering Forman's question. (This particular measure seems especially natural from the point of view of combinatorics, since so many simplicial complexes arise as order complexes of posets, hence are automatically flag complexes.)

UPDATE:

(1) I showed recently that for every $k ge 3$, there is a range of edge probability so that the random clique complex (also called random flag complex) is rationally homotopy equivalent to a wedge of $k$-dimensional spheres. In particular all the rational homology is in middle degree. There is only a very small overlap where there is homology in degree $k$ and in degree $k+1$, but in some sense, most of the time there is only homology in one degree. The conjecture that "rationally homotopy equivalent" can be replaced by "homotopy equivalent" is equivalent to showing that with high probability, homology is torsion free.

(2) On the note of torsion in random homology, in joint work with Hoffman and Paquette, we recently showed that for a slightly different model of random simplicial complex, for most of the range where rational homology is vanishing, integer homology is also vanishing.

There are one or two technical issues in applying the method of (2) in the setting of (1) (namely non-monotonicity of homology), but so far it seems like there is reason to believe that the method will go through eventually.

Together, these two recent results suggest that a random flag complex (for a suitable range of edge probability $p$) is homotopy equivalent to wedges of $d$-dimensional spheres. Random flag complexes seem to me like a very natural model for addressing your question probabilistically, since so many complexes in combinatorics are flag complexes, arising as order complexes of posets, etc.

geometric langlands - A question on group action on categories

The $G((t))$ action and the $Rep(G^vee)$ [or equivalently of $G^vee$ itself after deequivariantization, as Victor explains] are of quite different natures -- the former is a "smooth" action, and the latter an "algebraic" or "analytic" actions (the adjectives smooth and analytic come from analogy with p-adic rep theory).
i.e. there are many kinds of notion of group action, and they are (to me) most conveniently summarized by describing the corresponding notion of group algebra which acts. An algebraic action of a group on a category is an action of the "quasicoherent group algebra" of G, ie the monoidal category of quasicoherent sheaves wrt convolution. (though I'd feel much safer if we said all this in a derived context, makes me uneasy otherwise).
A smooth action is an action of the monoidal category of D-modules on G, the "smooth group algebra" -- analog of smooth functions on a p-adic group. Such an action is the same as an algebraic action, which is infinitesimally trivialized. Such examples are studied in Chapter 7 of Beilinson-Drinfeld's Hecke manuscript and the appendix to the long paper by Gaitsgory-Frenkel, in particular.

PS the "equivariantization" dictionary between categories over BH and categories with H action is a nice simple case of descent --- you describe things over BH as things over a point with descent data, that descent data is given by the map H --> pt,
the two maps H x H---> H, and so on. When you assemble this together (most efficiently using the Barr-Beck theorem) you get the desired dictionary. (Of course if you want to consider categories as forming a 2-category you'd need a 2-categorical version of Barr-Beck, but for most practical purposes I know of you can get by with the current
Lurie [$(infty,$]1-categorical version.