@misc{Postnikov2007, archivePrefix = {arXiv}, author = {Postnikov, Alexander and Speyer, David and Williams, Lauren}, eprint={}, month = jun, pages = {26}, title = {Matching polytopes, toric geometry, and the non-negative part of the Grassmannian}, year = {2007} } @misc{Barkley2019, title={Channels, Billiards, and Perfect Matching 2-Divisibility}, author={G. T. Barkley and R. I. Liu}, year={2019}, eprint={1911.08102}, archivePrefix={arXiv}, primaryClass={math.CO} } @iarticle{Eppstein2018, address = {Phoenix, AZ, USA}, title = {{NC} {Algorithms} for {Computing} a {Perfect} {Matching}, the {Number} of {Perfect} {Matchings}, and a {Maximum} {Flow} in {One}-{Crossing}-{Minor}-{Free} {Graphs}}, isbn = {9781450361842}, opturl = {http://dl.acm.org/citation.cfm?doid=3323165.3323206}, doi = {10.1145/3323165.3323206}, booktitle = {The 31st {ACM} on {Symposium} on {Parallelism} in {Algorithms} and {Architectures} - {SPAA} '19}, publisher = {ACM Press}, author = {Eppstein, David and Vazirani, Vijay V.}, year = {2019}, pages = {23--30} } @article{Stanley2015, author = {Stanley, Richard P.}, doi = {10.1007/s00454-015-9683-0}, issn = {14320444}, journal = {Discrete and Computational Geometry}, keywords = {Chromatic polynomial,Dilworth truncation,Hyperplane arrangement,Line shelling,Matroid,Order polytope}, title = {Valid Orderings of Real Hyperplane Arrangements}, year = {2015} } @article{Hohlweg2011, archivePrefix = {arXiv}, author = {Hohlweg, Christophe and Lange, Carsten E M C and Thomas, Hugh}, doi = {10.1016/j.aim.2010.07.005}, issn = {00018708}, journal = {Advances in Mathematics}, keywords = {Cambrian fans,Cambrian lattices,Cluster fans,Coxeter groups,Generalized associahedron}, title = {Permutahedra and generalized associahedra}, year = {2011} } @article{Dynkin2010, author = {Dynkin, E. B. and Minchenko, A. N.}, doi = {10.1007/s00031-010-9100-y}, issn = {10834362}, journal = {Transformation Groups}, title = {Enhanced Dynkin diagrams and Weyl orbits}, year = {2010} } @article{Stanley2016, abstract = {This paper surveys some combinatorial aspects of Smith normal form, and more generally, diagonal form. The discussion includes general algebraic properties and interpretations of Smith normal form, critical groups of graphs, and Smith normal form of random integer matrices. We then give some examples of Smith normal form and diagonal form arising from (1) symmetric functions, (2) a result of Carlitz, Roselle, and Scoville, and (3) the Varchenko matrix of a hyperplane arrangement.}, archivePrefix = {arXiv}, author = {Stanley, Richard P.}, doi = {10.1016/j.jcta.2016.06.013}, issn = {10960899}, journal = {Journal of Combinatorial Theory. Series A}, keywords = {Critical group,Diagonal form,Jacobi–Trudi matrix,Random matrix,Smith normal form,Varchenko matrix}, month = nov, pages = {476--495}, publisher = {Academic Press Inc.}, title = {Smith normal form in combinatorics}, volume = {144}, year = {2016} } @article{Varchenko1993, author = {Varchenko, Alexandre}, doi = {10.1006/aima.1993.1003}, issn = {10902082}, journal = {Advances in Mathematics}, number = {1}, pages = {110--144}, title = {Bilinear form of real configuration of hyperplanes}, volume = {97}, year = {1993} } @techreport{Mokler2017, abstract = {We investigate the faces and the face lattices of arbitrary Coxeter group invariant convex subcones of the Tits cone of a linear Coxeter system as introduced by E. B. Vinberg. Particular examples are given by certain Weyl group invariant polyhedral cones, which underlie the theory of normal reductive linear algebraic monoids as developed by M. S. Putcha and L. E. Renner. We determine the faces and the face lattice of the Tits cone and the imaginary cone, generalizing some of the results obtained for linear Coxeter systems with symmetric root bases by M. Dyer, and for linear Coxeter systems with free root bases by E. Looijenga, P. Slodowy, and the author.}, archivePrefix = {arXiv}, author = {Mokler, Claus}, title = {Invariant convex subcones of the Tits cone of a linear Coxeter group}, year = {2017} } @article{McCammond2017, abstract = {This article resolves several long-standing conjectures about Artin groups of Euclidean type. Specifically we prove that every irreducible Euclidean Artin group is a torsion-free centerless group with a decidable word problem and a finite-dimensional classifying space. We do this by showing that each of these groups is isomorphic to a subgroup of a group with an infinite-type Garside structure. The Garside groups involved are introduced here for the first time. They are constructed by applying semi-standard procedures to crystallographic groups that contain Euclidean Coxeter groups but which need not be generated by the reflections they contain.}, archivePrefix = {arXiv}, author = {McCammond, Jon and Sulway, Robert}, doi = {10.1007/s00222-017-0728-2}, issn = {00209910}, journal = {Inventiones Mathematicae}, keywords = {20F36}, month = oct, number = {1}, pages = {231--282}, publisher = {Springer New York LLC}, title = {Artin groups of Euclidean type}, volume = {210}, year = {2017} } @article{Zuber1997, abstract = {Graphs which generalize the simple or affine Dynkin diagrams are introduced. Each diagram defines a bilinear form on a root system and thus a reflection group. We present some properties of these groups and of their natural "Coxeter element". The folding of these graphs and groups is also discussed, using the theory of C-algebras. (Proceedings of the Taniguchi Symposium {Topological Field Theory, Primitive Forms and Related Topics}, Kyoto Dec 1996)}, archivePrefix = {arXiv}, author = {Zuber, Jean-Bernard}, month = jul, primaryClass = {hep-th}, title = {Generalized Dynkin diagrams and root systems and their folding}, year = {1997} } @article{Bjorner1990, abstract = {A hyperplane arrangement is a finite set of hyperplanes through the origin in a finite-dimensional real vector space. Such an arrangement divides the vector space into a finite set of regions. Every such region determines a partial order on the set of all regions in which these are ordered according to their combinatorial distance from the fixed base region. We show that the base region is simplicial whenever the poset of regions is a lattice and that conversely this condition is sufficient for the lattice property for three-dimensional arrangements, but not in higher dimensions. For simplicial arrangements, the poset of regions is always a lattice. In the case of supersolvable arrangements (arrangements for which the lattice of intersections of hyperplanes is supersolvable), the poset of regions is a lattice if the base region is suitably chosen. We describe the geometric structure of such arrangements and derive an expression for the rank-generating function similar to a known one for Coxeter arrangements. For arrangements with a lattice of regions we give a geometric interpretation of the lattice property in terms of a closure operator defined on the set of hyperplanes. The results generalize to oriented matroids. We show that the adjacency graph (and poset of regions) of an arrangement determines the associated oriented matroid and hence in particular the lattice of intersections. {\textcopyright} 1990 Springer-Verlag New York Inc.}, author = {Bj{\"{o}}rner, Anders and Edelman, Paul H. and Ziegler, G{\"{u}}nter M.}, doi = {10.1007/BF02187790}, issn = {01795376}, journal = {Discrete {\&} Computational Geometry}, month = dec, number = {1}, pages = {263--288}, publisher = {Springer-Verlag}, title = {Hyperplane arrangements with a lattice of regions}, volume = {5}, year = {1990} } @article{Dyer2016, abstract = {Let (W, S) be an infinite Coxeter system. To each geometric representation of W is associated a root system. While a root system lives in the positive side of the isotropic cone of its associated bilinear form, an imaginary cone lives in the negative side of the isotropic cone. Precisely on the isotropic cone, between root systems and imaginary cones, lives the set E of limit points of the directions of roots. In this article we study the close relations of the imaginary cone with the set E, which leads to new fundamental results about the structure of geometric representations of infinite Coxeter groups. In particular, we show that the W-action on E is minimal and faithful, and that E and the imaginary cone can be approximated arbitrarily well by sets of limit roots and imaginary cones of universal root subsystems of W, i.e., root systems for Coxeter groups without braid relations (the free object for Coxeter groups). Finally, we discuss open questions as well as the possible relevance of our framework in other areas such as geometric group theory.}, author = {Dyer, Matthew and Hohlweg, Christophe and Ripoll, Vivien}, doi = {10.1007/s00209-016-1671-4}, issn = {14321823}, journal = {Mathematische Zeitschrift}, keywords = {Accumulation set,Coxeter group,Elementary roots,Limit point,Root system,Roots,Small roots}, title = {Imaginary cones and limit roots of infinite Coxeter groups}, year = {2016} } @article{Delucchi2006, abstract = {We examine Deligne's classical proof of the asphericity of simplicial arrangements from the viewpoint of the combinatorics of the poset of regions of the arrangement. This turns out to be very natural. In particular, we show that an arrangement is simplicial only if it satisfies Deligne's property on positive paths, thus answering a question posed by Luis Paris.}, archivePrefix = {arXiv}, author = {Delucchi, Emanuele}, month = nov, primaryClass = {math}, title = {Combinatorial remarks on a classical theorem of Deligne}, year = {2006} } @article{Cautis2014, abstract = {We give a diagrammatic presentation in terms of generators and relations of the representation category of (formula presented) More precisely, we produce all the relations among (formula presented) -webs, thus describing the full subcategory (formula presented) -generated by fundamental representations (formula presented) (this subcategory can be idempotent completed to recover the entire representation category). Our result answers a question posed by Kuperberg in Commun Math Phys 180(1):109–151, (1996) and affirms conjectures of Kim in Graphical calculus on representations of quantum lie algebras, Ph. D. thesis, University of California, Davis, (2003) and Morrison in A Diagrammatic Category for the Representation Theory of (formula presented). PhD thesis, University of California, Berkeley, (2007). Our main tool is an application of quantum skew Howe duality. This is the published version of arXiv:1210.6437.}, author = {Cautis, Sabin and Kamnitzer, Joel and Morrison, Scott}, doi = {10.1007/s00208-013-0984-4}, issn = {00255831}, journal = {Mathematische Annalen}, month = sep, number = {1-2}, pages = {351--390}, publisher = {Springer New York LLC}, title = {Webs and quantum skew Howe duality}, volume = {360}, year = {2014} } @article{Cuntz2019, abstract = {Simplicial arrangements are classical objects in discrete geometry. Their classification remains an open problem but there is a list conjectured to be complete at least for rank three. A further important class in the theory of hyperplane arrangements with particularly nice geometric, algebraic, topological, and combinatorial properties are the supersolvable arrangements. In this paper we give a complete classification of supersolvable simplicial arrangements (in all ranks). For each fixed rank, our classification already includes almost all known simplicial arrangements. Surprisingly, for irreducible simplicial arrangements of rank greater than three, our result shows that supersolvability imposes a strong integrality property; such an arrangement is called crystallographic. Furthermore we introduce Coxeter graphs for simplicial arrangements which serve as our main tool of investigation.}, archivePrefix = {arXiv}, author = {Cuntz, Michael and M{\"{u}}cksch, Paul}, doi = {10.1016/j.aam.2019.02.008}, issn = {10902074}, journal = {Advances in Applied Mathematics}, keywords = {Coxeter graph,Hyperplane arrangements,Reflection arrangements,Root system,Simplicial arrangements,Supersolvable arrangements}, title = {Supersolvable simplicial arrangements}, year = {2019} } @article{Paolini2019, archivePrefix = {arXiv}, author = {Paolini, Giovanni and Salvetti, Mario}, month = jul, title = {Proof of the {\$}K(\backslashpi,1){\$} conjecture for affine Artin groups}, year = {2019} } @article{Rolfsen2010, abstract = {This is an introduction to the braid groups, as presented in the summer school and workshop on braid groups at the National University of Singapore in June 2007.}, archivePrefix = {arXiv}, author = {Rolfsen, Dale}, month = oct, title = {Tutorial on the braid groups}, year = {2010} } @article{Douglass2008, abstract = {We give an overview of some of the main results in geometric representation theory that have been proved by means of the Steinberg variety. Steinberg's insight was to use such a variety of triples in order to prove a conjectured formula by Grothendieck. The Steinberg variety was later used to give an alternative approach to Springer's representations and played a central role in the proof of the Deligne-Langlands conjecture for Hecke algebras by Kazhdan and Lusztig.}, archivePrefix = {arXiv}, author = {Douglass, J. Matthew and Roehrle, Gerhard}, month = feb, title = {The Steinberg Variety and Representations of Reductive Groups}, year = {2008} } @article{Cuntz2009, abstract = {We continue our study of Cartan schemes and their Weyl groupoids. The results in this paper provide an algorithm to determine connected simply connected Cartan schemes of rank three, where the real roots form a finite irreducible root system. The algorithm terminates: Up to equivalence there are exactly 55 such Cartan schemes, and the number of corresponding real roots varies between 6 and 37. We identify those Weyl groupoids which appear in the classification of Nichols algebras of diagonal type.}, archivePrefix = {arXiv}, author = {Cuntz, M. and Heckenberger, I.}, month = dec, title = {Finite Weyl groupoids of rank three}, year = {2009} } @article{Cuntz2010, abstract = {We introduce the simple notion of a "crystallographic arrangement" and prove a one-to-one correspondence between these arrangements and the connected simply connected Cartan schemes for which the real roots are a finite root system (up to equivalence on both sides). We thus obtain a more accessible definition for this very large subclass of the class of simplicial arrangements for which a complete classification is known.}, archivePrefix = {arXiv}, author = {Cuntz, Michael}, doi = {10.1112/blms/bdr009}, month = jun, title = {Crystallographic arrangements: Weyl groupoids and simplicial arrangements}, year = {2010} } @article{Wang2018, archivePrefix = {arXiv}, author = {Wang, Weijia}, month = mar, title = {Infinite Reduced Words, Lattice Property And Braid Graph of Affine Weyl Groups}, year = {2018} } @article{Cuntz2015, author = {Cuntz, M. and Geis, D.}, doi = {10.1007/s13366-014-0190-x}, issn = {0138-4821}, journal = {Beitr{\"{a}}ge zur Algebra und Geometrie / Contributions to Algebra and Geometry}, month = oct, number = {2}, pages = {439--458}, publisher = {Springer Berlin Heidelberg}, title = {Combinatorial simpliciality of arrangements of hyperplanes}, volume = {56}, year = {2015} } @article{, title = {Simplicial arrangements on convex cones} } @article{Crisp2001, abstract = {Let A be an Artin group with standard generating set {$\sigma$ s : s ∈ S}. Tits conjectured that the only relations in A amongst the squares of the generators are consequences of the obvious ones, namely that $\sigma$ 2 s and $\sigma$ 2 t commute whenever $\sigma$ s and $\sigma$ t commute , for s, t ∈ S. In this paper we prove Tits' conjecture for all Artin groups. In fact, given a number m s ≥ 2 for each s ∈ S, we show that the elements {T s = $\sigma$ ms s : s ∈ S} generate a subgroup that has a finite presentation in which the only defining relations are that T s and T t commute if $\sigma$ s and $\sigma$ t commute.}, author = {Crisp, John and Paris, Luis}, doi = {10.1007/s002220100138}, title = {The solution to a conjecture of Tits on the subgroup generated by the squares of the generators of an Artin group}, year = {2001} } @inproceedings{Paris2000, author = {Paris, Luis}, doi = {10.2969/aspm/02710257}, issn = {0920-1971}, pages = {257--272}, publisher = {Mathematical Society of Japan}, title = {On the fundamental group of the complement of a complex hyperplane arrangement}, year = {2000} } @article{, title = {ull-tex} } @article{Dyer2011a, abstract = {This is the first of a series of papers which define and study structures called rootoids, which are groupoids equipped with a representation in the category of Boolean rings and with an associated 1-cocycle. The axioms for rootoids are abstracted from formal properties of Coxeter groups with their root systems and weak orders. They imply that each of the weak orders of a rootoid embeds as an order ideal in a complete ortholattice. This first paper is concerned only with the most basic definitions, facts and examples; the main results, which are new even for Coxeter groups, will be stated and proved in subsequent papers. They involve certain categories of rootoids and especially a notion of functor rootoid.}, archivePrefix = {arXiv}, author = {Dyer, Matthew}, month = oct, title = {Groupoids, root systems and weak order I}, year = {2011} } @article{Dyer2009, author = {Dyer, Matthew J.}, doi = {10.1016/j.jalgebra.2008.11.001}, issn = {00218693}, journal = {Journal of Algebra}, month = feb, number = {3}, pages = {953--981}, title = {Embeddings of root systems II: Permutation root systems}, volume = {321}, year = {2009} } @techreport{Wang2017, author = {Wang, Weijia and Dyer, Matthew}, title = {CLOSURE OPERATOR AND LATTICE PROPERTY OF ROOT SYSTEMS}, year = {2017} } @article{Viard2015, abstract = {Weak order on a Coxeter group W is a partial order on W appearing in many areas of algebraic combinatorics. In this thesis, we propose a new general model for the study of the weak order and other related partially ordered sets (also called “posets”) and we explore various algebraic and combinatorial consequences of this construction. We begin with studying a restricted version of this model in Chapter 3. More precisely, we explain how one can associate a poset to any simple acyclic digraph together with a valuation on its vertices (also called “valued digraph”). We then prove that these posets are complete meet semi-lattices in general, complete lattices when the underlying digraph is finite, and we give an explicit formula to compute the value of their M{\"{o}}bius functions. Then, we show that the weak order on Coxeter groups of type A, B and A, the flag weak order, and the up-set (resp. down-set) lattices of any finite poset can be described within this theory. This description naturally leads to associate a quasi-symmetric function to any element of An And An, and we demonstrate that this function is in fact the corresponding Stanley symmetric function. In Chapter 4 we introduce the main results of this thesis. Indeed, we introduce in this chapter the generalization of the construction made in Chapter 3 to the case of any valued digraph, that is without the simplicity and acyclicity condition. Furthermore, this new definition allows us to get rid of some constraints of the definition of Chapter 3, allowing us to associate a complete lattice to each valued digraph. In particular, the meet semi-lattices of Chapter 3 are naturally extended into complete lattices. This leads us to the study of some conjectures of Dyer about the properties of an extension of the weak order having a lot of the properties conjecturally attached to Dyer's extensions, and we prove that each one of our extensions contains Dyer's extension as a sub-poset. We make the conjecture that one of this extension coincide with the one of Dyer, and we provide tools in order to test this conjecture. Finally, we study various consequences of out theory : we provide extensions of Cambrian semi-lattices into complete lattices (end of Chapter 4), we construct a new combinatorial model for Tamari and m-Tamari lattices (Chapter 5), and we finish with an application to tableaux combinatorics (Chapter 6)}, author = {Viard, François}, keywords = {Cambrian semi-lattices,Coxeter groups,Digraphs,Graphes orient{\'{e}}s,Groupe de Coxeter,Lattices,Ordre faible,Root systems,Semi-treillis cambriens,Syst{\`{e}}me de racines,Treillis,Weak order}, month = nov, title = {From valued digraphs to complete lattices : a new approach of weak order on Coxeter groups}, year = {2015} } @techreport{Berlin2013, author = {Berlin, Jean-Philippe Labb{\'{e}}}, title = {Polyhedral Combinatorics of Coxeter Groups}, year = {2013} } @article{Dyer2012a, author = {Dyer, M. J.}, doi = {10.1090/conm/139/1197833}, pages = {141--165}, title = {Hecke algebras and shellings of Bruhat intervals. II. Twisted Bruhat orders}, volume = {139}, year = {2012} } @article{, doi = {10.1016/0021-8693(90)90149-I}, issn = {0021-8693}, journal = {Journal of Algebra}, month = nov, number = {1}, pages = {57--73}, publisher = {Academic Press}, title = {Reflection subgroups of Coxeter systems}, volume = {135}, year = {1990} } @techreport{Postnikov2000, abstract = {dedicated to the memory of gian-carlo rota We investigate several hyperplane arrangements that can be viewed as deformations of Coxeter arrangements. In particular, we prove a conjecture of Linial and Stanley that the number of regions of the arrangement x i {\&}x j =1, 11i{\textless} jn, is equal to the number of alternating trees on n+1 vertices. Remarkably, these numbers have several additional combinatorial interpretations in terms of binary trees, partially ordered sets, and tournaments. More generally, we give formulae for the number of regions and the Poincare polynomial of certain finite subarrangements of the affine Coxeter arrangement of type A n{\&}1. These formulae enable us to prove a ``Riemann hypothesis'' on the location of zeros of the Poincaree polynomial. We give asymptotics of the Poincaree polynomials when n goes to infinity. We also consider some generic deformations of Coxeter arrangements of type A n{\&}1 .}, author = {Postnikov, Alexander and Stanley, Richard P}, booktitle = {Journal of Combinatorial Theory, Series A}, keywords = {AMS 2000 subject classifications: Primary 05A15,Coxeter arrangement,Linial arrangement,Secondary 52C35, 05A16, 05C05 Key Words: hyperplan,characteristic polynomial,trees}, pages = {5444597}, title = {Deformations of Coxeter Hyperplane Arrangements 1}, volume = {91}, year = {2000} } @article{Dyer1991a, author = {Dyer, Matthew}, journal = {Compositio Mathematica}, number = {2}, pages = {185--191}, title = {On the “Bruhat graph” of a Coxeter system}, volume = {78}, year = {1991} } @article{Dyer1994, author = {Dyer, M.J.}, doi = {10.1006/jabr.1994.1049}, issn = {00218693}, journal = {Journal of Algebra}, month = feb, number = {3}, pages = {861--879}, title = {Quotients of Twisted Bruhat Orders}, volume = {163}, year = {1994} } @article{Dyer1991, author = {Dyer, Matthew}, journal = {Compositio Mathematica}, number = {2}, pages = {185--191}, title = {On the “Bruhat graph” of a Coxeter system}, volume = {2}, year = {1991} } @techreport{Dyer2011, abstract = {This is the second introductory paper concerning structures called rootoids and protorootoids, the definition of which is abstracted from formal properties of Coxeter groups with their root systems and weak orders. The ubiquity of protorootoids is shown by attaching them to structures such as groupoids with generators , to simple graphs, to subsets of Boolean rings, to possibly infinite oriented matroids, and to groupoids with a specified preorder on each set of morphisms with fixed codomain; in each case, the condition that the structure give rise to a rootoid defines an interesting subclass of these structures. The paper also gives non-trivial examples of morphisms of rootoids and describes (without proof, and partly informally) some main ideas, results and questions from subsequent papers of the series, including the basic facts about principal rootoids and functor rootoids which together provide the raison d'ˆ etre for these papers.}, archivePrefix = {arXiv}, author = {Dyer, Matthew}, title = {GROUPOIDS, ROOT SYSTEMS AND WEAK ORDER II}, year = {2011} } @article{Reading2009, abstract = {We define a new lattice structure on the elements of a finite Coxeter group W. This lattice, called the shard intersection order, is weaker than the weak order and has the noncrossing partition lattice NC(W) as a sublattice. The new construction of NC(W) yields a new proof that NC(W) is a lattice. The shard intersection order is graded and its rank generating function is the W-Eulerian polynomial. Many order-theoretic properties of the shard intersection order, like Mobius number, number of maximal chains, etc., are exactly analogous to the corresponding properties of NC(W). There is a natural dimension-preserving bijection between simplices in the order complex of the shard intersection order (i.e. chains in the shard intersection order) and simplices in a certain pulling triangulation of the W-permutohedron. Restricting the bijection to the order complex of NC(W) yields a bijection to simplices in a pulling triangulation of the W-associahedron. The shard intersection order is defined indirectly via the polyhedral geometry of the reflecting hyperplanes of W. Indeed, most of the results of the paper are proven in the more general setting of simplicial hyperplane arrangements.}, archivePrefix = {arXiv}, author = {Reading, Nathan}, month = sep, title = {Noncrossing partitions and the shard intersection order}, year = {2009} } @article{Reading2014, abstract = {We consider two problems that appear at first sight to be unrelated. The first problem is to count certain diagrams consisting of noncrossing arcs in the plane. The second problem concerns the weak order on the symmetric group. Each permutation {\$}x{\$} has a canonical join representation: a unique lowest set of permutations joining to {\$}x{\$}. The second problem is to determine which sets of permutations appear as canonical join representations. The two problems turn out to be closely related because the noncrossing arc diagrams provide a combinatorial model for canonical join representations. The same considerations apply to more generally to lattice quotients of the weak order. Considering quotients produces, for example, a new combinatorial object counted by the Baxter numbers and an analogous new object in bijection with generic rectangulations.}, archivePrefix = {arXiv}, author = {Reading, Nathan}, month = may, title = {Noncrossing arc diagrams and canonical join representations}, year = {2014} } @techreport{Hohlweg, abstract = {In this article, we investigate the existence of joins in the weak order of an infinite Coxeter group W. We give a geometric characterization of the existence of a join for a subset X in W in terms of the inversion sets of its elements and their position relative to the imaginary cone. Finally, we discuss inversion sets of infinite reduced words and the notions of biconvex and biclosed sets of positive roots.}, archivePrefix = {arXiv}, author = {Hohlweg, Christophe and Labb{\'{e}}, Jean-Philippe and Labb{\'{e}}, Labb´}, title = {ON INVERSION SETS AND THE WEAK ORDER IN COXETER GROUPS}, } @incollection{Dyer2012, author = {Dyer, M J}, doi = {10.1090/conm/139/1197833}, pages = {141--165}, title = {Hecke algebras and shellings of Bruhat intervals. II. Twisted Bruhat orders}, volume = {89}, year = {2012} } @article{Dyer2019, abstract = {This paper provides some evidence for conjectural relations between extensions of (right) weak order on Coxeter groups, closure operators on root systems, and Bruhat order. The conjecture focused upon here refines an earlier question as to whether the set of initial sections of reflection orders, ordered by inclusion, forms a complete lattice. Meet and join in weak order are described in terms of a suitable closure operator. Galois connections are defined from the power set of {\$}W{\$} to itself, under which maximal subgroups of certain groupoids correspond to certain complete meet subsemilattices of weak order. An analogue of weak order for standard parabolic subsets of any rank of the root system is defined, reducing to the usual weak order in rank zero, and having some analogous properties in rank one (and conjecturally in general).}, archivePrefix = {arXiv}, author = {Dyer, Matthew}, doi = {10.4153/CJM-2017-059-0}, issn = {0008-414X}, journal = {Canadian Journal of Mathematics}, keywords = {Coxeter group,lattice,root system,weak order}, month = apr, number = {2}, pages = {299--336}, title = {On the Weak Order of Coxeter Groups}, volume = {71}, year = {2019} } @techreport{Cellini1999, abstract = {Let (W, S) be a Coxeter system with set of reflections T. It is known that if is a total reflection order for W , then, for each s ∈ S, {t ∈ T | t s} and its complement are stable under conjugation by s. Moreover the upper and lower s-conjugates of are still total reflection orders. For any total order on T , say that is stable if {t ∈ T | t s} is stable under conjugation by s for each s ∈ S. We prove that if and all orders obtained from by successive lower or upper S-conjugations are stable, then is a total reflection order.}, author = {Cellini, Paola}, booktitle = {PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY}, number = {6}, title = {A CHARACTERIZATION OF TOTAL REFLECTION ORDERS}, volume = {128}, year = {1999} } @article{Edgar2007, abstract = {Twisted Bruhat orders are certain partial orders on a Coxeter system (W, S) associated to initial sections of reflection orders, which are certain subsets of the set of reflections T of a Coxeter system. We determine which subsets of T give rise to a partial order on W in the same way.}, author = {Edgar, Tom}, doi = {10.1007/s10801-007-0060-9}, issn = {09259899}, journal = {Journal of Algebraic Combinatorics}, number = {3}, pages = {357--362}, title = {Sets of reflections defining twisted Bruhat orders}, volume = {26}, year = {2007} } @article{, title = {hellabl} } @article{Rains2013, author = {Rains, Eric M. and Vazirani, Monica J.}, doi = {10.1007/s10801-012-0371-3}, issn = {0925-9899}, journal = {Journal of Algebraic Combinatorics}, month = may, number = {3}, pages = {455--502}, publisher = {Springer US}, title = {Deformations of permutation representations of Coxeter groups}, volume = {37}, year = {2013} } @article{Athanasiadis2014, author = {Athanasiadis, Christos A. and Roichman, Yuval}, doi = {10.1007/s10801-013-0439-8}, issn = {0925-9899}, journal = {Journal of Algebraic Combinatorics}, month = feb, number = {1}, pages = {75--98}, publisher = {Springer US}, title = {The absolute order of a permutation representation of a Coxeter group}, volume = {39}, year = {2014} } @techreport{, title = {Biclosed sets in combinatorics}, year = {2015} } @article{Hohlweg2016, abstract = {In this article, we investigate the existence of joins in the weak order of an infinite Coxeter group W. We give a geometric characterization of the existence of a join for a subset X in W in terms of the inversion sets of its elements and their position relative to the imaginary cone. Finally, we discuss inversion sets of infinite reduced words and the notions of biconvex and biclosed sets of positive roots.}, author = {Hohlweg, Christophe and Labb{\'{e}}, Jean Philippe}, doi = {10.1016/j.ejc.2016.01.002}, issn = {01956698}, journal = {European Journal of Combinatorics}, month = jul, pages = {1--19}, publisher = {Academic Press}, title = {On inversion sets and the weak order in Coxeter groups}, volume = {55}, year = {2016} } @article{, title = {Imported from https://www.researchgate.net/publication/246361561{\_}Hecke{\_}algebras{\_}and{\_}shellings{\_}of{\_}Bruhat{\_}intervals}, } @article{, journal = {Society}, number = {3}, pages = {661--665}, title = {A Characterization of a Special Ordering in a Root System Author ( s ): Paolo Papi Source : Proceedings of the American Mathematical Society , Vol . 120 , No . 3 ( Mar ., 1994 ), pp . Published by : American Mathematical Society Stable URL : http://www.js}, volume = {120}, year = {2010} } @article{Papi1994, author = {Papi, Paolo}, doi = {10.2307/2160454}, issn = {00029939}, journal = {Proceedings of the American Mathematical Society}, month = mar, number = {3}, pages = {661}, title = {A Characterization of a Special Ordering in a Root System}, volume = {120}, year = {1994} } @article{Cellini1998, abstract = {We analyze the structure of total reflection orders in affine root systems. We obtain a complete characterization of the finite sections of these orders. {\textcopyright} 1998 Academic Press.}, author = {Cellini, Paola and Papi, Paolo}, doi = {10.1006/jabr.1997.7378}, issn = {00218693}, journal = {Journal of Algebra}, title = {The Structure of Total Reflection Orders in Affine Root Systems}, year = {1998} } @techreport{Lam2009, abstract = {This is the second in a series of papers developing a theory of total positivity for loop groups. In this paper, we study infinite products of Chevalley generators. We show that the combinatorics of infinite reduced words underlies the theory, and develop the formalism of infinite sequences of braid moves, called a braid limit. We relate this to a partial order, called the limit weak order, on infinite reduced words. The limit semigroup generated by Chevalley generators has a transfinite structure. We prove a form of unique factorization for its elements, in effect reducing their study to infinite products which have the order structure of N. For the latter infinite products, we show that one always has a factorization which matches an infinite Coxeter element. One of the technical tools we employ is a totally positive exchange lemma which appears to be of independent interest. This result states that the exchange lemma (in the context of Coxeter groups) is compatible with total positivity in the form of certain inequalities.}, archivePrefix = {arXiv}, author = {Lam, Thomas and Pylyavskyy, Pavlo}, title = {TOTAL POSITIVITY FOR LOOP GROUPS II: CHEVALLEY GENERATORS}, year = {2009} } @techreport{Chajda1998, abstract = {A concept of congruence preserving upper and lower bounds in a poset P is introduced. If P is a lattice, this concept coincides with the notion of lattice congruence. Keywords: ordered set, morphism, lower and upper bounds MSC 2000 : 06A06, 06B10 There exist various concepts of a congruence relation in ordered sets. We use the term "ordered set" for the partially ordered set. All of them define a congruence as an equivalence relation whose classes are convex subsets. However, this concept is too weak, namely the factor set by such an equivalence need not be an ordered set. Hence, the definitions are usually amended by additional conditions. As an example we can show the definition by M. Kolibiar [Kol]. A natural condition for a congruence on an ordered set is that if this set is a lattice (w.r.t. the order) then this congruence coincides with the lattice congruence. The aim of our paper is to introduce a concept of congruence in an ordered set satisfying all the foregoing assumptions which, moreover, corresponds to the concept of morphism preserving upper and lower bounds. Let A = (A,) be an ordered set. If there is no danger of misunderstanding, the symbol will be omitted. For a subset B ⊆ A (with the induced order) we denote by L(B) or U (B) the set of all lower or upper bounds of B, i. e. L(B) = {x ∈ A ; x a for all a ∈ B}, U (B) = {x ∈ A ; x a for all a ∈ B}. We adopt the notation U (B, C) = U (B ∪ C) and L(B, C) = L(B ∪ C). If B = {b 1 , b 2 ,. .. , b n }, we will write briefly U (B) = U (b 1 , b 2 ,. .. , b n), dually for L(B). If 95}, author = {Chajda, Ivan and Sn{\'{a}}{\v{s}}el, V{\'{a}}clav}, pages = {95--100}, title = {CONGRUENCES IN ORDERED SETS}, volume = {1}, year = {1998} } @article{Reading2009a, abstract = {We define a new lattice structure on the elements of a finite Coxeter group W. This lattice, called the shard intersection order, is weaker than the weak order and has the noncrossing partition lattice NC(W) as a sublattice. The new construction of NC(W) yields a new proof that NC(W) is a lattice. The shard intersection order is graded and its rank generating function is the W-Eulerian polynomial. Many order-theoretic properties of the shard intersection order, like Mobius number, number of maximal chains, etc., are exactly analogous to the corresponding properties of NC(W). There is a natural dimension-preserving bijection between simplices in the order complex of the shard intersection order (i.e. chains in the shard intersection order) and simplices in a certain pulling triangulation of the W-permutohedron. Restricting the bijection to the order complex of NC(W) yields a bijection to simplices in a pulling triangulation of the W-associahedron. The shard intersection order is defined indirectly via the polyhedral geometry of the reflecting hyperplanes of W. Indeed, most of the results of the paper are proven in the more general setting of simplicial hyperplane arrangements.}, archivePrefix = {arXiv}, author = {Reading, Nathan}, month = sep, title = {Noncrossing partitions and the shard intersection order}, year = {2009} } @article{, abstract = {In this chapter, we develop the basic theory of finite Coxeter groups, drawing on results already proved for posets of regions. There are two main points to this chapter: First, to show how the geometry and lattice theory of hyperplane arrangements underlies the theory of finite Coxeter groups, and second, to point out the weak orders on finite Coxeter groups as an important class of lattice-theoretic examples. A broader class of examples is obtained as lattice quotients of weak orders. Several examples of such quotients are given in Sections 10-6 and 10-7. 10-1. Coxeter groups and the weak order A Coxeter group is a group presented by generators and relations of a very specific form. There is a finite 1 set S of generators, and for each pair s, t of distinct generators, we choose a quantity m(s, t), which must be either an 1 Some authors allow S to be infinite, but we have no need to do so.}, doi = {10.1007/978-3-319-44236-5_10}, title = {Finite Coxeter Groups and the Weak Order N. Reading}, year = {2016} } @article{, abstract = {Hyperplane arrangements (collections of codimension-1 subspaces) have long been an object of study in combinatorics, topology, and geometry. This chapter explores the lattice theory of the poset of regions of a (real) hyperplane arrangement. We discuss the open problem, first posed by Bj{\"{o}}rner, Edelman, and Ziegler [70], of characterizing by local geometric conditions which posets of regions are lattices. We give a local geometric characterization ("tightness") of which posets of regions are semidistributive lattices. Along the way, we discuss a local condition for checking that a partially ordered set is a lattice, along with analogous local conditions for determining lattice-theoretic properties. In the case of simplicial arrangements (which are in particular tight), we characterize the regions of the arrangement in terms of two notions of combinatorial convexity. We then turn our attention to lattice congruences on posets of regions, focusing in particular on the tight case. We begin with a discussion of lattice congruences from a combinatorial point of view. We then establish that tight posets of regions have the special property of being polygonal lattices. We discuss how to decompose the hyperplanes in a tight arrangement into shards and show how the polygonal property leads to a geometric characterization of 399}, doi = {10.1007/978-3-319-44236-5_9}, title = {Lattice Theory of the Poset of Regions N. Reading}, year = {2016} } @techreport{Alon2005, abstract = {For a p-adic hyperplane arrangement in a vector space V, we consider a local system of De Shalit on the Bruhat-Tits building of PGL(V). We express this local system in terms of Orlik-Solomon algebras, and calculate its cohomology in the case where the arrangement is finite.}, author = {Alon, Gil}, booktitle = {ISRAEL JOURNAL OF MATHEMATICS}, pages = {189--207}, title = {COHOMOLOGY OF LOCAL SYSTEMS COMING FROM p-ADIC HYPERPLANE ARRANGEMENTS}, volume = {14}, year = {2005} } @article{Saldanha2003, abstract = {Tilings of a quadriculated annulus A are counted according to volume (in the formal variable q) and flux (in p). We consider algebraic properties of the resulting generating function $\Phi$A (p, q . For q = -1, the non-zero roots in p must be roots of unity and for q{\textgreater}0, real negative. {\textcopyright} 2002 Elsevier Science (USA). All rights reserved.}, author = {Saldanha, Nicolau C and Tomei, Carlos}, doi = {10.1016/S0095-8956(02)00042-4}, issn = {00958956}, journal = {Journal of Combinatorial Theory. Series B}, keywords = {Dimers,Quadriculated surfaces,Tilings by dominoes}, month = may, number = {1}, pages = {153--183}, publisher = {Academic Press}, title = {Tilings of quadriculated annuli}, volume = {88}, year = {2003} } @techreport{Savage2013, abstract = {We study the roots of generalized Eulerian polynomials via a novel approach. We interpret Eulerian polynomials as the generating polynomials of a statistic over inversion sequences. Inversion sequences (also known as Lehmer codes or subexcedant functions) were recently generalized by Savage and Schuster, to arbitrary sequences s of positive integers, which they called s-inversion sequences. Our object of study is the generating polynomial of the ascent statistic over the set of s-inversion sequences of length n. Since this ascent statistic over inversion sequences is equidistributed with the descent statistic over permutations we call this generalized polynomial the s-Eulerian polynomial. The main result of this paper is that, for any sequence s of positive integers, the s-Eulerian polynomial has only real roots. This result is first shown to generalize several existing results about the real-rootedness of various Eulerian polynomials. We then show that it can be used to settle a conjecture of Brenti, that Eulerian polynomials for all finite Coxeter groups have only real roots, and partially settle a conjecture of Dilks, Petersen, Stembridge on type B affine Eulerian polynomials. It is then extended to several q-analogs. We show that the MacMahon-Carlitz q-Eulerian polynomial has only real roots whenever q is a positive real number confirming a conjecture of Chow and Gessel. The same holds true for the hyperoctahedral group and the wreath product groups, confirming further conjectures of Chow and Gessel, and Chow and Mansour, respectively. Our results have interesting geometric consequences as well.}, archivePrefix = {arXiv}, author = {Savage, Carla D and Mirk´, Mirk´o and Visontai, Mirk´o}, title = {THE s-EULERIAN POLYNOMIALS HAVE ONLY REAL ROOTS}, year = {2013} } @article{Zhang1997, abstract = {In the present paper, the minimal proper alternating cycle (MPAC) rotation graph R(G) of perfect matchings of a plane bipartite graph G is defined. We show that an MPAC rotation graph R(G) of G is a directed rooted tree, and thus extend such a result for generalized polyhex graphs to arbitrary plane bipartite graphs. As an immediate result, we describe a one-to-one correspondence between MPAC systems and perfect matchings in G.}, author = {Zhang, Heping and Zhang, Fuji}, doi = {10.1016/S0166-218X(96)00024-8}, issn = {0166218X}, journal = {Discrete Applied Mathematics}, month = feb, number = {1}, pages = {5--12}, title = {The rotation graphs of perfect matchings of plane bipartite graphs}, volume = {73}, year = {1997} } @article{Reshetikhin1990, author = {Reshetikhin, N. Y. and Turaev, V. G.}, doi = {10.1007/BF02096491}, issn = {0010-3616}, journal = {Communications in Mathematical Physics}, month = jan, number = {1}, pages = {1--26}, publisher = {Springer-Verlag}, title = {Ribbon graphs and their invaraints derived from quantum groups}, volume = {127}, year = {1990} } @techreport{Kuperberg1991, abstract = {We derive an inductive, combinatorial definition of a polynomial-valued regular isotopy invariant of links and tangled graphs. We show that the invariant equals the Reshetikhin-Turaev invariant corresponding to the exceptional simple Lie algebra G2. It is therefore related to G2 in the same way that the HOMFLY polynomial is related to An and the Kauffman polynomial is related to Bn, Cn, and Dn. We give parallel constructions for the other rank 2 Lie algebras and present some combinatorial conjectures motivated by the new inductive definitions. This paper is divided into two parts. In the first part we derive from first principles some variants of the link invariant known as the Jones polynomial. In the second part we show that these invariants are the same known invariants constructed using rank 2 Lie algebras, and we discuss some of their properties.}, author = {Kuperberg, Greg}, title = {The Quantum G 2 Link Invariant}, year = {1991} } @article{Valiant1979, abstract = {It is shown that the permanent function of (0, 1)-matrices is a complete problem for the class of counting problems associated with nondeterministic polynomial time computations. Related counting problems are also considered. The reductions used are characterized by their nontrivial use of arithmetic. {\textcopyright} 1979.}, author = {Valiant, L. G.}, doi = {10.1016/0304-3975(79)90044-6}, isbn = {03043975}, issn = {03043975}, journal = {Theoretical Computer Science}, month = jan, number = {2}, pages = {189--201}, pmid = {11802913}, publisher = {Elsevier}, title = {The complexity of computing the permanent}, volume = {8}, year = {1979} } @article{Percus1969, abstract = {The problem of counting the dimer coverings of a square lattice is recast as a counting of coverings by oriented closed loops. Thus the answer is expressed as the value of a suitable permanent. This permanent is transformed to a determinant, which on evaluation recovers the familiar result.}, author = {Percus, Jerome K.}, doi = {10.1063/1.1664774}, issn = {00222488}, journal = {Journal of Mathematical Physics}, month = oct, number = {10}, pages = {1881--1884}, publisher = {American Institute of Physics}, title = {One more technique for the dimer problem}, volume = {10}, year = {1969} } @article{Tenner2005, abstract = {We prove combinatorially that the parity of the number of domino tilings of a region is equal to the parity of the number of domino tilings of a particular subregion. Using this result we can resolve the holey square conjecture. We furthermore give combinatorial proofs of several other tiling parity results, including that the number of domino tilings of a particular family of rectangles is always odd.}, author = {Tenner, Bridget Eileen}, journal = {Electronic Journal of Combinatorics}, number = {2}, pages = {{\#}R17}, title = {Tiling Parity Results and the Holey Square Solution}, volume = {11}, year = {2005} } @article{Chen2013, abstract = {Two kinds of Au/CeO 2 , prepared by deposition-precipitation (DP) using urea (U) or NaOH (N) as precipitants were investigated as catalysts for HCHO oxidation. H 2 -TPR and XPS techniques were used to characterize the Au/CeO 2 samples. Due to the generation of increased amounts of active surface oxygen species resulting from the strong Au-CeO 2 interaction, the Au/CeO 2 (DPU) catalyst showed higher activity than the DPN catalyst, achieving 100{\%} conversion of HCHO into CO 2 and H 2 O at room temperature, even in the presence of water and at high GHSV (143,000h -1 ); moreover, the conversion was stable for at least 60h. The reaction mechanism and the rate limiting steps for HCHO oxidation over the Au/CeO 2 catalysts were identified by means of in situ DRIFTS studies. The influence of oxygen and water on the formation and consumption of the formate reaction intermediates was also investigated. Results suggest that Au/CeO 2 (DPU) is a promising catalyst for HCHO removal under real world conditions. {\textcopyright} 2012 Elsevier B.V.}, author = {Chen, Bing-Bing and Shi, Chuan and Crocker, Mark and Wang, Yu and Zhu, Ai-Min}, doi = {10.1016/j.apcatb.2012.11.028}, issn = {09263373}, journal = {Applied Catalysis B: Environmental}, month = mar, number = {2 R}, pages = {245--255}, title = {Catalytic removal of formaldehyde at room temperature over supported gold catalysts}, volume = {132-133}, year = {2013} } @book{Lovasz1993, author = {Lov{\'{a}}sz, L.}, pages = {636}, publisher = {Elsevier Science}, title = {Combinatorial Problems and Exercises, Second Edition}, year = {1993} } @article{Temperley1961, abstract = {An important, even though physically oversimplified model of a system (e.g. solution or gas) containing diatomic molecules is that of a lattice occupied by ‘rigid dimers' (e.g. Fowler and Rushbrooke 1937). Each dimer fills two nearest-neighbour sites on the lattice and no site may be occupied by more than one dimer. This represents a statistical problem of some difficulty which has so far been solved exactly only in one dimension (Green and Leipnik 1960, Fisher and Temperley 1960). (It has been treated by various authors on the basis of approximate statistical methods, e.g. Rushbrooke et al. (1953).) This note reports an exact solution for the dimer problem on the plane square lattice in the limiting case where the dimera completely fill the lattice (close-packed or high density limit).}, author = {Temperley, H. N.V. V. and Fisher, Michael E.}, doi = {10.1080/14786436108243366}, issn = {00318086}, journal = {Philosophical Magazine}, month = aug, number = {68}, pages = {1061--1063}, pmid = {23697256}, publisher = { Taylor {\&} Francis Group }, title = {Dimer problem in statistical mechanics-an exact result}, volume = {6}, year = {1961} } @article{Kasteleyn1961, abstract = {The number of ways in which a finite quadratic lattice (with edges or with periodic boundary conditions) can be fully covered with given numbers of "horizontal" and "vertical" dimers is rigorously calculated by a combinatorial method involving Pfaffians. For lattices infinite in one or two dimensions asymptotic expressions for this number of dimer configurations are derived, and as an application the entropy of a mixture of dimers of two different lengths on an infinite rectangular lattice is calculated. The relation of this combinatorial problem to the Ising problem is briefly discussed. {\textcopyright} 1957.}, archivePrefix = {arXiv}, author = {Kasteleyn, P. W.}, doi = {10.1016/0031-8914(61)90063-5}, isbn = {978-0-8176-4842-8}, journal = {Physica}, month = dec, number = {12}, pages = {1209--1225}, publisher = {North-Holland}, title = {The statistics of dimers on a lattice. I. The number of dimer arrangements on a quadratic lattice}, volume = {27}, year = {1961} } @article{Ciucu1996, title = {Enumeration of {Perfect} {Matchings} in {Graphs} with {Reflective} {Symmetry}}, volume = {77}, doi = {10.1006/jcta.1996.2725}, number = {1}, journal = {Journal of Combinatorial Theory, Series A}, author = {Ciucu, M.}, month = jan, year = {1997}, pages = {67--97} } @article{, title = {m19{\_}3-4{\_}2} } @article{Beck2009, abstract = {We examine domino tilings of rectangular boards, which are in natural bijection with perfect matchings of grid graphs. This leads to the study of their associated perfect matching polytopes, and we present some of their properties, in particular, when these polytopes are Gorenstein. We also introduce the notion of domino stackings and present some results and several open questions. Our techniques use results from graph theory, polyhedral geometry, and enumerative combinatorics.}, archivePrefix = {arXiv}, author = {Beck, Matthias and Haase, Christian and Sam, Steven V.}, doi = {10.1007/s00373-005-0858-y}, issn = {09110119}, journal = {Graphs and Combinatorics}, keywords = {Domino tilings,Ehrhart polynomials,Gorenstein polytopes,Grid graphs,Magic labellings,Perfect matching polytopes,Rational functions,Reciprocity theorems,Recurrence relations}, number = {4}, pages = {409--426}, title = {Grid graphs, Gorenstein polytopes, and domino stackings}, volume = {25}, year = {2009} } @article{Cohn1999, abstract = {We study the 2-adic behavior of the number of domino tilings of a 2n-by-2n square as nvaries. It was previously known that this number was of the form 2{\^{}}n f(n){\^{}}2, where f(n) is an odd, positive integer. We show that the function f is uniformly continuous under the 2-adic metric, and thus extends to a function on all of Z. The extension satisfies the functional equation f(-1-n) = +- f(n), where +- sign is + if n is congruent to 0 or 3 modulo 4 and - otherwise.}, archivePrefix = {arXiv}, author = {Cohn, Henry}, issn = {10778926}, journal = {Electronic Journal of Combinatorics}, month = aug, number = {1}, pages = {\#R14}, pmid = {8922461}, primaryClass = {math}, title = {2-Adic behavior of numbers of domino tilings}, volume = {6}, year = {1999} } @article{Kasteleyn1963, abstract = {After the introduction of the concept of lattice graph and a brief discussion of its role in the theory of the Ising model, a related combinatorial problem is discussed, namely that of the statistics of non‐overlapping dimers, each occupying two neighboring sites of a lattice graph. It is shown that the configurational partition function of this system can be expressed in terms of a Pfaffian, and hence calculated explicitly, if the lattice graph is planar and if the dimers occupy all lattice sites. By the examples of the quadratic and the hexagonal lattice, it is found that the dimer system may show a phase transition similar to that of a two‐dimensional Ising model, or one of a different nature, or no transition at all, depending on the activities of various classes of bonds. The Ising problem is then shown to be equivalent to a generalized dimer problem, and a rederivation, of Onsager's expression for the Ising partition function of a rectangular lattice graph is sketched on the basis of this equivalence.}, author = {Kasteleyn, P. W.}, doi = {10.1063/1.1703953}, journal = {Journal of Mathematical Physics}, month = feb, number = {2}, pages = {287--293}, publisher = {American Institute of Physics}, title = {Dimer statistics and phase transitions}, volume = {4}, year = {1963} } @article{Florescu2015, abstract = {{\textcopyright} 2015, Australian National University. All rights reserved. We consider the subgroup of the abelian sandpile group of the grid graph consisting of configurations of sand that are symmetric with respect to central vertical and horizontal axes. We show that the size of this group is (i) the number of domino tilings of a corresponding weighted rectangular checkerboard; (ii) a product of special values of Chebyshev polynomials; and (iii) a double-product whose factors are sums of squares of values of trigonometric functions. We provide a new derivation of the formula due to Kasteleyn and to Temperley and Fisher for counting the number of domino tilings of a 2m×2n rectangular checkerboard and a new way of counting the number of domino tilings of a 2m×2n checkerboard on a M¨obius strip.}, archivePrefix = {arXiv}, author = {Florescu, Laura and Morar, Daniela and Perkinson, David and Salter, Nick and Xu, Tianyuan}, issn = {10778926}, journal = {Electronic Journal of Combinatorics}, month = may, number = {1}, pages = {I--66}, title = {Sandpiles and dominos}, volume = {22}, year = {2015} } @article{Ciucu2003, abstract = {In the last decade there have been many results about special families of graphs whose number of perfect matchings is given by perfect or near perfect powers. In this paper we present an approach that allows proving them in a unified way. We use this approach to prove a conjecture of James Propp stating that the number of tilings of the so-called Aztec dungeon regions is a power (or twice a power) of 13. We also prove a conjecture of Matt Blum stating that the number of perfect matchings of a certain family of subgraphs of the square lattice is a power of 3 or twice a power of 3. In addition we obtain multi-parameter generalizations of previously known results, and new multi-parameter exact enumeration results. We obtain in particular a simple combinatorial proof of Bo-Yin Yang's multivariate generalization of fortresses, a result whose previously known proof was quite complicated, amounting to evaluation of the Kasteleyn matrix by explicit row reduction. We also include a new multivariate exact enumeration of Aztec diamonds, in the spirit of Stanley's multivariate version.}, archivePrefix = {arXiv}, author = {Ciucu, Mihai}, doi = {10.1023/A:1025005023573}, issn = {09259899}, journal = {Journal of Algebraic Combinatorics}, keywords = {Exact enumeration,Perfect matchings,Tilings}, month = jan, number = {3}, pages = {335--375}, primaryClass = {math}, title = {Perfect Matchings and Perfect Powers}, volume = {17}, year = {2003} } @article{Tenner2009, archivePrefix = {arXiv}, author = {Tenner, Bridget Eileen}, doi = {10.1007/s00373-009-0865-5}, isbn = {0780395050}, issn = {0911-0119}, journal = {Graphs and Combinatorics}, keywords = {Congruence,Domino tiling,Tiling}, month = nov, number = {4}, pages = {625--638}, publisher = {Springer Japan}, title = {Domino Tiling Congruence Modulo 4}, volume = {25}, year = {2009} } @article{Kokhas2009, abstract = {An Aztec diamond of rank n is a rhombus of side length n on the square grid. We give several new combinatorial proofs of known theorems about the numbers of domino tilings of diamonds and squares. We also prove generalizations of these theorems for the generating polynomials of some statistics of tilings. Some results here are new. For example, we describe how to calculate the rank of a tiling using special weights of edges on the square grid.}, author = {Kokhas, K. P.}, doi = {10.1007/s10958-009-9421-3}, issn = {10723374}, journal = {Journal of Mathematical Sciences}, month = may, number = {6}, pages = {868--894}, publisher = {Springer US}, title = {Domino tilings of Aztec diamonds and squares}, volume = {158}, year = {2009} } @article{Tauraso2004, abstract = {In this short note, we prove that the sequence A061646 from Neil Sloane's Online Encyclopedia of Integer Sequences is connected with the number of domino tilings of a holey square.}, author = {Tauraso, Roberto}, issn = {15307638}, journal = {Journal of Integer Sequences}, keywords = {Domino tilings,Fibonacci numbers}, number = {2}, title = {A new domino tiling sequence}, volume = {7}, year = {2004} } @article{Jockusch1994, abstract = {In 1961, P. W. Kasteleyn enumerated the domino tilings of a 2n × 2n chessboard. His answer was always a square or double a square (we call such a number "squarish"), but he did not provide a combinatorial explanation for this. In the present thesis, we prove by mostly combinatorial arguments that the number of matchings of a large class of graphs with 4-fold rotational symmetry is squarish; our result includes the squarishness of Kasteleyn's domino tilings as a special case and provides a combinatorial interpretation for the square root. We then extend our result to graphs with other rotational symmetries. {\textcopyright} 1994 Academic Press. Inc.}, author = {Jockusch, William}, doi = {10.1016/0097-3165(94)90006-X}, issn = {10960899}, journal = {Journal of Combinatorial Theory, Series A}, number = {1}, pages = {100--115}, pmid = {23225022}, title = {Perfect matchings and perfect squares}, volume = {67}, year = {1994} } @techreport{Pak2016, abstract = {Domino tileability is a classical problem in Discrete Geometry, famously solved by Thurston for simply connected regions in nearly linear time in the area. In this paper, we improve upon Thurston's height function approach to a nearly linear time in the perimeter.}, archivePrefix = {arXiv}, author = {Pak, Igor and Sheffer, Adam and Tassy, Martin}, booktitle = {Discrete {\&} Computational Geometry}, doi = {10.1007/s00454-016-9807-1}, issn = {14320444}, number = {2}, pages = {377--394}, title = {Fast Domino Tileability}, volume = {56}, year = {2016} } @article{Pachter1997, abstract = {We give the first complete combinatorial proof of the fact that the number of domino tilings of the 2n × 2n square grid is of the form 2n(2k + 1)2, thus settling a question raised in [4] . The proof lends itself naturally to some interesting generalizations, and leads to a number of new conjectures. Mathematical Subject Classification. Primary 05C70.}, author = {Pachter, L.}, journal = {Electronic Journal of Combinatorics}, pages = {{\#}R29}, title = {Combinatorial approaches and conjectures for 2-divisibility problems concerning domino tilings of polyominoes}, volume = {4}, year = {1997} } @article{Kuperberg2002, abstract = {We consider Kasteleyn and Kasteleyn-Percus matrices, which arise in enumerating matchings of planar graphs, up to matrix operations on their rows and columns. If such a matrix is defined over a principal ideal domain, this is equivalent to considering its Smith normal form or its cokernel. Many variations of the enumeration methods result in equivalent matrices. In particular, Gessel-Viennot matrices are equivalent to Kasteleyn-Percus matrices. We apply these ideas to plane partitions and related planar of tilings. We list a number of conjectures, supported by experiments in Maple, about the forms of matrices associated to enumerations of plane partitions and other lozenge tilings of planar regions and their symmetry classes. We focus on the case where the enumerations are round or q-round, and we conjecture that cokernels remain round or q-round for related "impossible enumerations" in which there are no tilings. Our conjectures provide a new view of the topic of enumerating symmetry classes of plane partitions and their generalizations. In particular we conjecture that a q-specialization of a Jacobi-Trudi matrix has a Smith normal form. If so it could be an interesting structure associated to the corresponding irreducible representation of SL(n, C ). Finally we find, with proof, the normal form of the matrix that appears in the enumeration of domino tilings of an Aztec diamond.}, archivePrefix = {arXiv}, author = {Kuperberg, Greg}, issn = {10778926}, journal = {Electronic Journal of Combinatorics}, month = aug, number = {1}, pages = {\#R29}, primaryClass = {math}, title = {Kasteleyn cokernels}, volume = {9}, year = {2002} } @article{Deift1983, abstract = {It is proved that the determinant of the adjacency matrix for a finite subgraph G of Z × Z is 1, 0, or -1, provided that G has no "holes.". {\textcopyright} 1983.}, author = {Deift, P. A. and Tomei, C}, doi = {10.1016/0095-8956(83)90054-0}, issn = {10960902}, journal = {Journal of Combinatorial Theory, Series B}, month = dec, number = {3}, pages = {278--289}, publisher = {Academic Press}, title = {On the determinant of the adjacency matrix for a planar sublattice}, volume = {35}, year = {1983} } @article{Tomei2002, abstract = {Given an m × n rectangular mesh, its adjacency matrix A, having only integer entries, may be interpreted as a map between vector spaces over an arbitrary field K. We describe the kernel of A: it is a direct sum of two natural subspaces whose dimensions are equal to ⌈c/2⌉ and ⌊c/2⌋, where c = gcd(m +1, n +1 ) - 1. We show that there are bases to both vector spaces, with entries equal to 0, 1 and -1. When K = ℤ/(2), the kernel elements of these subspaces are described by rectangular tilings of a special kind. As a corollary, we count the number of tilings of a rectangle of integer sides with a specified set of tiles.}, author = {Tomei, C. and Vieira, T.}, doi = {10.1007/s00454-002-2819-z}, journal = {Discrete and Computational Geometry}, month = aug, number = {3}, pages = {411--425}, publisher = {Springer-Verlag}, title = {The kernel of the adjacency matrix of a rectangular mesh}, volume = {28}, year = {2002} } @article{Propp2005, abstract = {This article, based on joint work with Gabriel Carroll, Andy Itsara, Ian Le, Gregg Musiker, Gregory Price, Dylan Thurston, and Rui Viana, presents a combinatorial model based on perfect matchings that explains the symmetries of the numerical arrays that Conway and Coxeter dubbed frieze patterns. This matchings model is a combinatorial interpretation of Fomin and Zelevinsky's cluster algebras of type A. One can derive from the matchings model an enumerative meaning for the Markoff numbers, and prove that the associated Laurent polynomials have positive coefficients as was conjectured (much more generally) by Fomin and Zelevinsky. Most of this research was conducted under the auspices of REACH (Research Experiences in Algebraic Combinatorics at Harvard).}, archivePrefix = {arXiv}, author = {Propp, James}, month = nov, primaryClass = {math}, title = {The combinatorics of frieze patterns and Markoff numbers}, year = {2005} } @article{Housley2015, abstract = {We study natural bases for two constructions of the irreducible representation of the symmetric group corresponding to [n, n, n]: the reduced web basis associated to Kuperberg's combinatorial description of the spider category; and the left cell basis for the left cell construction of Kazhdan and Lusztig. In the case of [n, n], the spider category is the Temperley-Lieb category; reduced webs correspond to planar matchings, which are equivalent to left cell bases. This paper compares the image of these bases under classical maps: the Robinson-Schensted algorithm between permutations and Young tableaux and Khovanov-Kuperberg's bijection between Young tableaux and reduced webs. One main result uses Vogan's generalized $\tau$-invariant to uncover a close structural relationship between the web basis and the left cell basis. Intuitively, generalized $\tau$-invariants refine the data of the inversion set of a permutation. We define generalized $\tau$-invariants intrinsically for Kazhdan-Lusztig left cell basis elements and for webs. We then show that the generalized $\tau$-invariant is preserved by these classical maps. Thus, our result allows one to interpret Khovanov-Kuperberg's M. 123 294 J Algebr Comb (2015) 42:293-329 bijection as an analogue of the Robinson-Schensted correspondence. Despite all of this, our second main result proves that the reduced web and left cell bases are inequiv-alent; that is, these bijections are not S 3n-equivariant maps.}, archivePrefix = {arXiv}, author = {Housley, Matthew and Russell, Heather M. and Tymoczko, Julianna}, doi = {10.1007/s10801-015-0582-5}, isbn = {1080101505825}, issn = {15729192}, journal = {Journal of Algebraic Combinatorics}, keywords = {Kazhdan–Lusztig basis,Robinson–Schensted correspondence,Sl(3) web basis,Tau invariant}, number = {1}, pages = {293--329}, title = {The Robinson–Schensted correspondence and A2-web bases}, volume = {42}, year = {2015} } @article{Benkart2014, abstract = {The nonelliptic {\$}\backslashmathsf{A{\_}2}{\$}-webs with {\$}k{\$} "{\$}+{\$}"s on the top boundary and {\$}3n-2k{\$} "{\$}-{\$}"s on the bottom boundary combinatorially model the space {\$}\backslashmathsf{Hom}{\_}{\backslashmathfrak{sl}{\_}3}(\backslashmathsf{V}{\^{}}{\backslashotimes (3n-2k)}, \backslashmathsf{V}{\^{}}{\backslashotimes k}){\$} of {\$}\backslashmathfrak{sl}{\_}3{\$}-module maps on tensor powers of the natural {\$}3{\$}-dimensional {\$}\backslashmathfrak{sl}{\_}3{\$}-module {\$}\backslashmathsf{V}{\$}, and they have connections with the combinatorics of Springer varieties. Petersen, Pylyavskyy, and Rhodes showed that the set of such {\$}\backslashmathsf{A{\_}2}{\$}-webs and the set of semistandard tableaux of shape {\$}(3{\^{}}n){\$} and type {\$}\backslash{1{\^{}}2,\backslashdots,k{\^{}}2,k+1,\backslashdots, 3n-k\backslash}{\$} have the same cardinalities. In this work, we use the {\$}\backslashsf{m}{\$}-diagrams introduced by Tymoczko and the Robinson-Schensted correspondence to construct an explicit bijection, different from the one given by Russell, between these two sets. In establishing our result, we show that the pair of standard tableaux constructed using the notion of path depth is the same as the pair constructed from applying the Robinson-Schensted correspondence to a {\$}3\backslash,2\backslash,1{\$}-avoiding permutation. We also obtain a bijection between such pairs of standard tableaux and Westbury's {\$}\backslashmathsf{A{\_}2}{\$} flow diagrams.}, author = {Benkart, Georgia and Cho, Soojin and Moon, Dongho}, journal = {Electronic Journal of Combinatorics}, title = {The combinatorics of A2-webs}, year = {2014} } @article{Tymoczko2010, abstract = {Combinatorial spiders are a model for the invariant space of the tensor product of representations. The basic objects, webs, are certain directed planar graphs with boundary; algebraic operations on representations correspond to graph-theoretic operations on webs. Kuperberg developed spiders for rank 2 Lie algebras and sl{\_}2. Building on a result of Kuperberg's, Khovanov-Kuperberg found a recursive algorithm giving a bijection between standard Young tableaux of shape (n,n,n) and irreducible webs for sl{\_}3 whose boundary vertices are all sources. In this paper, we give a simple and explicit map from standard Young tableaux of shape (n,n,n) to irreducible webs for sl{\_}3 whose boundary vertices are all sources, and show that it is the same as Khovanov-Kuperberg's map. Our construction generalizes to some webs with both sources and sinks on the boundary. Moreover, it allows us to extend the correspondence between webs and tableaux in two ways. First, we provide a short, geometric proof of Petersen-Pylyavskyy-Rhoades's recent result that rotation of webs corresponds to jeu-de-taquin promotion on (n,n,n) tableaux. Second, we define another natural operation on tableaux called a shuffle, and show that it corresponds to the join of two webs. Our main tool is an intermediary object between tableaux and webs that we call an m-diagram. The construction of m-diagrams, like many of our results, applies to shapes of tableaux other than (n,n,n).}, archivePrefix = {arXiv}, author = {Tymoczko, Julianna}, month = may, title = {A simple bijection between standard (n,n,n) tableaux and irreducible webs for sl{\_}3}, year = {2010} } @article{Baur2016, abstract = {We associate a dimer algebra A to an alternating strand diagram D (in a disk), corresponding to a cluster of minors in the cluster structure of the Grassmannian Gr(k,n). We show that A is isomorphic to the endomorphism algebra of a corresponding maximal Cohen-Macaulay module over the algebra B used to categorify the cluster structure of Gr(k,n) by Jensen-King-Su. It follows that B can be realised as the boundary algebra of A, that is, the subalgebra eAe for an idempotent e corresponding to the boundary of the disk. The construction and proof uses an interpretation of the diagram D, with its associated plabic graph and dual quiver (with faces), as a dimer model with boundary. We also discuss the general surface case, in particular computing boundary algebras associated to the annulus.}, author = {Baur, Karin and King, Alastair D. and Marsh, Robert J.}, doi = {10.1112/plms/pdw029}, journal = {Proceedings of the London Mathematical Society}, title = {Dimer models and cluster categories of Grassmannians}, year = {2016} } @article{Kenyon1999, author = {Kenyon, Richard W. and Propp, James G. and Wilson, David B.}, journal = {The Electronic Journal of Combinatorics}, keywords = {spanning trees; square grid; perfect matchings; dimer coverings; planar graph}, number = {1}, pages = {\#R25}, publisher = {Prof. André Kündgen, Deptartment of Mathematics, California State University San Marcos, San Marcos}, title = {Trees and matchings.}, url = {http://eudml.org/doc/120355}, volume = {7}, year = {2000}, } @article{Yan2005, abstract = {The method of graphical vertex-condensation for enumerating perfect matchings of plane bipartite graph was found by Propp [Generalized Domino-shuffling, Theoret. Comput. Sci. 303 (2003) 267-301], and was generalized by Kuo [Applications of graphical condensation for enumerating matchings and tilings, Theoret. Comput. Sci. 319 (2004) 29-57] and Yan and Zhang [Graphical condensation for enumerating perfect matchings, J. Combin. Theory Ser. A 110 (2005) 113-125]. In this paper, by a purely combinatorial method some explicit identities on graphical vertex-condensation for enumerating perfect matchings of plane graphs (which do not need to be bipartite) are obtained. As applications of our results, some results on graphical edge-condensation for enumerating perfect matchings are proved, and we count the sum of weights of perfect matchings of weighted Aztec diamond. {\textcopyright} 2005 Elsevier B.V. All rights reserved.}, author = {Yan, Weigen and Yeh, Yeong-Nan and Zhang, Fuji}, doi = {10.1016/j.tcs.2005.09.039}, issn = {03043975}, journal = {Theoretical Computer Science}, month = dec, number = {3}, pages = {452--461}, title = {Graphical condensation of plane graphs: A combinatorial approach}, volume = {349}, year = {2005} } @article{Berman1981, abstract = {It is shown that in a 0-sum Boolean weighted graph G the sum of the weights taken over all the spanning trees equals the sum of the weights taken over all the perfect matchings in the graph G - v, where v is any vertex of G. Several related theorems are proved which include parity results on perfect matchings and spanning trees in Eulerian graphs. The ideas on perfect matchings in 0-sum Boolean weighted graphs are generalized to matchings in any Boolean weighted graph. {\textcopyright} 1981.}, author = {Berman, Kenneth A.}, doi = {10.1016/0095-8956(81)90051-4}, issn = {10960902}, journal = {Journal of Combinatorial Theory, Series B}, number = {3}, pages = {343--350}, title = {Matchings and spanning trees in Boolean weighted graphs}, volume = {30}, year = {1981} } @article{Marsh2016, abstract = {The homogeneous coordinate ring of the Grassmannian Gr(k,n) has a cluster structure defined in terms of planar diagrams known as Postnikov diagrams. The cluster corresponding to such a diagram consists entirely of Pluecker coordinates. We introduce a twist map on Gr(k,n), related to the BFZ-twist, and give an explicit Laurent expansion for the twist of an arbitrary Pluecker coordinate, in terms of the cluster variables associated with a fixed Postnikov diagram. The expansion arises as a (scaled) dimer partition function of a weighted version of the bipartite graph dual to the Postnikov diagram, modified by a boundary condition determined by the Pluecker coordinate.}, author = {Marsh, R. J. and Scott, J. S.}, doi = {10.1007/s00220-015-2493-7}, journal = {Communications in Mathematical Physics}, title = {Twists of Pl{\"{u}}cker Coordinates as Dimer Partition Functions}, year = {2016} } @article{John2000, abstract = {This is a contribution to the number theory of the dimer problem. Let An = 2nB2n (Bn {\textgreater} 0) denote the number of dimer coverings (i.e., perfect matchings) of a 2n × 2n square lattice graph. Bn turns out to be an integer. Motivated by a somewhat strange observation (see below), we investigated the residue classes Bn mod 2r. In this paper, we outline a method that, for a fixed integer r, enables these residue classes to be determined. Explicitly, Bn mod 64 is calculated and from the resulting formula the following proposition is deduced: Bn≡{n + 1 (mod 32) if n is even, (-1)(n-1)/2n(mod 32) if n is odd. The analogous statement mod 64 is not true: B3 = 29 is a counterexample. {\textcopyright} 2000 Elsevier Science B.V. All rights reserved.}}, author = {John, Peter E. and Sachs, Horst}, doi = {10.1016/S0012-365X(99)00301-5}, issn = {0012365X}, journal = {Discrete Mathematics}, number = {1-3}, pages = {211--219}, title = {On a strange observation in the theory of the dimer problem}, volume = {216}, year = {2000} } @article{Stanley1985, abstract = {For fixed k let Andenote the number of dimer coverings of a k × n rectangle. Various properties of the generating function $\Sigma$ Anxnare obtained, in particular answering questions of Klarner and Pollack and of Hock and McQuistan. An explicit expression for the molecular freedom for dimers on a saturated k × n lattice space is also obtained. The results are consequences of the explicit formula for Anobtained by Kasteleyn and by Temperley and Fisher. {\textcopyright} 1985.}, author = {Stanley, Richard P.}, doi = {10.1016/0166-218X(85)90042-3}, isbn = {0945-1129}, issn = {0166218X}, journal = {Discrete Applied Mathematics}, month = sep, number = {1}, pages = {81--87}, publisher = {North-Holland}, title = {On dimer coverings of rectangles of fixed width}, volume = {12}, year = {1985} } @article{Propp2001, abstract = {Let T(m,n) denote the number of ways to tile an m-by-n rectangle with dominos. For any fixed m, the numbers T(m,n) satisfy a linear recurrence relation, and so may be extrapolated to negative values of n; these extrapolated values satisfy the relation T(m,-2-n) = epsilonm,n T(m,n), where epsilonm,n is -1 if m is congruent to 2 (mod 4) and n is odd, and is +1 is otherwise. This is equivalent to a fact demonstrated by Stanley using algebraic methods. Here I give a proof that provides, among other things, a uniform combinatorial interpretation of T(m,n) that applies regardless of the sign of n.}, archivePrefix = {arXiv}, author = {Propp, James}, issn = {10778926}, journal = {Electronic Journal of Combinatorics}, month = apr, number = {1 R}, pages = {1--9}, primaryClass = {arXiv:math}, title = {A reciprocity theorem for domino tilings}, volume = {8}, year = {2001} } @article{Eppstein1996, abstract = {Any bipartite Eulerian graph, any Eulerian graph with evenly many ver-tices, and any bipartite graph with evenly many vertices and edges, has an even number of spanning trees. More generally, a graph has evenly many spanning trees if and only if it has an Eulerian edge cut.}, author = {Eppstein, David}, journal = {Work}, title = {On the Parity of Graph Spanning Tree Numbers}, year = {1996} } @misc{Kuo2006, author = {Kuo, E}, eprint={math/0605154}, number = {1}, pages = {1--12}, primaryClass = {arXiv:math}, title = {Graphical condensation generalizations involving Pfaffians and determinants}, year = {2006} } @article{Yan2004, abstract = {The Pfaffian method enumerating perfect matchings of plane graphs was discovered by Kasteleyn. We use this method to enumerate perfect matchings in a type of graphs with reflective symmetry which is different from the symmetric graphs considered in [J. Combin. Theory Ser. A 77 (1997) 67, MATCH - Commun. Math. Comput. Chem. 48 (2003) 117]. Here are some of our results: (1) If G is a reflective symmetric plane graph without vertices on the symmetry axis, then the number of perfect matchings of G can be expressed by a determinant of order G /2, where G denotes the number of vertices of G. (2) If G contains no subgraph which is, after the contraction of at most one cycle of odd length, an even subdivision of K2,3, then the number of perfect matchings of G × K2can be expressed by a determinant of order G . (3) Let G be a bipartite graph without cycles of length 4s, s ∈ {1, 2,...}. Then the number of perfect matchings of G × K2equals $\Pi$(1 + $\theta$2)m$\theta$, where the product ranges over all non-negative eigenvalues $\theta$ of G and m$\theta$is the multiplicity of eigenvalue $\theta$. Particularly, if T is a tree then the number of perfect matchings of T × K2equals $\Pi$(1 + $\theta$2)m$\theta$, where the product ranges over all non-negative eigenvalues $\theta$ of T and m$\theta$is the multiplicity of eigenvalue $\theta$. {\textcopyright} 2003 Elsevier Inc. All rights reserved.}, author = {Yan, Weigen and Zhang, Fuji}, doi = {10.1016/S0196-8858(03)00097-6}, issn = {01968858}, journal = {Advances in Applied Mathematics}, keywords = {Bipartite graph,Even subdivision,Nice cycle,Outerplanar graph,Perfect matchings,Pfaffian orientation,Skew adjacency matrix,Symmetric graph}, number = {4}, pages = {655--668}, title = {Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians}, volume = {32}, year = {2004} } @article{Liu2002, abstract = {A matching of a graph is a near-perfect matching if it covers all but one vertex. A connected graph G is said to be factor-critical if G−v has perfect matchings for every vertex v of G. In this paper, the enumeration problems for near-perfect matchings in special factor-critical graphs are solved. From this, the exact values of the number of perfect matchings in special bicritical graphs are obtained.}, author = {Liu, Yan and Hao, Jianxiu}, doi = {http://dx.doi.org/10.1016/S0012-365X(01)00204-7}, issn = {0012-365X}, journal = {Discrete Mathematics}, keywords = {Bicritical graph,Factor-critical graph,Near-perfect matching}, number = {1-3}, pages = {259--266}, title = {The enumeration of near-perfect matchings of factor-critical graphs}, volume = {243}, year = {2002} } @article{Lis2017, abstract = {A matrix is called totally positive (resp. totally nonnegative) if all its minors are positive (resp. nonnegative). Consider the Ising model with free boundary conditions and no external field on a planar graph {\$}G{\$}. Let {\$}a{\_}1,\backslashdots,a{\_}k,b{\_}k,\backslashdots,b{\_}1{\$} be vertices placed in a counterclockwise order on the outer face of {\$}G{\$}. We show that the {\$}k\backslashtimes k{\$} matrix of the two-point spin correlation functions $\backslash$[ M{\_}{i,j} = $\backslash$langle $\backslash$sigma{\_}{a{\_}i} $\backslash$sigma{\_}{b{\_}j} $\backslash$rangle $\backslash$] is totally nonnegative. Moreover, {\$}\backslashdet M {\textgreater} 0{\$} if and only if there exist {\$}k{\$} pairwise vertex-disjoint paths that connect {\$}a{\_}i{\$} with {\$}b{\_}i{\$}. We also compute the scaling limit at criticality of the probability that there are {\$}k{\$} parallel and disjoint connections between {\$}a{\_}i{\$} and {\$}b{\_}i{\$} in the double random current model. Our results are based on a new distributional relation between double random currents and random alternating flows of Talaska.}, author = {Lis, Marcin}, doi = {10.1007/s10955-016-1690-x}, journal = {Journal of Statistical Physics}, title = {The Planar Ising Model and Total Positivity}, year = {2017} } @article{Postnikov2006, abstract = {The aim of this paper is to discuss a relationship between total positivity and planar directed networks. We show that the inverse boundary problem for these networks is naturally linked with the study of the totally nonnegative Grassmannian. We investigate its cell decomposition, where the cells are the totally nonnegative parts of the matroid strata. The boundary measurements of networks give parametrizations of the cells. We present several different combinatorial descriptions of the cells, study the partial order on the cells, and describe how they are glued to each other.}, archivePrefix = {arXiv}, author = {Postnikov, Alexander}, month = sep, primaryClass = {math}, title = {Total positivity, Grassmannians, and networks}, year = {2006} } @article{Feng-Gen2009, abstract = {The importance of Pfaffian orientations stems from the fact that if a graph G is Pfaffian, the number of perfect matchings of G (as well as other related problems) can be computed polynomial time. Although there are many equivalent conditions for the existence a Pfaffian orientation of a graph, this property is not well-characterized. The problem is no polynomial algorithm is known for checking whether or not a given orientation of a is Pfaffian. Similarly, we do not know whether this property of an undirected graph it has a Pfaffian orientation is in NP. It is well known that the enumeration problem perfect matchings for general graphs is NP-hard. L. Lov́asz pointed out that it makes not only to seek good upper and lower bounds of the number of perfect matchings general graphs, but also to seek special classes for which the problem can be solved . For a simple graph G and a cycle C n with n vertices (or a path P n with n vertices), define C n (or P n )×excl;¿G as the Cartesian product of graphs C n (or P n ) and G. In the present , we construct Pfaffian orientations of graphs C 4 ×excl;¿ G, P 4 ×excl;¿ G and P 3 ×excl;¿ G, where G is a non bipartite graph with a unique cycle, and obtain the explicit formulas in terms of of the skew adjacency matrix of -?excl;{\ae}G to enumerate their perfect matchings by Pfaffian approach, where excl;{\ae}G is an arbitrary orientation of G.}, author = {Feng-Gen, Lin and Lian-Zhu, Zhang}, journal = {Electronic Journal of Combinatorics}, title = {Pfaffian orientation and enumeration of perfect matchings for some Cartesian products of graphs}, year = {2009} } @article{Kuo2004, abstract = {A technique called graphical condensation is used to prove various combinatorial identities among numbers of (perfect) matchings of planar bipartite graphs and tilings of regions. Graphical condensation involves superimposing matchings of a graph onto matchings of a smaller subgraph, and then re-partitioning the united matching (actually a multigraph) into matchings of two other subgraphs, in one of two possible ways. This technique can be used to enumerate perfect matchings of a wide variety of planar bipartite graphs. Applications include domino tilings of Aztec diamonds and rectangles, diabolo tilings of fortresses, plane partitions, and transpose complement plane partitions. {\textcopyright} 2004 Elsevier B.V. All rights reserved.}, archivePrefix = {arXiv}, author = {Kuo, Eric H.}, doi = {10.1016/j.tcs.2004.02.022}, issn = {03043975}, journal = {Theoretical Computer Science}, keywords = {Generating functions,Perfect matchings,Plane partitions,Tilings}, number = {1-3}, pages = {29--57}, primaryClass = {math}, title = {Applications of graphical condensation for enumerating matchings and tilings}, volume = {319}, year = {2004} } @article{Godsil2017, abstract = {In this paper we give a proof that the largest set of perfect matchings, in which any two contain a common edge, is the set of all perfect matchings that contain a fixed edge. This is a version of the famous Erd$\backslash$H{o}s-Ko-Rado theorem for perfect matchings. The proof given in this paper is algebraic, we first determine the least eigenvalue of the perfect matching derangement graph and use properties of the perfect matching polytope. We also prove that the perfect matching derangement graph is not a Cayley graph.}, author = {Godsil, Chris and Meagher, Karen}, journal = {Ars Mathematica Contemporanea}, title = {An algebraic proof of the Erdos-Ko-Rado theorem for intersecting families of perfect matchings}, year = {2017} } @article{Kuperberg1996, author = {Kuperberg, Greg}, doi = {10.1007/BF02101184}, issn = {0010-3616}, journal = {Communications in Mathematical Physics}, month = sep, number = {1}, pages = {109--151}, publisher = {Springer-Verlag}, title = {Spiders for rank 2 Lie algebras}, volume = {180}, year = {1996} } @article{Tong2014, abstract = {We introduce a class of graphs called compound graphs, generalizing rectangles, which are constructed out of copies of a planar bipartite base graph. The main result is that the number of perfect matchings of every compound graph is divisible by the number of matchings of its base graph. Our approach is to use Kasteleyn's theorem to prove a key lemma, from which the divisibility theorem follows combinatorially. This theorem is then applied to provide a proof of Problem 21 of Propp's Enumeration of Matchings, a divisibility property of rectangles. Finally, we present a new proof, in the same spirit, of Ciucu's factorization theorem.}, archivePrefix = {arXiv}, author = {Tong, Forest}, issn = {10778926}, journal = {Electronic Journal of Combinatorics}, month = jun, number = {3}, title = {Generalizing the divisibility property of rectangle domino tilings}, volume = {23}, year = {2016} } @article{Rhoades2005, author = {Rhoades, Brendon and Skandera, Mark}, doi = {10.1007/s00026-005-0268-0}, issn = {0218-0006}, journal = {Annals of Combinatorics}, keywords = {Temperley-Lieb algebra,immanant,matrix minor,total nonnegativity}, month = dec, number = {4}, pages = {451--494}, publisher = {Birkh{\"{a}}user-Verlag}, title = {Temperley-Lieb Immanants}, volume = {9}, year = {2005} } @article{Pylyavskyy2010, abstract = {We describe the rank 3 Temperley–Lieb–Martin algebras in terms of Kuperberg's A2-webs. We define consistent labelings of webs and use them to describe the coefficients of decompositions into reduced webs. We introduce web immanants, inspired by Temperley–Lieb immanants of Rhoades and Skandera. We show that web immanants are positive when evaluated on totally positive matrices and describe some further properties.}, author = {Pylyavskyy, Pavlo}, doi = {10.1016/J.DISC.2010.04.008}, issn = {0012-365X}, journal = {Discrete Mathematics}, month = aug, number = {15-16}, pages = {2183--2197}, publisher = {North-Holland}, title = {A2-web immanants}, volume = {310}, year = {2010} } @article{Propp1999, abstract = {This document is built around a list of thirty-two problems in enumeration of matchings, the first twenty of which were presented in a lecture at MSRI in the fall of 1996. I begin with a capsule history of the topic of enumeration of matchings. The twenty original problems, with commentary, comprise the bulk of the article. I give an account of the progress that has been made on these problems as of this writing, and include pointers to both the printed and on-line literature; roughly half of the original twenty problems were solved by participants in the MSRI Workshop on Combinatorics, their students, and others, between 1996 and 1999. The article concludes with a dozen new open problems. (Note: This article supersedes math.CO/9801060 and math.CO/9801061.)}, archivePrefix = {arXiv}, author = {Propp, J.}, isbn = {0-521-77087-4/pbk}, journal = {New Perspectives in Geometric Combinatorics}, month = apr, pages = {255--291}, primaryClass = {arXiv:math.CO}, title = {Enumeration of Matchings: Problems and Progress}, volume = {38}, year = {1999} } @article{Lam2015, abstract = {We study the dimer model for a planar bipartite graph N embedded in a disk, with boundary vertices on the boundary of the disk. Counting dimer configurations with specified boundary conditions gives a point in the totally nonnegative Grassmannian. Considering pairing probabilities for the double-dimer model gives rise to Grassmann analogues of Rhoades and Skandera's Temperley-Lieb immanants. The same problem for the (probably novel) triple-dimer model gives rise to the combinatorics of Kuperberg's webs and Grassmann analogues of Pylyavskyy's web immanants. This draws a connection between the square move of plabic graphs (or urban renewal of planar bipartite graphs), and Kuperberg's square reduction of webs. Our results also suggest that canonical-like bases might be applied to the dimer model. We furthermore show that these functions on the Grassmannian are compatible with restriction to positroid varieties. Namely, our construction gives bases for the degree two and degree three components of the homogeneous coordinate ring of a positroid variety that are compatible with the cyclic group action.}, archivePrefix = {arXiv}, author = {Lam, Thomas}, doi = {10.1112/jlms/jdv039}, issn = {14697750}, journal = {Journal of the London Mathematical Society}, number = {3}, pages = {633--656}, title = {Dimers, webs, and positroids}, volume = {92}, year = {2015} } @article{Fraser2017, title = {From dimers to webs}, volume = {371}, issn = {0002-9947, 1088-6850}, opturl = {http://www.ams.org/tran/2019-371-09/S0002-9947-2019-07641-9/}, doi = {10.1090/tran/7641}, number = {9}, journal = {Transactions of the American Mathematical Society}, author = {Fraser, Chris and Lam, Thomas and Le, Ian}, month = jan, year = {2019}, pages = {6087--6124} } @article{Farber2016, abstract = {We discuss arrangements of equal minors of totally positive matrices. More precisely, we investigate the structure of equalities and inequalities between the minors. We show that arrangements of equal minors of largest value are in bijection with sorted sets, which earlier appeared in the context of alcoved polytopes and Gr{\"{o}}bner bases. Maximal arrangements of this form correspond to simplices of the alcoved triangulation of the hypersimplex; and the number of such arrangements equals the Eulerian number. On the other hand, we prove in many cases that arrangements of equal minors of smallest value are weakly separated sets. Weakly separated sets, originally introduced by Leclerc and Zelevinsky, are closely related to the positive Grassmannian and the associated cluster algebra. However, we also construct examples of arrangements of smallest minors which are not weakly separated using chain reactions of mutations of plabic graphs.}, archivePrefix = {arXiv}, author = {Farber, Miriam and Postnikov, Alexander}, doi = {10.1016/j.aim.2016.03.031}, issn = {10902082}, journal = {Advances in Mathematics}, keywords = {Alcoved polytopes,Arrangements of equal minors,Chain reactions of mutations,Cluster algebras and plabic graphs,Gr{\"{o}}bner bases,Matrix completion problem,Minors and Pl{\"{u}}cker coordinates,Mutation distance,Schur positivity,The Eulerian numbers,The Laurent phenomenon,The affine Coxeter arrangement,The positive Grassmannian,Totally positive matrices,Triangulations and thrackles,Weakly separated and sorted sets,honeycombs,hypersimplices}, pages = {788--834}, title = {Arrangements of equal minors in the positive Grassmannian}, volume = {300}, year = {2016} }