Research

Enumeration of tilings is the mathematical study concerning the total number of coverings of regions by similar pieces without gaps or overlaps.  Enumeration of tilings has become a vibrant subfield of combinatorics with connections and applications to diverse mathematical areas.  In 1999, James Propp published his well-known list of 32 open problems in the field. The list has got much attention from experts around the world. After two decades, most of the problems on the list have been solved. In this paper, we propose a new set of tiling problems. This survey paper contributes to the Open Problems in Algebraic Combinatorics 2022 conference (OPAC 2022) at the University of Minnesota.

Available on the website of the conference. Preprint arXiv:2109.01466.

This is a series of papers with Hyun Byun about lozenge tilings of hexagons with intrusions. The paper has been available on arXiv:  arXiv:2211.08220 

MacMahon's classical theorem on the number of boxed plane partitions has been generalized in several directions. One way to generalize the theorem is to view boxed plane partitions as lozenge tilings of a hexagonal region and then generalize it by making some holes in the region and counting its tilings. In this paper, we provide new regions whose numbers of lozenges tilings are given by simple product formulas. The regions we consider can be obtained from hexagons by removing structures called intrusions. In fact, we show that the tiling-generating functions of those regions under certain weights are given by similar formulas. These give the q-analog of the enumeration results.

We investigate a connection between perfect matchings of families of six-sided graphs and cluster variables arising from sequences of toric mutation in the dP3 quiver. The project could be divided into three parts:

Part 1 (with Gregg Musiker) has been published as  "Beyond Aztec Castles: Toric Cascades in the dP3 Quiver", Communications in Mathematical Physics, Volume 356, Issue 3 (2017), pp. 823-881.  Preprint arXiv:1512.00507v2

We consider the dP3 quiver and construct a family of subgraphs of the brane tiling restricted by certain 6-sided oriented contours (the direction of the contour depends on its `signed side-lengths'). Our family of graphs generalizes many known families, including the Aztec Dragons, Aztec Castles, and Dragon regions. We showed that the weighted sums of perfect matchings of our graphs are equal to cluster variables arising from sequences of toric mutations in the dP3 quiver. Moreover, the latter cluster variable can be written as a closed-form product formula.

Part 2 (with Gregg Musiker) has been published as "Dungeons and Dragons: Combinatorics for the dP3 Quiver", Annals of Combinatorics, Volume 24 (2020), pp.257-309.  Preprint arXiv:1805.09280 .

In this paper, we utilize the machinery of cluster algebras, quiver mutations, and brane tilings to study a variety of historical enumerative combinatorics questions all under one roof. Previous work by the second author and REU students, and more recently of both authors, analyzed the cluster algebra associated with the cone over dP3, the del Pezzo surface of degree 6 (CP2 blown up at three points). By investigating sequences of toric mutations, those occurring only at vertices with two incoming and two outgoing arrows, in this cluster algebra, we obtained a family of cluster variables that could be parameterized by Z3 and whose Laurent expansions had elegant combinatorial interpretations in terms of dimer partition functions (in most cases). While the earlier work focused exclusively on one possible initial seed for this cluster algebra, there are in total four relevant initial seeds (up to graph isomorphism). In the current work, we explore the combinatorics of the Laurent expansions from these other initial seeds and how this allows us to relate enumerations of perfect matchings on Dungeons to Dragons.

Part 3 (with Gregg Musiker and Helen Jenne) focuses on proving our conjecture in Part 2 about the double-dimers of graphs with self-intersecting contours. This is still ongoing.

Inspired by Ciucu-Eisenkölbl-Krattenthaler-Zare's theorem, I investigated the tiling number of hexagons with three chains of triangular holes. This is an ultimate example of using Kuo condensation. I have used 60 different recurrences to prove more than 30 tiling formulas at once. This was originally a paper of more than 100 pages. However, the editor was recommended to break it into two papers.

Part 1 is Lozenge Tilings of Hexagons with Central Holes and Dents. Electronic Journal of Combinatorics, Volume 27, Issue 1 (2020), P1.61 (63 pages). Preprint arXiv:1803.02792.

Ciucu proved a simple product formula for the tiling number of a hexagon in which a chain of equilateral triangles of alternating orientations, called a `fern', has been removed from the center (Adv. Math. 2017). In this paper, we present a multi-parameter generalization of this work by giving an explicit tiling enumeration for a hexagon with three ferns removed, besides the central fern as in Ciucu's region, we remove two new ferns from two sides of the hexagon. Our result also implies a new `dual' of MacMahon's classical formula of boxed plane partitions, corresponding to the exterior of the union of three disjoint concave polygons obtained by turning 120 degrees after drawing each side.

Part 2  is Tiling Enumeration of Hexagons with Off-central Holes. Tiling Enumeration of Hexagons with Off-central Holes, Electronic Journal of Combinatorics, Volume 29, Issue 1 (2022), P.1.41 (76 pages). Preprint arXiv:1905.07119.

In the prequel of the paper ( arXiv:1803.02792), we considered exact enumerations of the cored versions of a doubly-intruded hexagon. The result generalized Ciucu's work about F-cored hexagons (Adv. Math. 2017). In this paper, we provide an extensive list of 30 tiling enumerations of hexagons with three collinear chains of triangular holes with alternating orientations. Besides two chains of holes attaching to the boundary of the hexagon, we remove one more chain of triangles that is slightly off the center of the hexagon. Two of our enumerations imply two conjectures posed by Ciucu, Eisenkölbl, Krattenthaler, and Zare (J. Combin. Theory Ser. A 2001) as two very special cases.

Changing a small parameter could lead to a dramatic change in the tiling number of the region. However, in some cases, the changes in the position of holes in a region only change the tiling number by a simple multiplicative factor. I realized the first instance of this phenomenon when discussing the tiling number of the hexagon with three chains of triangles removed with Dennis Stanton at the JMM in San Diego in 2019. There are many instances of shuffling phenomenon that have been found. 

A Shuffling Theorem for Lozenge Tilings of Doubly-Dented Hexagons (with Ranjan Rohatgi) (12 pages). Preprint arXiv:1905.08311.

MacMahon's theorem on plane partitions yields a simple product formula for the tiling number of a hexagon, and Cohn, Larsen, and Propp's theorem provides an explicit enumeration for tilings of a dented semihexagon via semi-strict Gelfand-Tsetlin patterns. In this paper, we prove a natural hybrid of the two theorems for hexagons with an arbitrary set of unit triangles removed along a horizontal axis. In particular, we show that `shuffling' removed unit triangles only changes the tiling number of the region by a simple multiplicative factor. Our main result generalizes a number of known enumerations and asymptotic enumerations of tilings. We also reveal connections between the main result and the study of symmetric functions and q-series.

A Shuffling Theorem for Centrally Symmetric Tilings. Preprint: arXiv:1906.03759.

In arXiv:1905.08311, Rohatgi and the author proved a shuffling theorem for lozenge tilings of doubly-dented hexagons. The theorem can be considered as a hybrid between two classical theorems in the enumeration of tilings: MacMahon's theorem about centrally symmetric hexagons and Cohn-Larsen-Prop's theorem about semihexagons with dents. In this paper, we consider a similar shuffling theorem for the centrally symmetric tilings of the doubly-dented hexagons. Our theorem generalizes a recent conjecture by Ciucu about centrally symmetric tiling of hexagons with `ferns' removed. Our theorem also implies a conjecture posed by the author in arXiv:1803.02792 about the enumeration of centrally symmetric tilings of hexagons with three arrays of triangular holes. This enumeration, in turn, generalizes (a tiling-equivalent version of) Stanley's enumeration of self-complementary plane partitions and Ciucu's work on symmetries of the shamrock structure.

Tilings of hexagons with a removed triad of bowties (with Mihai Ciucu and Ranjan Rohatgi) (30 pages) Journal of Combinatorial Theory, Series A, Volume 178 (2020), 105359 (online). ScienceDirect link. Preprint: arXiv:1909.04070.

 In this paper, we consider arbitrary hexagons on the triangular lattice with three arbitrary bowtie-shaped holes, whose centers form an equilateral triangle. The number of lozenge tilings of such general regions is not expected - and indeed is not - given by a simple product formula. However, when considering a certain natural normalized counterpart of any such region, we prove that the ratio between the number of tilings of the original and the number of tilings of the normalized region is given by a simple, conceptual product formula. Several seemingly unrelated previous results from the literature - including Lai's formula for hexagons with three dents and Ciucu and Krattenthaler's formula for hexagons with a removed shamrock - follow as immediate consequences of our result.

The closed form product formulas of plane partitions in many special shapes have been found. However, there is a missing piece in the picture: the plane partitions in a shifted double staircase shape. Sam Hopskins conjectured an elegant formula for this class of plane partitions. He reached out to me and we settled his conjecture in the paper:

Plane partitions of shifted double staircase shape (with Sam Hopkins) (23 pages), Journal of Combinatorial Theory, Series A, Volume 183 (2021), 105486. Preprint: arXiv:2007.05381.

We give a product formula for the number of shifted plane partitions of shifted double staircase shapes with bounded entries. This is the first new example of a family of shapes with a plane partition product formula in many years. The proof is based on the theory of lozenge tilings; specifically, we apply the "free boundary" Kuo condensation due to Ciucu.

This is a series of papers inspired by MacMahon's enumeration of boxed plane partitions. We view lozenge tilings of hexagons with defects as stacks of unit cubes fitting in certain connected rooms. We provide exact product formulas for the volume-generating functions of the stacks of cubes. 

Part 1 has been published as A q-enumeration of lozenge tilings of a hexagon with four adjacent triangles removed from the boundary, European Journal of Combinatorics, Volume 64 (2017), pp. 66-87. Preprint arXiv:1502.01679v4 .

MacMahon proved a simple product formula for the generating function of plane partitions fitting in a given box. The theorem implies a q-enumeration of lozenge tilings of a semi-regular hexagon on the triangular lattice. In this paper, we generalize MacMahon's classical theorem by q-enumerating lozenge tilings of a new family of hexagons with four adjacent triangles removed from their boundary.

Part 2 has been published as A q-enumeration of Lozenge Tilings of a Hexagon with Three Dents, Advances in Applied Mathematics, Volume 82 (2017), pp. 23-57. Preprint arXiv:1502.05780v5

We q-enumerate lozenge tilings of a hexagon from which three bowtie-shaped regions have been removed from three non-consecutive sides of the hexagon. The unweighted version of the result generalizes a problem posed by James Propp on enumeration of lozenge tilings of a hexagon of side-lengths 2n,2n+3,2n,2n+3,2n,2n+3 (in cyclic order) with the central unit triangles on the (2n+3)-sides removed.

Part 3 (with Mihai Ciucu) has been published as Lozenge Tilings of Doubly-intruded Hexagons (with Mihai Ciucu). Journal of Combinatorial Theory, Series A, Volume 167 (2019), pp. 294-339.  Preprint arXiv:1712.08024.

Motivated in part by Propp's intruded Aztec diamond regions, we consider hexagonal regions out of which two horizontal chains of triangular holes (called ferns) are removed, so that the chains are at the same height, and are attached to the boundary. By contrast with the intruded Aztec diamonds (whose number of domino tilings contain some large prime factors in their factorization), the number of lozenge tilings of our doubly-intruded hexagons turns out to be given by simple product formulas in which all factors are linear in the parameters. We present in fact q-versions of these formulas, which enumerate the corresponding plane-partitions-like structures by their volume. We also pose some natural statistical mechanics questions suggested by our set-up, which should be possible to tackle using our formulas.

Enumeration of lozenge tilings of a hexagon with a shamrock missing on the symmetry axis (with Ranjan Rohatgi), Discrete Mathematics, Volume 342, Issue 2 (2019), pp. 451-472. Preprint arXiv:1711.02818.

In their paper about a dual of MacMahon's classical theorem about plane partitions, Ciucu and Krattenthaler proved a closed form product formula for the tiling number of a hexagon with a ``shamrock", a union of four adjacent triangles, removed in the center (Proc. Natl. Acad. Sci. USA 2013). The first author later presented a nice q-enumeration for lozenge tilings of hexagons with a shamrock removed from the boundary ( arXiv:1502.01679 ). However, these are only two positions of the shamrock hole that yield nice tiling enumerations. In this paper, we show that in the case of symmetric hexagons, we always have a closed form tiling formula when removing a shamrock at any position along the symmetry axis. Our result also generalizes Eisenkölbl's work about lozenge tilings of a hexagon with two unit triangles missing on the symmetry axis ( Electron. J. Combin. 1999).

The paper has been selected as Discrete Mathematics Editor Choice 2019.

In 2015, Pavlo (Pasha) Pylyavskyy introduced an interesting conjecture by Kenyon and Wilson about a surprising connection between tilings and semicontiguous minors. I proved the conjecture in the paper: Proof of a Conjecture of Kenyon and Wilson on Semicontiguous Minors , Journal of Combinatorial Theory, Series A, Volume 161 (2019), pp. 134-163.  Preprint arXiv:1507.02611v6 .

In their paper on circular planar electrical networks ( arXiv:1411.7425 ), Kenyon and Wilson showed how to test if an electrical network with n nodes is well-connected by checking the positivity of n(n-1)/2 minors of the response matrix. In particular, they proved that any contiguous minor of a matrix can be expressed as a Laurent polynomial in the central minors. Interestingly, the Laurent polynomial is the generating function of domino tilings of an Aztec diamond weighted by the central minors. They conjectured that any semicontiguous minor can also be written in terms of domino tilings of a region on the square lattice. In this paper, we present a proof of the conjecture.

W. Thurston showed that any two domino tilings of a region can be connected by a sequence of flips of two parallel dominoes. Elkies, Kuperberg, Larsen, and Propp proved a simple product formula for the tiling-generating function of the Aztec Diamond for the number of Thurston's flips. I also investigated a similar generating function of various regions.

Generating Function of the Tilings of an Aztec Rectangle with Holes, Graphs and Combinatorics, Volume 32, Issue 3 (2016), pp. 1039-1054. Preprint arXiv:1402.0825v6

We consider a generating function of the domino tilings of an Aztec rectangle with several boundary unit squares removed. Our generating function involves two statistics: the rank of the tiling and half number of vertical dominoes as in the Aztec diamond theorem by Elkies, Kuperberg, Larsen and Propp. In addition, our work deduces a combinatorial explanation for an interesting connection between the number of lozenge tilings of a semihexagon and the number of domino tilings of an Aztec rectangle.

Double Aztec Rectangles, Advances in Applied Mathematics, Volume 75 (2016), pp. 1-17 Preprint arXiv:1411.0146v2

We investigate the connection between lozenge tilings and domino tilings by introducing a new family of regions obtained by attaching two different Aztec rectangles. We prove a simple product formula for the generating functions of the tilings of the new regions, which involves the statistics as in the Aztec diamond theorem (Elkies, Kuperberg, Larsen, and Propp, J. Algebraic Combin. 1992). Moreover, we consider the connection between the generating function and MacMahon's q-enumeration of plane partitions fitting in a given box.

In 1999, Jim Propp published a well-known list of 32 open tiling problems. Since 2014, most of the problems on the list have been solved. Only several stubborn ones were still open. One of them is the conjecture of Matt Blum on a striking pattern of a hexagonal version of the Aztec Dungeon, called  "Hexagonal Dungeon." Mihai Ciucu and I had managed to prove the conjecture using Kuo Condensation. This is the first time, we know that Kuo Condensation could be used to prove a hard conjecture in the field. After 10 years, Kuo Condensation has become one of the strongest methods in the field. I finished the proof in early 2012. However, for many reasons, the paper only got submitted 2 years later and was finally published as: 

Proof of Blum's Conjecture on Hexagonal Dungeons (with Mihai Ciucu), Journal of Combinatorial Theory, Series A, Volume 125, 2014, pp. 273-305. Available online at ScienceDirect or arXiv:1402.7257

Matt Blum conjectured that the number of tilings of the Hexagonal Dungeon of sides a, 2a, b, a, 2a, b (where b ≥ 2a) is 132a214⌊a2⁄2⌋(J. Propp, New Perspectives in Geometric Combinatorics, Cambridge University Press, 1999). In this paper, we present a proof for this conjecture using Kuo's Graphical Condensation Theorem (E. Kuo, Applications of Graphical Condensation for Enumerating Matchings and Tilings, Theoretical Computer Science, 2004).

After this paper, I have discovered many different versions of Blum's Hexagonal Dungeon in a series of papers:

• A Generalization of Aztec Dragons , Graphs and Combinatorics, Volume 32, Issue 5 (2016), pp. 1979-1999 Preprint arXiv:1504.00303 .

• Proof of a Refinement of Blum's Conjecture on Hexagonal Dungeons . Discrete Mathematics, Volume 340, Issue 7 (2017), pp. 1617-1632. Preprint arXiv:1403.4481v4.

• Perfect Matchings of Trimmed Aztec Rectangles. Electronic Journal of Combinatorics, Volume 24, Issue 4 (2017), #P4.19 (34 pages), Preprint arXiv: 1504.00291.

In 1999, Jim Propp published a well-known list of 32 open tiling problems. Since 2014, most of the problems on the list have been solved. Only several stubborn ones were still open. One of them is Problem 16 asking for the number of quasi-hexagonal regions, which is a natural hybrid of the Aztec diamond and the lozenge hexagon. I solved the problem and published it in the paper:

Enumeration of Hybrid Domino-Lozenge Tilings, Journal of Combinatorial Theory, Series A, Volume 122, 2014, pp. 53-81. Available online at ScienceDirect or arXiv:1309.5376

We solve and generalize an open problem posed by James Propp (Problem 16 in New Perspectives in Geometric Combinatorics, Cambridge University Press, 1999) on the number of tilings of quasi-hexagonal regions on the square lattice with every third diagonal drawn in. We also obtain a generalization of Douglas' Theorem on the number of tilings of a family of regions of the square lattice with every second diagonal drawn in.

After this paper, I used the method to find the tiling number of many different regions:

• Enumeration of Hybrid Domino-Lozenge Tilings II: Quasi-octagonal Regions, Electronic Journal of Combinatorics, Volume 23, Issue 2 (2016), P2.2 (25 pages). Preprint arXiv:1310.3332v4

• Enumeration of hybrid domino-lozenge tilings III: Symmetric tilings. Australasian Journal of Combinatorics, Volume 74, Issue 2 (2019), 253--287. Preprint arXiv:1609.03116

Dividing an Aztec diamond region by two zigzag paths passing its center, we get four quartered Aztec diamonds. Jockusch and Propp (in an unpublished work) found that the number of tilings of a quartered Aztec diamond is given by a simple product formula. The formula also counts antisymmetric monotone triangles. This inspired a series of papers of mine:

• A Simple Proof for the Number of Tilings of Quartered Aztec Diamonds, Electronic Journal of Combinatorics, Volume 21, Issue 1 (2014), P1.6 (13 pages). Available online at Combinatorics.org or arXiv:1309.6720

• Enumeration of tilings of quartered Aztec rectangles, Electronic Journal of Combinatorics, Volume 21, Issue 4 (2014), P4.46. (28 pages). Preprint arXiv:1403.4493v3

• A New Proof for the Number of Lozenge Tilings of Quartered Hexagons, Discrete Mathematics, Volume 338, Issue 11 (2015), pp. 1866-1872. Preprint arXiv:1410.8116v2

• Enumeration of Antisymmetric Monotone Triangles and Domino Tilings of Quartered Aztec Rectangles, Discrete Mathematics, Volume 339, Issue 5 (2016), pp. 1512-1518. Preprint arXiv:1410.8112v3

During my last months of graduate school, Larry Moss asked me about a problem arising from his research on logic. He converted the problem into a graph problem. I solved the problem using some construction with the chessboard. Larry later converted it to a better construction using binary string, and his postdoc, Jorg Endrullis generalized my result. We end up with the paper 

Majority Digraphs, Proceeding of the AMS, Volume 144, Number 9 (2016), pp. 3701-3715. Preprint arXiv:1509.07567.

Let α∈(0, 1). A majority-digraph is a finite simple graph G such that there exist finite sets Ag for g ∈ G with the following property: g → h iff "at least α of the Ag are Ah". That is, g → h iff |Ag ∩ Ah| > α|Ag|. We characterize majority-digraphs as the digraphs with the property that every directed cycle has a back-edge. This characterization is independent of α. When α= 1/2, we apply the result to obtain a result on the logic of assertions "most X are Y".

We are proving and generalizing Di Francesco's conjecture about an elegant product formula for the number of domino tilings of the Aztec triangle.

We investigate a nice phenomenon when the ratio of the numbers of standard and semi-standard Young tableaux of a skew shape is given by a simple product formula. A q-analog will also be provided.

We prove a simple product formula for the generating function for the domino tiling of Ciucu's cruciform region.