Search Results

The asymptotics for acyclic graphs is not the same as for those that are transitive. The asymptotics for posets is given in D. J. Kleitman and B. L. Rothschild, Trans. Amer. Math. Soc. 205 (1975), 20 …

At MIT all departments have numbers, and math is 18. Last year MIT math majors produced a tee shirt that said ${i\choose 18}$ ("I choose 18") on the front, and on the back $$ \frac{34376687+1499084 …

Consider the monoid $M_k$ in the generators $A_k=\lbrace 0, 01^k, 01^{k+1}, 01^{k+2},...\rbrace$, where $1^r$ denotes a string of $r$ ones. This contains all binary sequences with no strings of 1's of …

I answer the first question in Corollary 4.1 of my paper at http://math.mit.edu/~rstan/pubs/pubfiles/42.pdf. The maximum number of sums that have the same value is the middle coefficient of the $q$-bi …

Information on this question is given in https://arxiv.org/pdf/0802.2550.pdf. In particular, $t(n,k)$ was computed for $k\leq 23$ by Erné and Stege, Ars Combinatoria 40 (1995), 65--88. For $k\leq 5$ w …

A dual order ideal $I$ (that is, if $F\in I$ and $G\supset F$ then $G\in I$) of the lattice $B_n$ of all subsets of $[n]$ is union-closed. The number of them is $2^{\binom{n}{\lfloor n/2\rfloor}(1+o(1 …

If I understand correctly the meaning of minorant and majorant, then the answer is negative. Let $P$ be the poset with vertices $1,\dots,8$ defined by $1<5,6$; $2<6,7$; $3<7,8$; $4<5,8$. Let $Q$ have …

If $f(A)=X$ for some $A$ then $f(X)=X$. Similarly if $f(A)=\emptyset$ then $f(\emptyset)=\emptyset$. Thus we may assume that the restriction $g$ of $f$ to $\overline{X^\ast}:= X^\ast-\lbrace \emptyset …

A related question is to obtain information on f-vectors of pure multicomplexes (or order ideals of monomials). Any restriction on them would also be a restriction for simplicial complexes. For inform …

The Dissertation of Frank Lutz (http://page.math.tu-berlin.de/~lutz/dissertation.ps‎) has examples of Cohen-Macaulay vertex-transitive simplicial complexes that are not shellable. In particular, there …

Define $i_m<j_m$ if one of the conditions is $\sigma(i_m)<\sigma(j_m)$. If the conditions are consistent, then this relation defines a partially ordered set $P$, and you are asking for the number of l …

One can give a generating function for the number $f_n(k)$ of $n$-tuples $(X_1,\dots, X_n)$ of subsets of $\{1,2,\dots,k\}$ such that if $Y_j=X_1\cup X_2\cup \cdots\cup X_j$, then the $Y_j$'s are stri …

Assume without loss of generality that $b\leq n/2$. Writing $f(x)=(1-x^2)^b(1+x)^{n-2b}$ shows that an upper bound is $2^{n-b}$, but this is very crude.

I prefer to write $K_{\lambda/\nu,\mu}$ for $K^\nu_{\lambda,\mu}$. Using standard symmetric function notation, we have $$ K_{\lambda/\nu,\mu}=\langle s_{\lambda/\nu},h_\mu\rangle = \langle s_\ …

There is a formula for the number of components which unfortunately is pretty useless, namely, $$ \sum_{k,r} \frac{(-1)^{n+k+r}}{k!}f(k,n,r), $$ where $f(k,n,r)$ is the number of real $k\times n$ $ …