Groups Acting on Posets

From TedYunWiki
Revision as of 21:19, 3 December 2012 by Tedyun (talk | contribs) (Created page with "$S_n$ acting on the partition lattice $\pi_n$. The number of orbits are $A_{n-1}$, the Euler number. Questions: * Find $\beta_S(n)$ for the $S_n$-"quotient" poset of $\pi_n$ ...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

$S_n$ acting on the partition lattice $\pi_n$. The number of orbits are $A_{n-1}$, the Euler number.

Questions:

  • Find $\beta_S(n)$ for the $S_n$-"quotient" poset of $\pi_n$ and thereby get a refinement of $A_n$
  • According to "On Flag Vectors, the Dowling Lattice, and Braid Arrangements" (Ehrenborg & Readdy) it is well known that the face lattice of the permutahedron is given by the dual poset of $R_{n,1}$, the lattice of regions of the Dowling arrangement $\mathcal{H}_{n,1}$. Then, the dual of $R_{n,k}$ corresponds to the face lattice of generalized permutahedron?

More explicitly, define the "generalized" permutohedron $P_{n,q}$ to be the convex hull of $(\zeta^{i_1}\pi(1), \zeta^{i_2}\pi(2), \ldots, \zeta^{i_n}\pi(n))$, for $\pi\in S_n$, $1\leq i_j\leq q$ where $\zeta$ is the primitive $q$-th root of unity.

  • In general, for a subgroup $G$ of $Aut(P)$, is there a induced subposet $Q$ of $P$ such that $Q \cong P/G$?

Quotine Posets of Intersection Lattices of Hyperplane Arrangement

Type B

  • Subspace arrangements of type Bn and Dn - Anders Björner and Bruce E. Sagan

http://www.springerlink.com/content/35v1rmw0p5m56275/fulltext.pdf

  • Intersection lattices of type B, D Coxeter arrangements are studied by Zaslavsky in terms of "singed graphs"

The Geometry of Root Systems and Signed Graphs - Zaslavsky http://ftp.math.binghamton.edu/zaslav/Tpapers/grs.amm1981.pdf
Signed Graphs http://www.sciencedirect.com/science?_ob=MiamiImageURL&_cid=271602&_user=501045&_pii=0166218X82900336&_check=y&_origin=&_coverDate=31-Jan-1982&view=c&wchp=dGLbVlV-zSkzV&md5=03d5d2d55e61f1f213a285cd79fe5eb8/1-s2.0-0166218X82900336-main.pdf

  1. Q. Is it the same as Dowling lattice of $Z_2$? YES!
  2. Type B Euler number: http://oeis.org/A001586 http://iopscience.iop.org/0036-0279/47/1/R01/pdf/RMS_47_1_R01.pdf
  3. Labeled Ballot Paths and the Springer Numbers - William Y.C. Chen, Neil J.Y. Fan, Jeffrey Y.T. Jia http://arxiv.org/abs/1009.2233

The Springer numbers are defined in connection with the irreducible root systems of type $B_n$, which also arise as the generalized Euler and class numbers introduced by Shanks. Combinatorial interpretations of the Springer numbers have been found by Purtill in terms of Andre signed permutations, and by Arnol'd in terms of snakes of type $B_n$. We introduce the inversion code of a snake of type $B_n$ and establish a bijection between labeled ballot paths of length n and snakes of type $B_n$. Moreover, we obtain the bivariate generating function for the number B(n,k) of labeled ballot paths starting at (0,0) and ending at (n,k). Using our bijection, we find a statistic $\alpha$ such that the number of snakes $\pi$ of type $B_n$ with $\alpha(\pi)=k$ equals B(n,k). We also show that our bijection specializes to a bijection between labeled Dyck paths of length 2n and alternating permutations on [2n].

Quotient Posets induced by the Group Action (on pause due to counterexample)

$P$ a poset, $G \subset Aut(P)$, write $Q := P//G$, if Q is an induced subposet of P and each maximal chain of $Q$ represents each of G-orbits of maximal chains of $P$. Call $Q$ is a $M$-quotient of P w.r.t. the $G$-action. In terms of simplicial complexes, $\Delta(Q)$ is a simplicial complex whose vertex set is a subset of the vertex set of $\Delta(P)$ and its facets represents each and every orbit of facets of $\Delta(P)$ under some automorphism group $G$.

  1. Does $P//G$ always exist for every (finite) poset $P$? When $G = Aut(P)$?
    • Probably yes.
  2. When it exists, is it ranked?
    • Yes.
  3. Is $M$-quotient unique?
    • No, it is not unique for general $G$. Let $P$ be a "complete" poset of rank sequence $(1,2,2,1)$, and $G = \{id,g\}$ where $g$ maps each elements in rank $i$ to the other element of rank $i$ when $i = 1,2$. Then there are two $P//G$ with rank sequence $(1,2,1,1)$ and $(1,1,2,1)$.
    1. Is it unique when $G$ is the full automorphism group $Aut(P)$?
      • No. Counterexample from Maple.
    2. Is it unique UP TO some action?.
    3. Is the cardinality of $P//G$ unique?
    4. Is the comparability graph of $P//G$ unique?
      • No. Counterexample from Maple.
    5. If the cardinality is unique, can you write it in terms of some statistics of $P$ and $G$?
  4. What properties of $P$ convey to $P//G$? e.g. if $P$ is shellable, is $P//G$ shellable?
  5. When $P = J(P')$ i.e. distributive lattice, anything interesting happens?
    • Conjecture. When $P$ is distributive, $P//Aut(P)$ is also distributive. Checked by maple for some random posets. (Note that when $P$ is ranked, $J(P//G) \neq J(P)//G$ in general).

Proposition. (?) $P//G$ exists if and only if one can pick representatives $C_1, C_2, \ldots, C_n$ of the orbits of maximal chains of $P$ (under $G$-action) such that if $x\succ y$ (or $x > y$) in $C_1\cup \cdots \cup C_n$, then there exists $i$ such that $\{x,y\}\subset C_i$.

Want:. For $P$ and $G = Aut(P)$, there always exists $P//G$ as a subposet of $P$.
PROOF IDEA:

  1. Pick orbit representatives $C_1, \ldots, C_l$ such that the cardinality of $C_1\cup \cdots \cup C_l$ is minimal among any union $C_1'\cup \cdots \cup C_l'$ of orbit representatives of maximal chains. (This does not hold for general poset! Counterexample by maple. Probably for lattices??)
  2. Start with proving the theorem for rank 2 posets.
    1. In rank 2 case, conjecture that if a and b is identified under an isomorphism only one of a,b is in the quotient.
  3. The subposet of representatives of minimal cardinality is NOT unique. The counterexample is the poset constructed from a graph whose automorphism group is $C_3$ and has one invariant vertex in the center.

Dowling Lattices and the Symmetric Groups Action

Let $L_{n,q}$ be the Dowling lattice, which is a generaliztion of $\pi_{n+1}$. $E_{n,q}$ be the number of orbits of the obvious symmetric groups action on $L_{n,q}$, i.e. $E_{n,q}$ is the number of maximal chains of $L_{n,q}/_M S_n$.

Proposition. The total number $c_{n,q}$ of chains in $L_{n,q}$ is $c_{n,q} = \prod_{k=1}^n \frac{k(qk+2-q)}{2}$. In particular, $c_{n,2} = \prod_{k=1}^n k^2$.

For Whitney numbers of Dowling lattices: See On Whitney numbers of Dowling lattices http://www.sciencedirect.com/science/article/pii/0012365X9500095E

Numerical results on $q = 2$ i.e. type B intersection lattice

$E_{n,q}$ n = 1 2 3 4 5 6 7
$q = 1$ 1 2 5 16 61 272 #alternating permutation on $n+1$-letters,
$q = 2$ 1 3 10 48 274 1902 #not in OEIS

Numerical results on $q = 2$ i.e. type B intersection lattice, and the group is the whole hyperoctahedral group

$E_{n,q}$ n = 1 2 3 4 5 6 7
$q = 2$ 1 2 5 16 61 #alternating permutation

Numberical results on $L_{3,2}$

$L_{3,2}$ has 24 elements (http://oeis.org/search?q=dowling+lattice&language=english&go=Search) and 36 chains. $L_{3,2}//S_3$ has 14 elements, 10 chains.

$L_{n,1}$

Let $Q$ be an induce subposet of $L_{n,1}$ consisting of elements satisfying:

  1. If $i+1$ is in a non-singleton block or in a zero set, then $i$ is also in a non-singleton block or in a zero set.
  2. If $i$ is the least element of a non-singleton block, then $i+1$ is also in that block.

Then, $Q \cong L_{n,1}// S_n \cong (\pi_{n+2}// S_{n+2})\setminus \hat{0}$.

Exponential Dowling Structures

Ehrenborg & Readdy, "Exponential Dowling Structures", http://www.sciencedirect.com/science/article/pii/S0195669808000620

Other Aspects

  • The representation of $S_n$ on the homology of the partition lattice $\pi_n$ is isomorphic to the representation of $S_n$ on a multilinear component of the free Lie algebra on $[n]$ tensored with the sign representation.

Gottlieb and Wachs generalized this to Dowling lattices: as an $G \wr S_n$-module, the cohomology of $L_{n,G}$ is isomorphic to a multilinear component of the enveloping algebra of a certain Lie algebra tensored with a sign representation.

  • The total number of maximal chains in $L_{n,q}$ is...
  • What is the property that $\pi_n$ has, and $L_{n,q}$ doesn't have in general??
  • Should I consider $S_n$ action or $G\wr S_n$ action on Dowling lattices?
  • The homology of the partition lattice has been extensively studied in order to find representations of the symmetric group. Wachs has studied the signed partition lattice $L_{n,2}$. What can be said about the representations of the symmetric group arising from the Dowling lattice $L_{n,k}$? A related question: find an explicit basis for the highest homology group of the Dowling lattice.
Retrieved from "https://wiki.tedyun.com/index.php?title=Groups_Acting_on_Posets&oldid=10"