Improve this page

See the cyclic sieving phenomenon page for the definition and related theorems.

#Matchings and crossings

#Polygon dissections with \(k\) edges

In [RSW04], the authors consider dissections of polygons with \(k\) non-crossing edges, where each edge connects two vertices, \(X_{n,k}.\) Let \(\grpc_{n}\) act by rotation. This gives the CSP-triple \[\left( X_{n,k}, \grpc_{n}, \frac{1}{[n+k]_q}\qbinom{n+k}{k+1}_q \qbinom{n-3}{k}_q \right).\] This can also be turned into a CSP on the set \(\SYT((k+1)^2 1^{n-k-3}),\) but it is not explained what the corresponding group action is.

See also [BR14] for some related results.

#Matchings with \(k\) crossings

In [LB17], matchings on \([2n]\) with \(k\) crossings are studied. Let \(X_{n,k}\) be the set of such matchings, and let \(\grpc_{2n}\) act on such matchings via rotation. The case \(k=0\) corresponds to the Catalan case. For \(k=1,2,3\) they prove the following instances of cyclic sieving:

\[\left( X_{n,1}, \grpc_{2n}, \qbinom{2n}{n-2}_q \right) , \quad \left( X_{n,2}, \grpc_{2n}, \frac{[n+3]_q}{[2]_q} \qbinom{2n}{n-3}_q \right)\] and \[\left( X_{n,3}, \grpc_{2n}, \frac{1}{[3]_q} \qbinom{n+5}{2}_q \qbinom{2n}{n-4}_q + \qbinom{2n}{n-3}_q \right).\]

Problem

Find a cyclic sieving phenomenon on matchings with more than \(3\) crossings.

#Annular non-crossing permutations

Let \(\pi\) be a permutation on \([n]\) and draw the directed edges \(i\to \pi(i)\) on a circle with vertices \(1,\dotsc,n\) on the boundary. If all edges are non-crossing, and all cycles are oriented clockwise, we say that \(\pi\) is a non-crossing permutation. Such permutations are in natural bijection with Catalan objects.

In [Kim13], a generalization of non-crossing permutations is studied. Instead of a circle, one chooses \(n\) and \(m\) and places exterior vertices \(1,\dotsc,n\) on a circle clockwise, and interior vertices \(n+1,\dotsc,n+m\) counter-clockwise on an interior circle.

A permutation is \((n,m)\)-non-crossing if one can draw the edges as before in a non-crossing manner, such that every cycle is oriented clockwise. A non-crossing permutation is called connected if it contains at least one cycle with both exterior and interior vertices. The paper [Kim13] only considers non-crossing permutations with at least one connected cycle. Let \(ANC(n,m)\) denote the set of connected \((n,m)\)-non-crossing permutations.

Let \(C\) act on the annulus by rotation, where the order of \(C\) is \(\gcd(m,n).\) Then \[\left( ANC(n,m), C, \frac{[2nm]_q}{[n+m]_q}\qbinom{2n-1}{n}_q\qbinom{2m-1}{m}_q \right)\] is a CSP-triple.

Several refinements, such as the \(q\)-Narayana and \(q\)-Kreweras polynomials are also considered in [Kim13] and proved to have CSP. The type \(B\) variants, where all non-crossing partitions are symmetric with respect to rotation by half a turn, are also covered. For example, \[\left( ANC_B(n,m), C, \frac{[2nm]_q}{[n+m]_q}\qbinom{2n}{n}_q\qbinom{2m}{m}_q \right)\] is a CSP-triple.

#Non-crossing trees, forests and graphs

S. Kluge proves the cyclic sieving phenomenon for non-crossing forests, confirming a conjecture of A. Guo [Klu12]. Let \(X_{n,k}\) be the set of non-crossing forests with \(n\) vertices and \(k\) components. These are forests drawn with vertices on a circle and edges inside, such that edges do not cross.

Let \[f_{n,k}(q) \coloneqq \frac{1}{[2n-k]_q} \qbinom{n}{k-1}_q \qbinom{3n-2k-1}{n-k}_q,\] and let \(\grpc_n\) act on \(X_{n,k}\) by \(2\pi/n\) rotation. Then \((X_{n,k},\grpc_n,f_{n,k}(q))\) is a CSP triple. This is also proved in [Poz11].

We can also count graphs according to edges. In [Poz11], the following \(q\)-analog is considered, which enumerates the number of non-crossing graphs with \(n\) vertices and \(k\) edges, \(Y_{n,k}:\) \[g_{n,k}(q) \coloneqq \frac{1}{[n-1]_q} \sum_{j=0}^{n-2} q^{j(j+n-k+2)}\qbinom{n-1}{k-j}_q \qbinom{n-1}{j+1}_q \qbinom{n-2+j}{n-2}_q.\] Then \((Y_{n,k},\grpc_n,g_{n,k}(q))\) is a CSP-triple, under rotation.

Bibliography

  1. [BR14]Douglas Bowman and Alon Regev. Counting symmetry classes of dissections of a convex regular polygon. Advances in Applied Mathematics, 56:35–55, May 2014.
    .bib
    @article{BowmanRegev2014,
  doi = {10.1016/j.aam.2014.01.004},
  url2 = {https://doi.org/10.1016/j.aam.2014.01.004},
  year = {2014},
  month = may,
  publisher = {Elsevier {BV}},
  volume = {56},
  pages = {35--55},
  author = {Douglas Bowman and Alon Regev},
  title = {Counting symmetry classes of dissections of a convex regular polygon},
  journal = {Advances in Applied Mathematics}
}
  2. [Kim13]Jang Soo Kim. Cyclic sieving phenomena on annular noncrossing permutations. Séminaire Lotharingien de Combinatoire, 69(B69b), 2013.
    .bib
    @article{Kim2013,
author = {Jang Soo Kim},
journal = {S{\'{e}}minaire Lotharingien de Combinatoire},
language = {eng},
number = {B69b},
publisher = {Universit{\"{a}}t Wien, Fakult{\"{a}}t f{\"{u}}r Mathematik},
title = {Cyclic Sieving Phenomena on Annular Noncrossing Permutations},
url = {https://www.emis.de/journals/SLC/wpapers/s69kim.html},
volume = {69},
year = {2013}
}
  3. [Klu12]Stefan Kluge. The cyclic sieving phenomenon for non-crossing forests. The Electronic Journal of Combinatorics, 19(3), July 2012.
    .bib
    @article{Kluge2012,
  doi = {10.37236/2419},
  url2 = {https://doi.org/10.37236/2419},
  year = {2012},
  month = jul,
  publisher = {The Electronic Journal of Combinatorics},
  volume = {19},
  number = {3},
  author = {Stefan Kluge},
  title = {The Cyclic Sieving Phenomenon for Non-Crossing Forests},
  journal = {The Electronic Journal of Combinatorics},
  eprint = {1106.0992}
}
  4. [LB17]Qingzhong Liang and Grant Bowling. Cyclic sieving of matchings. arXiv:1712.07812, 2017.
    .bib
    @article{LiangBowling2017x,
Author = {Qingzhong Liang and Grant Bowling},
Title = {Cyclic Sieving of Matchings},
Year = {2017},
Eprint = {1712.07812},
  url = {https://arxiv.org/abs/1712.07812},
journal = {arXiv e-prints}
}
  5. [Poz11]Svetlana Poznanović. Cyclic sieving for two families of non-crossing graphs. 23th International conference on formal power series and algebraic combinatorics:789–800, 2011.
    .bib
    @inproceedings{Poznanovic2011,
  title = {Cyclic sieving for two families of non-crossing graphs},
  author = {Svetlana Poznanovi{\'{c}}},
  URL = {https://hal.inria.fr/hal-01215075},
  booktitle = {23th {I}nternational Conference on Formal Power Series and Algebraic Combinatorics},
  venue = {Reykjavik},
  EDITOR = {Mireille Bousquet-M{\'{e}}lou  and Michelle Wachs  and Axel Hultman},
  publisher = {Discrete Mathematics and Theoretical Computer Science},
  series = {DMTCS Proceedings},
  pages = {789--800},
  YEAR = {2011}
}
  6. [RSW04]Victor Reiner, Dennis Stanton and Dennis E. White. The cyclic sieving phenomenon. Journal of Combinatorial Theory, Series A, 108(1):17–50, October 2004.
    .bib
    @article{ReinerStantonWhite2004, 
	title={The cyclic sieving phenomenon}, 
	volume={108}, 
	url2={http://dx.doi.org/10.1016/j.jcta.2004.04.009}, 
	DOI={10.1016/j.jcta.2004.04.009}, 
	number={1}, 
	journal={Journal of Combinatorial Theory, Series A}, 
	publisher={Elsevier BV}, 
	author={Victor Reiner and Dennis Stanton and Dennis E. White}, 
	year={2004}, 
	month = oct, 
	pages={17--50}
}

I use cookies to detect website issues and track search terms.