User vasu vineet - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T00:30:38Z http://mathoverflow.net/feeds/user/10335 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/122373/box-removing-operators-on-partitions Box removing operators on partitions Vasu vineet 2013-02-20T03:43:18Z 2013-02-23T01:54:38Z <p>Consider the box removing operators $d_i$ for $i\geq 1$ defined as follows.</p> <p>Let $\lambda$ be a partitions. Then $d_i(\lambda)$ is the partition obtained by removing a box from a part of length $i$ in $\lambda$ so as to obtain another partition. (Here removing a box is an operation performed on the Ferrers diagram of $\lambda$.) If there is no part of length $i$ in $\lambda$, then $d_i(\lambda)=0$. (As pointed out by Darij in the comments below, $0$ is not to be confused with the empty partition $\varnothing$.)</p> <p>It is easy to see that the following equalities are satisfied. $$d_id_j=d_jd_i \text{ if } \lvert i-j \rvert\geq 2$$ $$d_id_{i+1}d_i=d_id_id_{i+1}$$ $$d_id_{i+1}d_{i+1}=d_{i+1}d_id_{i+1}$$ </p> <p>Now consider words in the $d_i$. Two words $w_1$ and $w_2$ are called equivalent if $w_1(\lambda)=w_2(\lambda)$ for all partitions $\lambda$.</p> <p>Is it true that if $w_1, w_2$ are equivalent then one can be obtained from the other by using the 3 relations mentioned above? </p> http://mathoverflow.net/questions/100488/bijection-between-saturated-chains-in-youngs-lattice-and-syts-using-jeu-de-taquin Bijection between saturated chains in Youngs lattice and SYTs using jeu-de-taquin Vasu vineet 2012-06-23T21:45:26Z 2012-06-24T12:38:37Z <p>Consider the following saturated chain in the Young's Lattice: $$\phi \subset \lambda^{1}\subset \lambda^{2}\subset \cdots \subset\lambda^{n}$$ where $\phi$ is the empty partition and $\lambda^{i}$ is a partition of $i$, denoted $\lambda^{i} \vdash i$, for $i=1,2,\ldots ,n$.</p> <p>I am going to consider the Ferrers diagram of partitions in French notation, and reference the cells of the Ferrers diagram by the pair (row,column).</p> <p>With the aforementioned saturated chain, associate a column growth word $w=w_1w_2\ldots w_n$ in the following manner: $$w_i= \text{ column of the cell } \lambda^{i}/\lambda^{i-1}$$ Starting from the empty tableau, do jeu-de-taquin slides starting from the outer corner as given by the word $w$ to recover a standard Young tableau(SYT) of shape $\lambda^{n}$. This gives one a(nother) bijection between saturated chains in Young's Lattice and SYTs.</p> <p>$\textbf{Question}$: Is it possible to predict what the SYT associated with a saturated chain will be, just by the knowing the column growth word, so as to avoid making $n$ jeu-de-taquin slides? </p> <p>What follows is what I have been doing. I would like a reference where this has already been dealt with, or is implicit (since I am pretty sure this has to be in the literature somewhere).</p> <p>1) Reverse the word $w$ to obtain $w^r$.</p> <p>2) Standardise the word $w^r$ to obtain a permutation $\pi$.</p> <p>3) $\pi \longleftrightarrow (P,Q)$ via the RSK correspondence.</p> <p>4) $Q^{t}$ (the transpose of the tableau, that is) is the SYT we are looking for.</p> <p>Example for making the notation clear: Consider the maximal chain $\phi \subset (1)\subset (1,1)\subset (2,1)\subset (2,1,1)\subset (2,2,1)$. Then the column growth word associated with this chain is $w=11212$. Then $w^r=21211$ and the standardisation gives the permutation $41523$ in single line notation.</p> http://mathoverflow.net/questions/70203/a-bijection-between-sets-of-young-tableaux-of-two-kinds A bijection between sets of Young tableaux of two kinds Vasu vineet 2011-07-13T06:25:50Z 2011-07-18T22:41:47Z <p>Assuming that the problem of exhibiting a bijection is not considerd a frivolous pursuit, allow me to ask a question troubling me for some time now.</p> <p>Let $\lambda \vdash n$ denote the fact that $\lambda$ is a partition of $n$. Denote the number of parts by $l(\lambda)$. If $T$ is a standard Young tableau (SYT), we will denote the underlying partition shape by $sh(T)$.</p> <p>Given a positive even integer $2n$, let $$Pe_{2n}=\{ \lambda: \lambda\vdash 2n,\text{ } l(\lambda) \leq3 \text{ and all parts of } \lambda \text{ are even} \}$$ and $$Qe_{2n}=\{ \lambda: \lambda\vdash 2n, \lambda = (k,k,1^{2n-2k}), \text{ }k\geq 1 \}$$</p> <p>Using these sets we will define two more sets whose elements are SYTs. $$TPe_{2n}=\{T: T \text{ an SYT, } sh(T)\in Pe_{2n} \}$$ and $$TQe_{2n}=\{T: T \text{ an SYT, } sh(T)\in Qe_{2n} \}$$</p> <p>$\textbf{Question}$: Is there a bijective proof exhibiting the fact that the cardinalities of $TPe_{2n}$ and $TQe_{2n}$ are equal?</p> <p>The second question is very similar. Given an odd positive integer $2n+1$, let $$Po_{2n+1}=\{ \lambda: \lambda\vdash 2n+1,\text{ } l(\lambda)=3 \text{ and all parts of } \lambda \text{ are odd} \}$$ and $$Qo_{2n+1}=\{ \lambda: \lambda\vdash 2n+1, \lambda = (k,k,1^{2n+1-2k}), \text{ }k\geq 1 \}$$</p> <p>Using these sets we will define two more sets whose elements are SYTs. $$TPo_{2n+1}=\{T: T \text{ an SYT, } sh(T)\in Po_{2n+1} \}$$ and $$TQo_{2n+1}=\{T: T \text{ an SYT, } sh(T)\in Qo_{2n+1} \}$$</p> <p>$\textbf{Question}$: Is there a bijective proof exhibiting the fact that the cardinalities of $TPo_{2n+1}$ and $TQo_{2n+1}$ are equal?</p> <p>I tried quite a few approaches ( Motzkin path interpretations, matching diagrams etc) but did not succeed. I hope somebody here can guide me.</p> <p>The relevant OEIS entry would be <a href="http://oeis.org/A005043" rel="nofollow">link text</a></p> <p>Thanks,</p> <p>Vasu</p> http://mathoverflow.net/questions/44048/lattice-walks-and-a-q-series-curiosity Lattice walks and a q-series curiosity Vasu vineet 2010-10-29T03:20:16Z 2011-01-06T11:17:38Z <p>I had been fiddling around with a particular expression over the summer. Since I haven't had much luck with it, I thought it was about time I took an opinion over the question.</p> <p>So here's where it all began. Consider the hexagonal lattice (also called the equilateral triangular lattice). Fix some point $P$ on the lattice to be the origin. Let $W_{n}$ be the number of walks of length $n$ which start and end at $P$. I was considering the simplest possible model, so there are no constraints (meaning no self-avoidance condition or anything of that sort). In trying to enumerate these walks, I came up with this 'cute' little identity </p> <p>$$\displaystyle\sum_{j=0}^{n}\binom{n}{j}^{3} = \sum_{j=0}^{n}\binom{n}{j}2^{j}\times W_{n-j}$$ We have the initial constraints being $W_{0}=1$, $W_{1}=0$.</p> <p>Next I tried to tweak out a q-deformation of this particular identity. Combinatory-wise I haven't got anything particularly exciting. But here is the q-version I am considering. The binomial coefficients are replaced with the q-binomial coefficients. Fix an integer $k$. Define $$2_{k}^{j} = \prod_{i=1}^{j} (1+q^{k+i})$$ with the norm that $2^{0}=1$. Now this allows one to obtain polynomials $W_{n,k}(q)$ recursively from the identity above with the initial conditions $W_{0}=1$, $W_{1}=0$. They don't necessarily have positive coefficients but as $n$ gets large, they do. Though one does obtain interesting polynomials for $k=-1,0$, here's the one I'll mention. As $k,n$ become large, one notices (formally) $$W_{n,k}(q)\rightarrow\prod_{i=1}^{\infty} \frac{1}{(1-q^i)^2}$$</p> <p>Is there a good reason? I have a feeling my setup is slightly artificial, but I'd love to know what's happening!</p> <p>Edit dated 6th Jan'2011:</p> <p>$$W_{n}=\displaystyle\sum_{i=0}^{n} (-2)^{n-i}\binom{n}{i}(\displaystyle\sum_{j=0}^{i} \binom{i}{j}^3)$$</p> http://mathoverflow.net/questions/47070/enumeration-of-standard-young-tableau-of-bounded-height Enumeration of Standard Young Tableau of bounded height Vasu vineet 2010-11-23T08:15:32Z 2010-11-23T08:15:32Z <p>First for some notation $$l(\lambda) = \text{ number of parts in a partition } \lambda \vdash n$$</p> <p>$$f_{\lambda} = \text{number of standard Young tableau of shape } \lambda\vdash n$$</p> <p>The number $f_{\lambda}$ is given by the hook length formula and might not acquire a "nice form". Given an integer $k$ consider the problem of computing $$\tau_{k}(n) = \displaystyle\sum_{\lambda\vdash n \text{, } l(\lambda)\leq k}f_{\lambda}$$</p> <p>Contrary to expectation, relatively neat closed forms are known for $\tau_{2}(n)$, $\tau_{3}(n)$ and $\tau_{4}(n)$. Gessel <a href="http://people.brandeis.edu/~gessel/homepage/papers/dfin.pdf" rel="nofollow">link text</a> proved the following $$\tau_{2}(n) = \binom{n}{\lfloor \frac{n}{2} \rfloor}$$ $$\tau_{3}(n) = M_{n}$$ $$\tau_{4}(n) = C_{\lfloor \frac{n+1}{2} \rfloor}C_{\lceil \frac{n+1}{2} \rceil}$$ where $M_{n}$ denotes the n'th Motzkin number <a href="http://oeis.org/A001006" rel="nofollow">link text</a> and $C_{n}$ denotes the n'th Catalan number <a href="http://oeis.org/A000108" rel="nofollow">link text</a></p> <p>(Here both sequences are indexed starting 0)</p> <p>(Aside: Proving the first two identities bijectively is a cute exercise in my opinion.)</p> <p>As a by-product of my research I obtained the following identity $$\displaystyle\sum_{\lambda\vdash n, l(\lambda)=5,\lambda_{5}=1}f_{\lambda} = \displaystyle\frac {\lfloor \frac{k+1}{2} \rfloor (\lceil \frac{k+1}{2} \rceil +1)}{k+1}C_{\lfloor \frac{k+1}{2} \rfloor}C_{\lceil \frac{k+1}{2} \rceil} - C_{\lfloor \frac{k}{2} \rfloor +1}C_{\lceil \frac{k}{2} \rceil +1}+M_{k}$$ where the sum on the left runs over all partitions $\lambda$ with length exactly 5 and minimum part $\lambda_{5}$ being 1. Admittedly this is very specific but my question is what is known about sums of the above sort </p> <p>a) where the minimum part is fixed and so is the length of the partition ?</p> <p>b) where $l(\lambda) \leq k$ and the k'th part $\lambda_{k} \leq i$ for a fixed non-negative integer $i$?</p> <p>Gessel, I believe, used some really clever symmetric function manipulation to obtain the identities mentioned earlier. I'd appreciate if somebody has seen this stuff elsewhere ( i.e. reference other than Gessel / Gouyou-Beauchamps) and directs me. Thanks!</p> http://mathoverflow.net/questions/45518/number-of-longest-decreasing-subsequences-and-rsk Number of Longest Decreasing subsequences and RSK Vasu vineet 2010-11-10T04:48:28Z 2010-11-11T02:32:29Z <p>It is well known via the RSK-correspondence that the length of the longest decreasing subsequence in a permutation $\pi \in S_n$ is the length of the longest column of the insertion tableau of $\pi$. ( The insertion tableau and the recording tableau produced by this algorithm have the same shape)</p> <p><a href="http://en.wikipedia.org/wiki/Robinson%25E2%2580%2593Schensted_algorithm" rel="nofollow">link text</a></p> <p>My question is what else can be gleaned from the RSK correspondence in terms of ,say,</p> <p>a) the length of the next longest decreasing subsequence in $\pi$ ?</p> <p>b) the number of longest decreasing subsequences in $\pi$, given the fact that there is exactly one column of maximum length ?</p> <p>c) can we say more about the above two questions if we knew that $\pi$ was an involution? (If $\pi$ happens to be an involution, then insertion tableau and recording tableau produced are equal)</p> http://mathoverflow.net/questions/43638/a-distinct-parts-odd-parts-identity-for-standard-young-tableaux A Distinct parts/Odd parts identity for standard Young tableaux Vasu vineet 2010-10-26T06:43:37Z 2010-10-30T01:16:10Z <p>Let $\lambda$ denote a partition of size $n$. Let $$d_{\lambda}= \text{number of distinct parts of } \lambda$$ $$o_{\lambda}= \text{number of odd parts of } \lambda$$ $$f_{\lambda}= \text{number of standard Young tableau of shape } \lambda$$ Given an involution $\pi \in S_{n}$, whose insertion tableau has shape $\lambda$, it is well known (via the Robinson-Schensted correspondence, and neatly outlined in Sagan's book on the Symmetric Group) that : $$o_{\lambda^{t}}= \text{number of fixed points in the involution } \pi$$ $$\sum_{\lambda \vdash n} f_{\lambda}= \text{number of involutions in } S_{n}$$</p> <p>In the aforementioned formulae, $\lambda^{t}$ refers to the conjugate of the partition $\lambda$. Now, some computations I have carried out for Kronecker products of two irreducible characters of $S_{n}$ revealed the following identity in a special case: $$\sum_{\lambda \vdash n}d_{\lambda}f_{\lambda}=\sum_{\lambda \vdash n}o_{\lambda}f_{\lambda}$$</p> <p>Note that the right hand side actually counts the total number of fixed points in all involutions in $S_{n}$. I did manage to prove the above result in general, but I am hoping someone could guide me to a proof which is bijective, i.e say uses the RS correspondence to establish the left hand side equals the the total number of fixed points in all involutions in $S_{n}$.</p> <p>Also, I'd like it if I could be directed to where this and/or similar sums appeared.(as an exercise in a book, or in some paper).</p> <p>Thanks!</p> <p>Edit: I had a look at Sagan, which I did not have handy last night and made a minor change in saying the number of fixed points in an involution $\pi \in S_{n}$ is the number of odd columns in the insertion tableau of $\pi$.</p> <p>Edit(10/27):</p> <p>I thought I should put down the idea that I had. But since I am not sure if this should count as an answer, I am putting it in the body of the question. Note that $$\sum_{\lambda \vdash n}d_{\lambda}f_{\lambda}=\sum_{\lambda \vdash n+1}f_{\lambda}-\sum_{\lambda \vdash n}f_{\lambda}$$ So all that remains to be shown is the nice fact that the total number of fixed points in all the involutions of $S_{n}$ is the difference between the number of involutions in $S_{n+1}$ and the number of involutions in $S_{n}$. </p> http://mathoverflow.net/questions/128891/what-does-the-q-catalan-numbers-count Comment by Vasu vineet Vasu vineet 2013-04-27T06:58:04Z 2013-04-27T06:58:04Z and I don't think there is such a thing as 'the' q-analog http://mathoverflow.net/questions/127398/distinct-odd-part-partitions-and-symmetric-partitions Comment by Vasu vineet Vasu vineet 2013-04-12T18:59:28Z 2013-04-12T18:59:28Z I imagine this might get closed. But here's a hint to get you started anyway: every part of odd length can be 'bent' into a hook shape that is symmetric. http://mathoverflow.net/questions/122373/box-removing-operators-on-partitions/122440#122440 Comment by Vasu vineet Vasu vineet 2013-02-21T20:14:15Z 2013-02-21T20:14:15Z Thank you for the answer. Let me see if I can push the idea here in the general case. http://mathoverflow.net/questions/122373/box-removing-operators-on-partitions/122453#122453 Comment by Vasu vineet Vasu vineet 2013-02-20T23:08:13Z 2013-02-20T23:08:13Z Here is the reference of Fomin-Greene that I am talking about (example 2.6 specifically) <a href="http://www.math.lsa.umich.edu/~fomin/Papers/ncschur.ps" rel="nofollow">math.lsa.umich.edu/~fomin/Papers/ncschur.ps</a> http://mathoverflow.net/questions/122373/box-removing-operators-on-partitions/122453#122453 Comment by Vasu vineet Vasu vineet 2013-02-20T23:07:34Z 2013-02-20T23:07:34Z Thanks for the answer and the link to Garsia's paper. But I do believe there is a lot more going on here than the case you mention, and I disagree that these are the Coxeter-Knuth relations. I checked a paper of Fomin's that defines the adjoint of the operators that I am considering, calling them Schur operators (or box adding operators if you will). He further goes on to say that the complete list of relations between the Schur operators is not known. http://mathoverflow.net/questions/122373/box-removing-operators-on-partitions Comment by Vasu vineet Vasu vineet 2013-02-20T05:45:17Z 2013-02-20T05:45:17Z If you check the relations that I gave, then they already list some words that are equivalent. For example, $d_1d_3$ and $d_3d_1$ are equivalent words because either both act on a partition to give $0$ or the same partition. Hope this clarifies. http://mathoverflow.net/questions/122373/box-removing-operators-on-partitions Comment by Vasu vineet Vasu vineet 2013-02-20T04:17:02Z 2013-02-20T04:17:02Z Sorry, I should have mentioned that. I will edit the question. Thanks http://mathoverflow.net/questions/108890/tensor-powers-of-the-standard-representation Comment by Vasu vineet Vasu vineet 2012-10-05T17:41:18Z 2012-10-05T17:41:18Z I think a combinatorial model for the case at hand is dealt with in <a href="http://www.emis.de/journals/SLC/wpapers/s54goupchau.html" rel="nofollow">emis.de/journals/SLC/wpapers/s54goupchau.html</a> http://mathoverflow.net/questions/100488/bijection-between-saturated-chains-in-youngs-lattice-and-syts-using-jeu-de-taquin/100524#100524 Comment by Vasu vineet Vasu vineet 2012-06-25T06:46:30Z 2012-06-25T06:46:30Z Thanks for the reference, Prof. Stanley. Let me look at the paper in detail before I accept the answer. From a first glance, surely the paper seems to be doing the sort of thing I want. http://mathoverflow.net/questions/24645/does-the-property-xyx-xy-have-a-name Comment by Vasu vineet Vasu vineet 2011-12-26T15:28:05Z 2011-12-26T15:28:05Z I have seen people dealing with Left Regular Bands call this 'left regularity'. I might be mistaken. http://mathoverflow.net/questions/81473/higher-dimensional-catalan-numbers/81562#81562 Comment by Vasu vineet Vasu vineet 2011-11-22T05:52:29Z 2011-11-22T05:52:29Z This paper discusses a related problem (Generalized ballot problem): <a href="http://thales.math.uqam.ca/~serrano/paths.pdf" rel="nofollow">thales.math.uqam.ca/~serrano/paths.pdf</a> http://mathoverflow.net/questions/81024/taylor-expansion-of-a-q-analog-of-the-negative-binomial-distribution Comment by Vasu vineet Vasu vineet 2011-11-16T01:48:42Z 2011-11-16T01:48:42Z Okay, I see the question got answered! http://mathoverflow.net/questions/81024/taylor-expansion-of-a-q-analog-of-the-negative-binomial-distribution Comment by Vasu vineet Vasu vineet 2011-11-16T01:47:24Z 2011-11-16T01:47:24Z Not sure if this helps but in the case where A and B are equal then one can put $x_i=\sqrt{t}q^j$, $y_j=\sqrt{t}q^j$ and the expression looks like the Cauchy determinant, and can be expanded as sum of product of Schur functions. Then you are trying to compute a specialization of Schur functions labeled by a partition $\lambda$ with the alphabets being $\sqrt{t}q^i$. The quotient of alternants formula for Schur function might come handy. http://mathoverflow.net/questions/70203/a-bijection-between-sets-of-young-tableaux-of-two-kinds Comment by Vasu vineet Vasu vineet 2011-09-10T06:55:24Z 2011-09-10T06:55:24Z @Gjergji : Could you please tell me what are the values for $TP_{10}$ and $TQ_{10}$ that you obtained? Thanks. http://mathoverflow.net/questions/70203/a-bijection-between-sets-of-young-tableaux-of-two-kinds Comment by Vasu vineet Vasu vineet 2011-09-03T19:28:23Z 2011-09-03T19:28:23Z I seem to be getting 13393689 for the both of them. I will look into my code to see if I am bungling up somewhere.