User jonah ostroff - MathOverflow

Answer by Jonah Ostroff for Permutations with restriction

2012-03-21T01:30:47Z

There's a nice result, I think due to Carlitz, Scoville, and Vaughan (I learned it as the "Carlitz-Scoville-Vaughan theorem", but I'm not sure how common that is) that the o.g.f. for words in which no pair of consecutive letters is among a restricted set is the multiplicative inverse of the o.g.f. for words in which every pair of consecutive letters is in that restricted set, evaluated at $(-a,-b,-c,\dots)$.

So for your problem, the o.g.f. for words in $a,b,c$ where all adjacent letters are the same is $$g(a,b,c) = 1 + a + b + c + a^2 + b^2 + c^2 + \cdots = 1 + \frac{a}{1-a}+\frac{b}{1-b}+\frac{c}{1-c},$$ which means the generating function for words in $a,b,c$ where no adjacent letters are the same is $$f(a,b,c) = \frac{1}{g(-a,-b,-c)} = \frac{1}{1-\frac{a}{1+a}-\frac{b}{1+b}-\frac{c}{1+c}}.$$

Answer by Jonah Ostroff for Giving a math talk with no blackboard or projector

2011-09-14T22:32:28Z

For a good 15-minute exercise for undergraduates, I like Heidi Burgiel's paper on how even a perfect Tetris player must eventually lose with probability one. I've given it as a talk before with almost no boardwork, and that was only to prove more rigorously some ideas that are pretty intuitive: that the best way to stack Ss and Zs vertically is by putting like-on-like, which I think most undergrads are happy to believe with just a little hand-waving.

Answer by Jonah Ostroff for Gale-Ryser stable marriage theorem: can we entrust matchmaking to monkeys?

2011-07-12T17:51:33Z

For (1), yes, it can loop endlessly. Here's a demonstration with 8 people.

Suppose you have 3 ladies and 3 gentlemen standing in a circle, along with one more lady and gentleman (the pariahs) inside the circle. Here are the preferences you need to know about: everyone around the circle prefers to person to his or her right over the person to his or her left, and prefers either of them to the oppositely-sexed pariah in the center. (The compatibility of people diagonally opposite each other and the opinions of those in the center won't matter for the purposes of this solution.)

Initially, choose a pair of diagonally opposite people and pair each of them up with the appropriate pariahs in the center. Pair up the remaining four people around the circle in adjacent pairs. This is unstable: those matched with pariahs would prefer to be matched with the neighbor to the left, and the feelings are reciprocated (since everyone around the circle prefers right over left).

Performing both of these swaps, however, only serves to rotate the whole picture 120° while preserving the symmetry of the preferences we care about. Do it two more times and you've got the original matching again.

Answer by Jonah Ostroff for Generalization of a horse-racing puzzle

2010-12-30T17:30:21Z

Well, this particular strategy generalizes for finding the k best horses when the track size is $n = (k-1)(k+2)/2$ and the number of horses is $n^2$, and it takes n+2 races as in your example:

Split them into n groups of size n, race them in those sets, and label as $a_{11}, a_{12}, \dots, a_{1n}, a_{21}, a_{22}, \dots, a_{2n}, \dots, a_{nn}$ as before (so the horse who came in $j$th place in the $i$th race has label $a_{ij}$. Then race $a_{11}, a_{21},\dots,a_{n1}$, and relabel the first subscripts of all horses using the results of this race. The winner of that race is the best horse. To determine the other k-1 best horses, race the n other horses who have fewer than k horses that are better than them (directly or by transitivity): $a_{12}, a_{13}, \dots, a_{1k}, a_{21}, a_{22}, \dots, a_{2(k-1)}, a_{31}, a_{32}, \dots, a_{3(k-2)},\dots, a_{k1}$. (Note here that conveniently $n = (k-1) + (k-1) + (k-2) + (k-3) + \dots + 2 + 1 = (k-1)(k+2)/2$.)

But this still leaves open the question of what to do for other cases.

Triangulations of polyhedra

2010-11-12T19:45:01Z

A topologist came to me with this question, but everything I think should work doesn't.

How many triangulations are there of a polyhedron with n vertices?

By a "triangulation" of a polyhedron P we mean a decomposition of P into 3-simplices whose interiors are disjoint, whose vertices are vertices of P, and whose union is P. Since this obviously depends on the polyhedron, let's say that P is the convex hull of n points on the curve (t, t^2, t^3). (I think this is general, but a proof of that would be nice too.) In particular, this means that all of the faces are triangles, since no four vertices are coplanar.

Since triangulations of a polygon are counted by the Catalan numbers, a reasonable first guess is that these are counted by the generalized Catalan numbers $C_{n,k} = \frac{1}{(k-1)(n+1)} {kn \choose n}$, which count k-ary trees (among other things). But just at n=5 we run into trouble: there are 2 (not 3) such triangulations, and they don't even contain a fixed number of pieces: one of them triangulates P into two tetrahedra, and one breaks it into three.

This seems obvious enough that someone would have asked it before, but I'm not finding anything. Of course, answers to the obvious generalization (triangulations of k-polytopes whose vertices lie on (t, t^2, ..., t^k)) are welcome as well.

Answer by Jonah Ostroff for Are there more connected or disconnected graphs on n vertices?

2010-11-04T22:53:32Z

Connectedness wins, since the complement of any disconnected graph is connected.

EDIT: Perhaps you'd like a proof of this. Let G be a disconnected graph, G' its complement. If v and u are in different components of G, then certainly they're connected by an edge in G'. And if they're in the same component of G, then there's some w in another component (since G was disconnected), so v-w-u is a path in G'.

Answer by Jonah Ostroff for Combinatorial results without known combinatorial proofs

2010-10-08T14:36:24Z

One result I like is that the number of 321-avoiding permutations of length 2n whose matrices are 180°-symmetric is (2n choose n). The best proof I know is fairly short, but I wouldn't call it bijective:

Under the Robinson-Schensted correspondence, the 180°-symmetric permutations are exactly the ones which map to ordered pairs of self-evacuating tableaux, which are in turn in bijection with ordered pairs of domino tableaux in the same shape. (See Stembridge) Now, if you look at the 2-row (since our permutations must be 321-avoiding) domino tableaux of size 2n, there are n+1 Ferrers shapes they can take, and they can be formed from those of size 2n-2 in a way satisfying the relation in Pascal's triangle, so the sum over all 2-row Ferrers shapes of the square of the number of domino tableaux of that shape is the sum of the squares of the binomial coefficients (2n choose i), yielding (2n choose n).

I've tried to "unpack" each of these steps into a simple bijection, but nothing's budged. Still, it seems like the kind of problem that someone else might be able to solve.

Answer by Jonah Ostroff for What are some good examples of non-monotone graph properties?

2010-09-28T12:52:11Z

Gracefulness and harmoniousness are not monotone.

Untrustworthy people picking a random number

2010-08-12T18:57:51Z

Inspired by the party game Mafia, in particular those situations where nobody is clearly innocent or guilty and the group wants to decide on someone random to eliminate.

Suppose n people each have their own personal random number generator (a machine which generates a 0 or 1 at the push of a button, each with equal likelihood), that these random number generators (henceforth RNGs) operate independently from each other, and, most critically, that each RNG can only be read by its owner. They would like to, as a group, decide on one of two courses of action, and they'd like to do so randomly with 50% probability for each choice.

But, a complication: some members of this group are secretly saboteurs, and they have their own preferences for which of the two options to pick. They'll do anything in their power to sway the decision in a particular direction. On the other hand, the non-saboteurs all have one goal in mind: to make this decision process truly unbiased, to wrench the control from those saboteurs. Nobody knows who the saboteurs are (but let's say there aren't very many of them), and nobody knows which of the two options they're trying to sway things towards.

Is there a strategy the group can employ to remove all bias from the selection process? All anyone can do is talk, push the button on his or her own RNG, and tell the results to the others (though they might not believe it).

EDIT: As a further clarification, the players can't all talk at once. So it's not enough to for everyone to pick a number and sum them mod 2, since the last person to give the number might be a saboteur.

Answer by Jonah Ostroff for Generalization of Finch Cheney's 5 Card Trick

2010-04-08T14:42:45Z

Kleber's paper will certainly point you in the right direction if you can find it. (I have a printed out copy, and I don't remember where on the web I got it. Sorry.)

In it, he suggests thinking about a strategy as a pairing up of the $(n!+n-1)_{n-1}$ messages with the ${{n!+n-1}\choose n} = (n!+n-1)_{n-1}$ hands the audience can give you. Of course, you can only pair a message with one of the n! hands that contain its cards, and you can only pair a hand with one of the n! messages you can make with it. So this is just like finding a perfect matching on an n!-regular bipartite graph, and by Hall's Marriage Theorem this is possible.

The bipartite graph you draw here is quite symmetric: aside from being n!-regular, it's also vertex transitive, so any of the n! edges you could choose from a particular vertex v are part of some perfect matching (since one of them is). This is where Kleber's claim that there are "at least n!" strategies come from.

We can get a much better lower bound if this paper is to be believed. Here it says there are at least $\left(\frac{(n!-1)^{n!-1}}{n!^{n!-2}}\right)^{{n!+n-1}\choose n}$ strategies, which for n=2 isn't very enlightening (it says there's at least one, when we know there are really two), but for n>2 puts our previous estimate to shame: with a three-card hand (and thus an eight-card deck), we get at least 2.54x10^21 strategies, a number so fantastically larger than our previous estimate of 6 that I'm still a little bit in shock. (It is, at least, many orders of magnitude lower than the naive upper bound of 6^56, where for each of the 3-subsets of 8 we choose one of the possible messages it could send without worrying about overlap with other hands.)

Anyway, I haven't read the linked paper, but the abstract suggests we might not get a much better lower bound than this. To improve, one might look for results on vertex transitive k-regular bipartite graphs, but I haven't found any.

Answer by Jonah Ostroff for Axiom of Choice and Order Types

2010-02-01T16:42:28Z

The equivalence classes referred to by Wikipedia don't correspond to order types; different orderings belong to the same equivalence class so long as the underlying sets have the same cardinality.

To elaborate: you can define an equivalence relation on unordered sets by saying that A~B if A and B can be ordered equivalently. This is, of course, an equivalence relation on sets, so it partitions the class of unordered sets. It just doesn't do it in the nice way you assumed it did, where different order types end up in different classes.

Graphs preserved under the Hamiltonian path operator

2010-01-03T20:59:00Z

Given a graph $G$ with vertex set $V$, let $HP(G)$ be the graph on $V$ where there's an edge from $u$ to $v$ if and only if there's a Hamiltonian path in $G$ from $u$ to $v$. (I believe this is called the Hamiltonian path operator, but all references I can find to it are from a computational perspective.)

Anyway, here's my question: for which graphs $G$ is $HP(G) \simeq G$? There are some obvious examples (complete graphs, their complements, n-cycles, and $K_{n,n}$s), and at least one less-obvious example ($K_{2,1,1}$, or a square with one diagonal). The latter is certainly more interesting, because the isomorphism between $HP(G)$ and $G$ doesn't just map each vertex to itself. Are there others like it, or any obvious ones I missed? Even better, can we completely classify these graphs?

Answer by Jonah Ostroff for Graphs preserved under the Hamiltonian path operator

2010-01-11T22:01:10Z

Two more large families (one of which includes both David's example and $K_{2,1,1}$) are:

• A 4n-cycle plus n of the 2n long diagonals (every other one).

• A 2n-cycle with an n-cycle inscribed in it along the odd vertices.

Answer by Jonah Ostroff for Hardness of combinatorial optimization after adding one constraint

2009-12-24T15:39:55Z

Okay, here's a less contrived example. While minimal edge coverings can be found in polynomial time, finding a minimal hyperedge covering in general (equivalently, set covering) is NP-hard. On the other hand, finding such a covering when one of the hyperedges spans all vertices on the graph is easy: you just use that edge.

So, given an arbitrary hypergraph, attach a new hyperedge to every vertex and look for a minimal cover. This can be done quickly. But constrain yourself to not using that edge, and you're back to the original NP-hard problem.

Answer by Jonah Ostroff for Hardness of combinatorial optimization after adding one constraint

2009-12-24T01:08:16Z

Sure. We'll construct a normally trivial problem that turns into a question of four-coloring when we restrict one parameter.

For a graph $G$ on $n$ vertices, consider binary words of length $2n+1$. This will represent an assignment of colors 1-4 on the $n$ vertices, with the last bit telling us what the restriction on neighboring colors is. Namely, if the last digit is $i$, then $f$ spits out a 0 (calls it an improper coloring) if some pair of adjacent vertices have colors that are $i$ apart. When it is proper, $f$ spits out the reciprocal of the number of colors used.

Well, this is easy to maximize: just make every vertex the same color and choose the last digit to be 1. Congrats, you only used one color. But if our constraint is that the last digit is 0, then now you're asking whether the graph needs 1, 2, 3, 4, or more colors to properly color (in the usual sense), which you can't answer in polynomial time.

Injective proof about sizes of conjugacy classes in S_n

2009-10-27T20:34:03Z

It's not hard to count the number of permutations in a given conjugacy class of S_n. In particular, the number of permutations in S_n whose cycle decomposition has c_i i-cycles is n!/(Π_i=1ⁿ c_i!i^c_i). It's also not too hard to see that this is maximized for the conjugacy class that leaves one element fixed and permutes the others in an (n-1)-cycle, and that this is strictly the maximum when n ≥ 3.

What I'm looking for is an "injective proof" of this fact. Namely, a set of injections from the other conjugacy classes into the set of (n-1)-cycles. Ideally you should be able to define a single nice function from S_n into these cycles, which is injective but not surjective (for n ≥ 3) when restricted to every other conjugacy class.

Answer by Jonah Ostroff for How do I iterate over binary trees?

2009-11-01T20:09:20Z

Wait, you mean n+1 labels for the leaves and n labels for the internal nodes, right?

Note that such trees are counted by the multinomial coefficient {2n choose 2,2,2,2,...,2} (with n 2s), because their Prüfer codes are exactly the ones containing 2 of all but one of the b_is and 1 of the last one. If you take such a Prüfer code and affix to its end the label of the root, then you're just counting anagrams of b₁b₁b₂b₂...b_n-1b_n-1b_nb_n. I'm not a computer scientist, but these are easy enough to loop through, right?

EDIT: Wait, sorry, this counts full binary trees where left and right children are indistinguishable. I suppose this isn't what you want, is it?

Not too hard to fix, fortunately, since the nodes are already labeled: just decide for each internal node whether the child with the higher label is on the right or left. There are 2ⁿ ways to pick that. We can incorporate this into our earlier counting method by looking at anagrams of the 2n distinct letters b₁c₁b₂c₂...b_n-1c_n-1b_nc_n. (There are, of course, (2n)! of these). Given such an anagram, get a binary tree as follows:

First, chop off the last letter, treat the c_is as b_is, and find the tree with this new string as its Prüfer code. Choose the letter you chopped off to be the root, so every internal node now has two children. To decide which is on the left and which is on the right, ask whether b_i came before c_i in the original string. If so, the child with the smaller label is on the left; otherwise it's on the right.

Variation on a matrix game

2009-10-23T21:23:23Z

The original problem appeared on last year's Putnam exam:

"Alan and Barbara play a game in which they take turns filling entries of an initially empty 2008×2008 array. Alan plays ﬁrst. At each turn, a player chooses a real number and places it in a vacant entry. The game ends when all the entries are filled. Alan wins if the determinant of the resulting matrix is nonzero; Barbara wins if it is zero. Which player has a winning strategy?"

It's not hard to see that Barbara can win this game by reflecting Alan's moves over a vertical line. (In fact, you might say she "wins with multiplicity 1004".) My question is, what if the goals were reversed? That is, suppose Alan (the first player) wants the determinant to be zero, and Barbara wants it to be nonzero. Now who has the winning strategy?

If you expect the result to rely solely on parity, then you should note that Alan wins in the 2×2 case, because he can force a row or column to have only zeroes. Unfortunately, it's not at all clear (to me, anyway) that he can do anything similar to a 4×4 matrix, let alone a 2008×2008 one.

Answer by Jonah Ostroff for Variant of binomial coefficients

2009-10-29T15:44:27Z

(For simplicity, you probably want the last term in the numerator to be z-k+a, right? That way F_(1,k)(z)=\binom{z}{k}. I'll pretend that's what you meant.)

I haven't come across such polynomials, but they're easily expressed in terms of multifactorials. Namely,

F_(a,k)(z)=z!^(a)/[(z-k)!^(a)k!^(a)]

Note that this isn't an integer when a doesn't divide z. EDIT: (And, as Qiaochu points out, when a does divide z it's just regular ol' z-choose-k.)

Answer by Jonah Ostroff for What is the first interesting theorem in (insert subject here)?

2009-10-24T21:13:54Z

Combinatorics: the nth Catalan number is (2n choose n)/(n+1)

Answer by Jonah Ostroff for What is the first interesting theorem in (insert subject here)?

2009-10-24T21:07:21Z

Combinatorics: counting the number of derangements of [n].

Answer by Jonah Ostroff for Can I finitely color Z^2 such that (x,a) and (a,y) are different for every x,y,a?

2009-10-24T00:30:34Z

Nope.

Suppose this were possible. For z \in Z, let R_z be the colors that appear in the row {(x,z) : x≠z \in Z}, and let C_z be the colors that appear in the column {(z,y) : y≠z \in Z}. The coloring condition is that each C_z and R_z is disjoint. Since there are finitely many possibilities for each set, find distinct z and z' where R_z = R_z', and C_z = C_z'. What color is (z,z')? Well, it's in R_z' (and not C_z'), and it's in C_z (but not R_z). So it's both in R_z and not: a contradiction.

(Ninja'd. Drat. Well, different proof at least.)

Answer by Jonah Ostroff for Placing checkers with some restrictions

2009-10-23T22:52:05Z

Comment to Ricky (sorry, can't comment for real just yet): the solutions to your modified problem (exactly -> less than), when read as a sequence of checker positions within the columns, are exactly the parking functions.

Comment by Jonah Ostroff

2011-09-27T22:22:05Z

The same page shows a two-dimensional Venn diagram of five ellipses that is rotationally symmetric, so I think that sentence is referring to a stronger condition.

Comment by Jonah Ostroff

2011-07-18T21:12:31Z

For (2), I've also seen these referred to as "restricted words".

Comment by Jonah Ostroff

2011-07-12T17:57:42Z

After thinking about it more, I guess you can do the same thing with 6 people (which is clearly minimal). I'm not sure why this solution felt more natural.

Comment by Jonah Ostroff

2011-05-27T14:35:09Z

Gerry: 132-avoiding permutations are enumerated by the Catalan numbers.

Comment by Jonah Ostroff

2011-01-24T21:54:05Z

There are eleven of cardinality 6, so clearly the answer is that they follow the progression of the primes! Just kidding. These are the partition numbers: oeis.org/A000041

Comment by Jonah Ostroff

2010-11-16T15:11:24Z

Have you tried requesting it through Inter-Library Loan at your institution?

Comment by Jonah Ostroff

2010-11-12T20:10:08Z

Wonderful. Thanks!

Comment by Jonah Ostroff

2010-11-10T14:13:36Z

You probably know this, but I figure it's worth reminding people that π is an involution if and only if P and Q (the tableaux under RSK) are equal.

Comment by Jonah Ostroff

2010-11-08T04:32:56Z

Counterexample: pick a composite number of the form n = 4k+3 (e.g. 15). Then 2^n-3 ends in a 5.

Comment by Jonah Ostroff

2010-11-06T22:37:45Z

That the complement of a disconnected graph is connected is well known, though I've forgotten and re-discovered this fact three or four times now. As for applying it to the particular question at hand, I have no idea. I'm sure someone has done it before, but I wouldn't necessarily expect it in Bollobas since the argument only applies to the case p=1/2, and doesn't have the flavor of most other results on random graphs.

Comment by Jonah Ostroff

2010-11-06T15:44:21Z

As I mention in a comment to my answer, you can generalize these paths a bit to any tree, so long as that tree isn't a star graph. The nice thing about that generalization is you don't have to check any cases by hand.

Comment by Jonah Ostroff

2010-11-05T14:51:13Z

Tony: Alternatively, take any tree T. The only way T' can be disconnected is if the n-1 missing edges are all incident to the same vertex, i.e. if T was the star graph. So for any other tree, both T and T' are connected.

Comment by Jonah Ostroff

2010-11-05T01:39:51Z

Awesome. I was going to follow up with whether most graphs are k-connected (when n is sufficiently large), and this sounds like a "yes".

Comment by Jonah Ostroff

2010-11-04T23:04:58Z

(Note that this implies the same result for unlabeled graphs, though enumeration is harder.)

Comment by Jonah Ostroff

2010-11-04T22:55:58Z

You mean connected clearly wins out, Thierry? For 4 vertices, 38/64 are connected.