User jonah ostroff - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T22:58:39Z http://mathoverflow.net/feeds/user/1060 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/91758/permutations-with-restriction/91779#91779 Answer by Jonah Ostroff for Permutations with restriction Jonah Ostroff 2012-03-21T01:30:47Z 2012-03-21T01:30:47Z <p>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 <i>every</i> pair of consecutive letters is in that restricted set, evaluated at $(-a,-b,-c,\dots)$.</p> <p>So for your problem, the o.g.f. for words in $a,b,c$ where <i>all</i> 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 <i>no</i> 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}}.$$</p> http://mathoverflow.net/questions/75419/giving-a-math-talk-with-no-blackboard-or-projector/75453#75453 Answer by Jonah Ostroff for Giving a math talk with no blackboard or projector Jonah Ostroff 2011-09-14T22:32:28Z 2011-09-14T22:32:28Z <p>For a good 15-minute exercise for undergraduates, I like <a href="http://www.geom.uiuc.edu/java/tetris/tetris.ps" rel="nofollow">Heidi Burgiel's paper</a> 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.</p> http://mathoverflow.net/questions/70126/gale-ryser-stable-marriage-theorem-can-we-entrust-matchmaking-to-monkeys/70157#70157 Answer by Jonah Ostroff for Gale-Ryser stable marriage theorem: can we entrust matchmaking to monkeys? Jonah Ostroff 2011-07-12T17:51:33Z 2011-07-12T17:51:33Z <p>For (1), yes, it can loop endlessly. Here's a demonstration with 8 people.</p> <p>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.)</p> <p>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).</p> <p>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.</p> http://mathoverflow.net/questions/50737/generalization-of-a-horse-racing-puzzle/50742#50742 Answer by Jonah Ostroff for Generalization of a horse-racing puzzle Jonah Ostroff 2010-12-30T17:30:21Z 2010-12-30T17:30:21Z <p>Well, this <em>particular</em> 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:</p> <p>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$.)</p> <p>But this still leaves open the question of what to do for other cases.</p> http://mathoverflow.net/questions/45863/triangulations-of-polyhedra Triangulations of polyhedra Jonah Ostroff 2010-11-12T19:45:01Z 2010-11-17T00:24:18Z <p>A topologist came to me with this question, but everything I think should work doesn't.</p> <p>How many triangulations are there of a polyhedron with n vertices?</p> <p>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.</p> <p>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 <em>they don't even contain a fixed number of pieces</em>: one of them triangulates P into two tetrahedra, and one breaks it into three.</p> <p>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.</p> http://mathoverflow.net/questions/44877/are-there-more-connected-or-disconnected-graphs-on-n-vertices/44889#44889 Answer by Jonah Ostroff for Are there more connected or disconnected graphs on n vertices? Jonah Ostroff 2010-11-04T22:53:32Z 2010-11-04T22:53:32Z <p>Connectedness wins, since the complement of any disconnected graph is connected.</p> <p>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'.</p> http://mathoverflow.net/questions/5449/combinatorial-results-without-known-combinatorial-proofs/41513#41513 Answer by Jonah Ostroff for Combinatorial results without known combinatorial proofs Jonah Ostroff 2010-10-08T14:36:24Z 2010-10-08T14:36:24Z <p>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:</p> <p>Under the <a href="http://en.wikipedia.org/wiki/Robinson%E2%80%93Schensted_algorithm" rel="nofollow">Robinson-Schensted</a> 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 <a href="http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.dmj/1077245253" rel="nofollow">Stembridge</a>) 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).</p> <p>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.</p> http://mathoverflow.net/questions/40230/what-are-some-good-examples-of-non-monotone-graph-properties/40310#40310 Answer by Jonah Ostroff for What are some good examples of non-monotone graph properties? Jonah Ostroff 2010-09-28T12:52:11Z 2010-09-28T12:52:11Z <p><a href="http://mathworld.wolfram.com/GracefulGraph.html" rel="nofollow">Gracefulness</a> and <a href="http://mathworld.wolfram.com/HarmoniousGraph.html" rel="nofollow">harmoniousness</a> are not monotone.</p> http://mathoverflow.net/questions/35382/untrustworthy-people-picking-a-random-number Untrustworthy people picking a random number Jonah Ostroff 2010-08-12T18:57:51Z 2010-08-15T11:18:35Z <p>Inspired by the party game <a href="http://en.wikipedia.org/wiki/Mafia_(party_game)" rel="nofollow">Mafia</a>, in particular those situations where nobody is clearly innocent or guilty and the group wants to decide on someone random to eliminate.</p> <p>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.</p> <p>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.</p> <p>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).</p> <p>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.</p> http://mathoverflow.net/questions/20667/generalization-of-finch-cheneys-5-card-trick/20735#20735 Answer by Jonah Ostroff for Generalization of Finch Cheney's 5 Card Trick Jonah Ostroff 2010-04-08T14:42:45Z 2010-04-08T14:54:16Z <p>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.)</p> <p>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.</p> <p>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.</p> <p>We can get a much better lower bound if <a href="http://www.sciencedirect.com/science?_ob=ArticleURL&amp;_udi=B6WHT-45SRMS1-9&amp;_user=520880&amp;_coverDate=01%2F31%2F1998&amp;_rdoc=1&amp;_fmt=high&amp;_orig=search&amp;_sort=d&amp;_docanchor=&amp;view=c&amp;_acct=C000023460&amp;_version=1&amp;_urlVersion=0&amp;_userid=520880&amp;md5=aa3f297a22e5087962ec4c451b0cc68b" rel="nofollow">this paper</a> 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.)</p> <p>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.</p> http://mathoverflow.net/questions/13705/axiom-of-choice-and-order-types/13707#13707 Answer by Jonah Ostroff for Axiom of Choice and Order Types Jonah Ostroff 2010-02-01T16:42:28Z 2010-02-01T16:47:32Z <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/10619/graphs-preserved-under-the-hamiltonian-path-operator Graphs preserved under the Hamiltonian path operator Jonah Ostroff 2010-01-03T20:59:00Z 2010-01-18T20:24:46Z <p>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.)</p> <p>Anyway, here's my question: for which graphs $G$ is $HP(G) \simeq G$? There are some obvious examples (complete graphs, their complements, <i>n</i>-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?</p> http://mathoverflow.net/questions/10619/graphs-preserved-under-the-hamiltonian-path-operator/11469#11469 Answer by Jonah Ostroff for Graphs preserved under the Hamiltonian path operator Jonah Ostroff 2010-01-11T22:01:10Z 2010-01-11T22:01:10Z <p>Two more large families (one of which includes both David's example and $K_{2,1,1}$) are:</p> <p>• A 4n-cycle plus n of the 2n long diagonals (every other one).</p> <p>• A 2n-cycle with an n-cycle inscribed in it along the odd vertices.</p> http://mathoverflow.net/questions/9647/hardness-of-combinatorial-optimization-after-adding-one-constraint/9681#9681 Answer by Jonah Ostroff for Hardness of combinatorial optimization after adding one constraint Jonah Ostroff 2009-12-24T15:39:55Z 2009-12-24T15:39:55Z <p>Okay, here's a less contrived example. While minimal edge coverings can be found in polynomial time, finding a minimal <i>hyperedge</i> covering in general (equivalently, set covering) is NP-hard. On the other hand, finding such a covering when one of the hyperedges spans <i>all</i> vertices on the graph is easy: you just use that edge.</p> <p>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.</p> http://mathoverflow.net/questions/9647/hardness-of-combinatorial-optimization-after-adding-one-constraint/9648#9648 Answer by Jonah Ostroff for Hardness of combinatorial optimization after adding one constraint Jonah Ostroff 2009-12-24T01:08:16Z 2009-12-24T01:08:16Z <p>Sure. We'll construct a normally trivial problem that turns into a question of four-coloring when we restrict one parameter.</p> <p>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 <i>is</i> proper, $f$ spits out the reciprocal of the number of colors used.</p> <p>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.</p> http://mathoverflow.net/questions/2888/injective-proof-about-sizes-of-conjugacy-classes-in-s-n Injective proof about sizes of conjugacy classes in S_n Jonah Ostroff 2009-10-27T20:34:03Z 2009-11-03T18:35:14Z <p>It's not hard to count the number of permutations in a given conjugacy class of S<sub>n</sub>. In particular, the number of permutations in S<sub>n</sub> whose cycle decomposition has c<sub>i</sub> i-cycles is n!/(&Pi;<sub>i=1</sub><sup>n</sup> c<sub>i</sub>!i<sup>c<sub>i</sub></sup>). 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 <i>strictly</i> the maximum when n ≥ 3.</p> <p>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<sub>n</sub> into these cycles, which is injective but not surjective (for n ≥ 3) when restricted to every other conjugacy class.</p> http://mathoverflow.net/questions/3653/how-do-i-iterate-over-binary-trees/3702#3702 Answer by Jonah Ostroff for How do I iterate over binary trees? Jonah Ostroff 2009-11-01T20:09:20Z 2009-11-01T20:24:30Z <p>Wait, you mean n+1 labels for the leaves and n labels for the internal nodes, right?</p> <p>Note that such trees are counted by the multinomial coefficient {2n choose 2,2,2,2,...,2} (with n 2s), because their <a href="http://en.wikipedia.org/wiki/Prufer_sequence" rel="nofollow">Prüfer codes</a> are exactly the ones containing 2 of all but one of the b<sub>i</sub>s 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<sub>1</sub>b<sub>1</sub>b<sub>2</sub>b<sub>2</sub>...b<sub>n-1</sub>b<sub>n-1</sub>b<sub>n</sub>b<sub>n</sub>. I'm not a computer scientist, but these are easy enough to loop through, right?</p> <p>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?</p> <p>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<sup>n</sup> ways to pick that. We can incorporate this into our earlier counting method by looking at anagrams of the 2n distinct letters b<sub>1</sub>c<sub>1</sub>b<sub>2</sub>c<sub>2</sub>...b<sub>n-1</sub>c<sub>n-1</sub>b<sub>n</sub>c<sub>n</sub>. (There are, of course, (2n)! of these). Given such an anagram, get a binary tree as follows:</p> <p>First, chop off the last letter, treat the c<sub>i</sub>s as b<sub>i</sub>s, 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<sub>i</sub> came before c<sub>i</sub> in the original string. If so, the child with the smaller label is on the left; otherwise it's on the right.</p> http://mathoverflow.net/questions/2193/variation-on-a-matrix-game Variation on a matrix game Jonah Ostroff 2009-10-23T21:23:23Z 2009-10-30T20:16:51Z <p>The original problem appeared on last year's Putnam exam:</p> <p>"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?"</p> <p>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?</p> <p>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.</p> http://mathoverflow.net/questions/3271/variant-of-binomial-coefficients/3272#3272 Answer by Jonah Ostroff for Variant of binomial coefficients Jonah Ostroff 2009-10-29T15:44:27Z 2009-10-29T15:44:27Z <p>(For simplicity, you probably want the last term in the numerator to be z-k+a, right? That way F<sub>(1,k)</sub>(z)=\binom{z}{k}. I'll pretend that's what you meant.)</p> <p>I haven't come across such polynomials, but they're easily expressed in terms of <a href="http://en.wikipedia.org/wiki/Factorial#Multifactorials" rel="nofollow">multifactorials</a>. Namely,</p> <p>F<sub>(a,k)</sub>(z)=z!<sup>(a)</sup>/[(z-k)!<sup>(a)</sup>k!<sup>(a)</sup>]</p> <p>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.)</p> http://mathoverflow.net/questions/2340/what-is-the-first-interesting-theorem-in-insert-subject-here/2366#2366 Answer by Jonah Ostroff for What is the first interesting theorem in (insert subject here)? Jonah Ostroff 2009-10-24T21:13:54Z 2009-10-24T21:13:54Z <p>Combinatorics: the nth Catalan number is (2n choose n)/(n+1)</p> http://mathoverflow.net/questions/2340/what-is-the-first-interesting-theorem-in-insert-subject-here/2363#2363 Answer by Jonah Ostroff for What is the first interesting theorem in (insert subject here)? Jonah Ostroff 2009-10-24T21:07:21Z 2009-10-24T21:07:21Z <p>Combinatorics: counting the number of derangements of [n].</p> http://mathoverflow.net/questions/2212/can-i-finitely-color-z2-such-that-x-a-and-a-y-are-different-for-every-x-y-a/2228#2228 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? Jonah Ostroff 2009-10-24T00:30:34Z 2009-10-24T00:30:34Z <p>Nope.</p> <p>Suppose this were possible. For z \in Z, let R<sub>z</sub> be the colors that appear in the row {(x,z) : x≠z \in Z}, and let C<sub>z</sub> be the colors that appear in the column {(z,y) : y≠z \in Z}. The coloring condition is that each C<sub>z</sub> and R<sub>z</sub> is disjoint. Since there are finitely many possibilities for each set, find distinct z and z' where R<sub>z</sub> = R<sub>z'</sub>, and C<sub>z</sub> = C<sub>z'</sub>. What color is (z,z')? Well, it's in R<sub>z'</sub> (and not C<sub>z'</sub>), and it's in C<sub>z</sub> (but not R<sub>z</sub>). So it's both in R<sub>z</sub> and not: a contradiction.</p> <p>(Ninja'd. Drat. Well, different proof at least.)</p> http://mathoverflow.net/questions/1947/placing-checkers-with-some-restrictions/2210#2210 Answer by Jonah Ostroff for Placing checkers with some restrictions Jonah Ostroff 2009-10-23T22:52:05Z 2009-10-23T22:52:05Z <p>Comment to Ricky (sorry, can't comment for real just yet): the solutions to your modified problem (<b>exactly</b> -> <b>less than</b>), when read as a sequence of checker positions within the columns, are exactly the <a href="http://www.combinatorics.org/Volume_4/PDF/v4i2r20.pdf" rel="nofollow">parking functions</a>.</p> http://mathoverflow.net/questions/76564/3d-venn-diagrams/76567#76567 Comment by Jonah Ostroff Jonah Ostroff 2011-09-27T22:22:05Z 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. http://mathoverflow.net/questions/70619/stricter-permutation-patterns/70662#70662 Comment by Jonah Ostroff Jonah Ostroff 2011-07-18T21:12:31Z 2011-07-18T21:12:31Z For (2), I've also seen these referred to as &quot;restricted words&quot;. http://mathoverflow.net/questions/70126/gale-ryser-stable-marriage-theorem-can-we-entrust-matchmaking-to-monkeys/70157#70157 Comment by Jonah Ostroff Jonah Ostroff 2011-07-12T17:57:42Z 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. http://mathoverflow.net/questions/66145/pattern-avoiding-permutations-and-zig-zags Comment by Jonah Ostroff Jonah Ostroff 2011-05-27T14:35:09Z 2011-05-27T14:35:09Z Gerry: 132-avoiding permutations are enumerated by the Catalan numbers. http://mathoverflow.net/questions/53132/combinatorial-questions-about-multisets Comment by Jonah Ostroff Jonah Ostroff 2011-01-24T21:54:05Z 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: <a href="http://oeis.org/A000041" rel="nofollow">oeis.org/A000041</a> http://mathoverflow.net/questions/46239/reference-request-on-permutation-factorisations Comment by Jonah Ostroff Jonah Ostroff 2010-11-16T15:11:24Z 2010-11-16T15:11:24Z Have you tried requesting it through Inter-Library Loan at your institution? http://mathoverflow.net/questions/45863/triangulations-of-polyhedra/45865#45865 Comment by Jonah Ostroff Jonah Ostroff 2010-11-12T20:10:08Z 2010-11-12T20:10:08Z Wonderful. Thanks! http://mathoverflow.net/questions/45518/number-of-longest-decreasing-subsequences-and-rsk Comment by Jonah Ostroff Jonah Ostroff 2010-11-10T14:13:36Z 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. http://mathoverflow.net/questions/45260/prime-number-composite Comment by Jonah Ostroff Jonah Ostroff 2010-11-08T04:32:56Z 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. http://mathoverflow.net/questions/44877/are-there-more-connected-or-disconnected-graphs-on-n-vertices/44889#44889 Comment by Jonah Ostroff Jonah Ostroff 2010-11-06T22:37:45Z 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. http://mathoverflow.net/questions/44877/are-there-more-connected-or-disconnected-graphs-on-n-vertices/45029#45029 Comment by Jonah Ostroff Jonah Ostroff 2010-11-06T15:44:21Z 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. http://mathoverflow.net/questions/44877/are-there-more-connected-or-disconnected-graphs-on-n-vertices/44889#44889 Comment by Jonah Ostroff Jonah Ostroff 2010-11-05T14:51:13Z 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. http://mathoverflow.net/questions/44877/are-there-more-connected-or-disconnected-graphs-on-n-vertices/44908#44908 Comment by Jonah Ostroff Jonah Ostroff 2010-11-05T01:39:51Z 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 &quot;yes&quot;. http://mathoverflow.net/questions/44877/are-there-more-connected-or-disconnected-graphs-on-n-vertices/44889#44889 Comment by Jonah Ostroff Jonah Ostroff 2010-11-04T23:04:58Z 2010-11-04T23:04:58Z (Note that this implies the same result for unlabeled graphs, though enumeration is harder.) http://mathoverflow.net/questions/44877/are-there-more-connected-or-disconnected-graphs-on-n-vertices Comment by Jonah Ostroff Jonah Ostroff 2010-11-04T22:55:58Z 2010-11-04T22:55:58Z You mean connected clearly wins out, Thierry? For 4 vertices, 38/64 are connected.