text:
# Internal Dynamics, Structure, and Formation of Dwarf Elliptical Galaxies: II. Rotating Versus Non-Rotating Dwarfs

## 1 Introduction

Dwarf elliptical (dE) galaxies are the dominant galaxy type in nearby galaxy clusters, accounting for more than 75% of all objects in these regions down to a limiting magnitude of $`M_V=14`$ (Bingelli, Sandage, & Tammann, 1988; Trentham & Tully, 2002). They are characterized by low effective surface brightness $`\mu _{V,\mathrm{eff}}>22`$ mag arcsec-2 and faint luminosities $`M_V18`$ (for a review see Ferguson & Binggeli, 1994). Unlike classical elliptical galaxies whose surface brightness profiles tend to be well fit by the de Vaucouleurs $`r^{1/4}`$ law (de Vaucouleurs, 1948), dEs have brightness profiles that are characterized by Sérsic profiles (Sérsic, 1968) with indices ranging between $`n=1`$–3 (where $`n=1`$ corresponds to an exponential law and $`n=4`$ to an $`r^{1/4}`$ law) making them appear more diffuse than classical ellipticals of the same total magnitude. A direct illustration of this is the discontinuity in surface brightness between dEs and the low luminosity end of classical elliptical galaxy sequence (Kormendy 1985; Bender, Burstein, & Faber 1992; however, see Graham & Guzman 2003).

Detailed studies of the internal dynamics of Local Group dEs have been carried out over the past two decades (e.g., Bender, Paquet, & Nieto, 1991), but, until recently, only integrated measurements were available for more distant dEs (Peterson & Caldwell, 1993). The number of dEs outside the Local Group with spatially-resolved measurements of internal kinematics has increased dramatically in the last few years (De Rijcke et al., 2001; Geha, Guhathakurta, & van der Marel, 2002; Pedraz et al., 2002; Simien & Prugniel, 2002). These observations have revealed an intriguing diversity of properties: several dEs in the Virgo and Fornax clusters appear to be roughly consistent with rotational flattening, while others have no detectable rotation similar to their Local Group counterparts (Bender et al., 1991). This range in rotation velocities is a newly found feature of cluster dEs that must be explained by theoretical models of their formation.

Formation scenarios for dE galaxies fall into two broad categories: (1) dEs are old, primordial objects, and (2) dEs have recently evolved or transformed from a progenitor galaxy population. Two independent lines of observational evidence favor the latter category. Primordial dwarf galaxies are expected to be less strongly clustered than massive galaxies in the context of hierarchical structure formation theories, whereas the dE-to-giant galaxy ratio is observed to be higher in regions of higher galaxy density (Ferguson & Sandage, 1991). The radial velocity distribution of galaxies in the Virgo Cluster suggests that dEs may be a recently accreted population (Bothun & Mould, 1988; Conselice, Gallagher, & Wyse, 2001).

From simulations, Moore, Lake, & Katz (1998) suggest that galaxy harassment in clusters can morphologically transform a spiral galaxy into a dE. Recent observations of embedded disks in a handful of Virgo and Fornax dEs support this model (Jerjen, Kalnajs, & Binggeli, 2000; Barazza, Binggeli, & Jerjen, 2002; De Rijcke et al., 2003). Galaxy harassment partially disrupts the rotational motion of the progenitor galaxy while increasing velocity dispersions, and is expected to result in a range of rotational velocities. It is yet unclear whether this scenario can reproduce the large fraction of dEs with extremely low rotational velocities (Geha et al., 2002). Another model suggests that gas-rich dwarf irregular and/or small spiral galaxies are transformed into dEs through the process of ram pressure stripping (Faber & Lin, 1983). In this case, dEs would be expected to largely retain the rotational properties of their progenitors. The degree of rotational support present in dE galaxies is thus a strong constraint on formation models.

We investigate whether or not dE properties such as morphology, stellar population, and local environment are correlated with the degree of internal rotation. A sample of 17 dEs in the Virgo Cluster forms the basis of this study. In § 2, we present Keck spectroscopy and imaging for eleven dEs and combine these observations with the six additional dEs previously presented in Geha et al. (2002). In § 3.1, we discuss the kinematic profiles of this sample and distinguish between rotating and non-rotating dEs. In §§ 3.23.4, respectively, we examine the position of the rotating and non-rotating sub-samples in the Fundamental Plane, study galaxy morphologies, and probe stellar populations using absorption-line-strength indices. In § 4, we compare the local environments of rotating and non-rotating dEs within the Virgo Cluster. Finally, in § 5, we argue that major axis rotation velocity appears to be uncorrelated with other internal properties and local environment for the dEs in our sample, and discuss the broader implications of these results.

Throughout this paper a Virgo Cluster true distance modulus of $`(mM)_0=30.92`$ is adopted, i.e., a distance of 15.3 Mpc, as determined by the Hubble Space TelescopeBased on observations with the NASA/ESA Hubble Space Telescope, obtained at the Space Telescope Science Institute, which is operated by the Association of Universities for Research in Astronomy, Inc., under NASA contract NAS 5-26555. (HST) Key Project on the extragalactic distance scale (Freedman et al., 2001). Line-of-sight extinction values are taken from Schlegel, Finkbeiner, & Davis (1998) assuming a standard Galactic reddening law with $`R_V=3.1`$.

## 2 Data

### 2.1 The Sample

We present Keck spectroscopy and imaging for eleven Virgo Cluster dE galaxies (in § 2.2 and § 2.3, respectively) and combine these with observations of an additional six Virgo Cluster dEs previously presented in Geha et al. (2002). This sample of 17 Virgo dEs is then analyzed together throughout the paper. The general properties of the full sample are listed in Table 1. The distribution of the dEs on the sky and in velocity space are shown in Figure 1. The galaxies lie primarily near the bright end of the dE luminosity function and were chosen to cover a range of ellipticities. All but three of the galaxies discussed in this paper were classified as “dE” by Bingelli, Sandage, & Tammann (1985). These three galaxies are included in our sample as they lie in the region of the Fundamental Plane typical for dEs (Figure 5). Two of these objects, VCC 1386 and VCC 1488, were classified as normal ellipticals with an uncertainty flag (E:), but are likely to be misclassified dEs. The third object, VCC 1036, was classified as a transition dE/dS0 galaxy; however, as we discuss in § 3.3, the presence of disks and other substructure may be fairly common among dEs. In several of our figures, we include two additional galaxies, VCC 1122 and VCC 1407 (Simien & Prugniel, 2002). These are the only other Virgo Cluster galaxies with published spatially-resolved internal kinematics outside our sample that are classified as “dE” by Bingelli et al. (1985).

### 2.2 Spectroscopy

Eleven dE galaxies were observed on 2002 March 10–11 using the Keck II 10-m telescope and the Echelle Spectrograph and Imager (ESI; Sheinis et al., 2002). The observing setup was identical to that for the six additional Virgo dEs presented in Geha et al. (2002). Observations were made in the echellette mode with continuous wavelength coverage over the range $`\lambda \lambda 3900`$$`11000\text{Å}`$ across 10 echelle orders with a spectral dispersion of 11.4 km s-1 pixel-1. The spectra were obtained through a $`0.75^{\prime \prime }\times 20^{\prime \prime }`$ slit, resulting in an instrumental resolution of 23 km s-1 (Gaussian sigma) over the entire spectrum. The slit was positioned on the major axis of each galaxy, with the galaxy’s center displaced $`5^{\prime \prime }`$ from the center of the slit along its $`20^{\prime \prime }`$ length. A summary of observing parameters is given in Table 2.

The ESI data were reduced using a combination of IRAF echelle and long-slit spectral reduction tasks. This is described in detail in Geha et al. (2002); a brief summary is given here. The sum of a bright calibration star exposure and a flat field exposure were used to trace a fiducial point and the ends of the slit for each of the 10 curved echelle orders. After overscan and dark frame subtraction, scattered light was subtracted from individual frames by fitting a smooth function to the areas outside the apertures corresponding to the echelle orders (as defined by the tracing of the slit ends). To preserve spatial information, the APALL task was used in “strip” mode to extract and rectify two-dimensional rectangular strips for each echelle order. The rectified orders for both data and calibration frames were then interpolated to a common spatial pixel scale of $`0.18^{\prime \prime }`$ per pixel. Data reduction was carried out on these rectified strips. Each strip was divided by its corresponding normalized flat-field image. Individual exposures were cleaned of cosmic rays and combined. Cosmic rays were easily distinguished from night sky lines even after the slight smearing caused by interpolation during the rectification process.

A two-dimensional wavelength solution was determined for each rectified echelle order from a combined Cu/Ar/Hg/Ne arc lamp spectrum. The wavelength solution was applied to the data (to render vertical lines of constant wavelength) using either a logarithmic wavelength interpolation scheme (with 11.4 km s-1 pixels) or linear interpolation (with $`0.2\text{Å}`$ pixels) for the kinematic and line strength analyses, respectively. The sky spectrum was determined for each combined frame from a $`2^{\prime \prime }`$-wide section near the end of the slit farthest from the galaxy center ($`r15^{\prime \prime }`$), and subtracted from the rest of the two-dimensional spectrum. The galaxy data were extracted into one-dimensional spectra in spatial (radial) bins to achieve a signal-to-noise level of $`\mathrm{S}/\mathrm{N}10`$ per pixel in all radial bins, while ensuring that the spatial bin size is at least as large as the FWHM of seeing during the observations ($`0.8^{\prime \prime }`$). The galaxy continuum flux in each order of each one-dimensional spectrum was then individually normalized to unity. Finally, the strips from the different echelle orders were combined, weighted by the noise frame, to create a single two-dimensional long-slit spectrum. The reddest and two bluest echelle orders were not included in the analysis due to low signal-to-noise; the final combined spectrum covers $`\lambda \lambda 48009200\text{Å}`$.

The mean line-of-sight velocity and velocity dispersion as a function of radius were determined using a pixel-fitting method described in van der Marel (1994). As demonstrated in Geha et al. (2002), internal velocity dispersions from this observing setup can be measured down to the instrumental resolution of 23 km s-1 with an accuracy of $`1`$%. Velocity profiles were recovered using template stars ranging in spectral type from G8III to M0III. The best fitting template stars, HD48433 and HD40460 (both K1III stars with \[Fe/H\] = $`0.13`$ and $`0.42`$ dex, respectively) were used to recover the velocity and velocity dispersion profiles presented in § 3.1.

### 2.3 Imaging

Imaging for the above spectroscopic dE sample came from two sources: archival HST Wide Field Planetary Camera 2 (WFPC2) images were available for five of the dEs, while the remaining six were imaged with ESI during our spectroscopic run. The WFPC2 data, first presented in Miller et al. (1998) and Stiavelli et al. (2001), consist of $`2\times 230`$-s WFPC2 images in the F555W ($`V`$) bandpass, except in the case of VCC 1261 where only archival WFPC2 F702W ($`R`$-band) imaging was available (Rest et al., 2001); photometric parameters for this galaxy were transformed to $`V`$-band assuming $`VR`$ = 0.5 (Prugniel & Heraudeau, 1998). The WFPC2 images were cleaned of cosmic rays and combined; instrumental magnitudes were calibrated to standard passbands using the transformations of Holtzman et al. (1995). The ground-based ESI images consist of $`2\times 200`$-s $`V`$-band exposures, with the seeing FWHM ranging between $`0.6^{\prime \prime }0.7^{\prime \prime }`$. In imaging mode, ESI has $`0.154^{\prime \prime }`$ pixels and a $`2^{}\times 8^{}`$ field-of-view. The ESI images were bias subtracted and flat fielded using twilight sky exposures. Photometric zero-points were determined based on observations of standard star fields taken on a different (but also photometric) night; our surface photometry and total magnitudes agree with previously published values.

Surface brightness profiles were determined for all galaxies using the IRAF ELLIPSE isophotal fitting routine (Jedrzejewski, 1987). Half-light effective radii ($`r_{\mathrm{eff}}`$) and effective surface brightnesses ($`\mu _{\mathrm{eff}}`$) were calculated by fitting a Sérsic profile of the form $`I(r)=I_0\mathrm{exp}[(r/r_0)^{1/n}]`$ to the observed $`V`$-band data. A Sérsic index $`n=1`$ represents an exponential profile and $`n=4`$ is a de Vaucouleurs law. The best-fit Sérsic profile is determined by non-linear least-squares fitting to the region $`r=1^{\prime \prime }20^{\prime \prime }`$; in this region, contributions from the nucleus and effects of the different spatial resolution of ESI and WFPC2 should be negligible. Sérsic indices, half-light effective radii and effective surface brightnesses are listed in Table 3. The average ellipticity and $`B_4`$-parameter (discussed in § 3.3) also listed in this table were determined over the same radial range.

## 3 Results

### 3.1 Kinematic Profiles

Kinematic profiles for the eleven Virgo Cluster dEs are presented in Figures 2 and 3. We have separately plotted dEs with significant rotation velocities and those which show no evidence for substantial rotation along the major axis ($`v_{\mathrm{rot}}2.5`$ km s-1, or $`v_{\mathrm{rot}}/\sigma =0.1`$ see below). For the former kinematic profiles (Figure 2), our observations do not reach out to a large enough radius in three out of four dEs to observe a turnover in the rotation curve; in these galaxies we measure only a lower limit to the maximum rotational velocity. We argue below that our observations are not far from the turnover radius. The maximum rotation velocity ($`v_{\mathrm{rot}}`$) are quoted as lower limits in Table 1 and shown as up-arrows in Figure 4. For galaxies which show no evidence for substantial rotation (Figure 3), we estimate the upper limit on the maximum rotation velocity by differencing the average velocities on either side of the major axis of the galaxy and dividing by two. Error bars on rotational motion were determined by adding in quadrature the error of the mean velocity on either side of the major axis. These quantities along with the heliocentric velocity and velocity dispersion are listed in Table 1.

We note that five dEs in our combined sample (VCC 543, VCC 856, VCC 1036, VCC 1087, VCC 1261) have been previously observed by Simien & Prugniel (2002) and/or Pedraz et al. (2002). Our kinematic profiles are entirely consistent with these measurements. Due to the higher spectral resolution and signal-to-noise ratio of our observations, we are able to place significantly tighter constraints on the rotational velocity for two of these galaxies. In all cases, we obtain a more accurate estimate of the velocity dispersions.

For the dE profiles in Figure 3, it is difficult to explain the lack of observed major axis rotation as being a result of insufficient radial coverage. The majority of our kinematic profiles are measured out to between 0.5–1.0 $`r_{\mathrm{eff}}`$. Two-integral dynamical models predict that if these galaxies were oblate, isotropic rotators we should have reached or measured beyond the maximum rotation velocity at these radii (see Figures 8–9 in Dehnen & Gerhard, 1994). Although these models are based on the specific case of density profiles with $`\rho r^4`$ at large radii and a varying inner cusp slope, the predictions for $`v(r/r_{\mathrm{eff}})`$ are generic and should not be very different for a Sérsic profile (as is more appropriate for dE galaxies). As an example, we measure the velocity profile of the dE3 galaxy VCC 1261 out to its effective radius of $`r_{\mathrm{eff}}=7.3^{\prime \prime }`$ (Figure 3). As we discuss below, if the observed flattening in this galaxy was due to rotation, we would expect $`v_{\mathrm{rot}}/\sigma =0.6`$, implying a maximum rotation velocity of 30 km s-1 given the average dispersion velocity of 45 km s-1. This is in stark contrast to the measured upper limit on rotation in VCC 1261 of 0.5 km s-1.

Conversely, for the four profiles with measurable rotation velocities (Figure 2), it is not surprising that we observe a turnover in the rotation curve for only one out of four strongly rotating galaxies (VCC 856). For these dEs, we only have kinematic data out to $`0.5r_{\mathrm{eff}}`$. The models of Dehnen & Gerhard suggest that we have barely reached the maximum rotation velocity in these systems and would need to observe a little further out in radius in order to see a turnover in these rotation curves. The rotation velocities for the these dEs are listed as lower limits in Table 1.

To compare the degree of rotational support in our full sample of 17 dEs, we plot the ratio of the maximum rotational velocity to the average velocity dispersion ($`v_{\mathrm{rot}}/\sigma `$) versus ellipticity (Figure 4, left panel). The solid line in this figure is the ratio expected from an oblate, isotropic, rotationally-flattened body seen edge-on; systems that are not edge-on should have somewhat larger predicted $`v_{\mathrm{rot}}/\sigma `$ values (Binney & Tremaine, 1987). The lower limits on $`v_{\mathrm{rot}}/\sigma `$ for the four galaxies with measured rotation are consistent with rotational flattening. The upper limits on $`v_{\mathrm{rot}}/\sigma `$ determined for the majority of our dEs are significantly smaller than expected if the observed flattenings were due to rotation and imply that these objects must be supported by anisotropic velocity dispersions. In our present sample, the degree of rotational support does not appear to be a continuous distribution: we observed either dEs with no measurable major axis rotation, or dEs with rotation velocities approaching that expected for rotational support. There is a natural division in our sample between “rotating” and “non-rotating” dEs; we arbitrarily place the dividing line in our sample as galaxies with rotational support greater or less than $`v_{\mathrm{rot}}/\sigma =0.1`$. Rotating and non-rotating dEs cover a similar range of ellipticities and absolute magnitudes. Figure 4 suggests that rotational support is not correlated to either of these quantities. In the remaining sections, we explore whether or not any other global dE property is correlated to rotational properties.

The mean velocity dispersions for the dEs in Figures 2 and 3, determined outside of $`r=1^{\prime \prime }`$ to exclude any nuclear contributions, range between 25 and 45 km s-1. The velocity dispersion profiles are either constant as a function of radius or show a decrease in dispersion in the central region. As demonstrated in Geha et al. (2002), such profiles can in general be adequately modeled assuming that the stellar mass density profile is equal to the luminosity density profile times a constant mass-to-light ratio. Although spherical, isotropic models do not necessarily fit the observed velocity dispersion profiles in detail, such models do in general reproduce the overall shape of the observed dE velocity dispersion profiles.

### 3.2 The Fundamental Plane

Dwarf elliptical galaxies lie in a region of Fundamental Plane space distinctly different from other stellar systems. This is best illustrated in the $`\kappa `$-projection of the multivariate space defined by central velocity dispersion, $`\sigma _0`$, effective surface brightness, $`\mu _{\mathrm{eff}}`$, and effective radius, $`r_{\mathrm{eff}}`$ (Bender et al., 1992). As shown in Figure 5, dEs appear well separated from other stellar systems. Bender et al. (1992) argued that this separation represents a fundamental difference between the galaxy formation processes of dEs and more luminous classical ellipticals (see Guzman et al., 2003, however, for an alternate viewpoint). Here, we are primarily interested in the relative position of our rotating and non-rotating dE galaxies within Fundamental Plane space.

In both panels of Figure 5, the rotating and non-rotating dEs occupy similar regions of the Fundamental Plane. As a statistical comparison, we use the one-dimensional Kolmogorov-Smirnov (K-S) test. This test gives the probability ($`P_{\mathrm{KS}}`$) that the difference between two distributions would be as large as observed if they had been drawn from the same population. Two distributions are considered different if the probability that they are drawn from the same parent distribution can be ruled out at a confidence level greater than 95% ($`P_{\mathrm{KS}}<0.05`$). As an example, the probability that the rotation velocities of our rotating and non-rotating subsamples are drawn from the same parent distribution is 0.3% ($`P_{\mathrm{KS}}`$ = 0.003); thus this hypothesis can be ruled out at high confidence level. In comparing $`\kappa `$-values for rotating and non-rotating dEs (listed in Table 3), the relatively high values of the K-S probability, $`P_{\mathrm{KS}}`$ = 0.6, 0.2, and 0.1 for $`\kappa _1`$, $`\kappa _2`$, and $`\kappa _3`$ respectively, indicate that we cannot demonstrate that these two samples are drawn from different populations. The rotating dEs appear slightly offset in the direction of higher $`\kappa _1`$ and $`\kappa _2`$ values (corresponding to larger mass and surface brightness, respectively), but more data is required to establish such a correlation.

### 3.3 Morphology

Evidence for underlying disk-like structure has been presented for a handful of cluster dE galaxies based on deep imaging. Five dEs in the Virgo Cluster show evidence for a bar or weak spiral structure (Jerjen et al., 2000; Barazza et al., 2002) and two Fornax Cluster dE/dS0s show evidence for embedded disks (De Rijcke et al., 2003). This accounts for roughly 20% of analyzed images. Two of these galaxies are in our sample: Jerjen et al. discovered faint spiral structure in VCC 856 (IC 3328) implying the presence of a nearly face-on disk, while Barazza et al. presented evidence for an elongated dumbbell-shaped structure along the major axis of VCC 940 (IC 3349). The former galaxy is a rotating dE in our sample, the latter is a non-rotating dE. In view of these results, we analyzed all our dE images to determine the level of substructure present and whether or not this is correlated with the amount of major axis rotation.

Images of the dE galaxies in our sample appear to be smooth and without obvious signs of substructure, however, detailed analysis is required to detect possible low level substructure. As discussed in § 2.3, we determine surface brightness profiles using the IRAF ELLIPSE isophotal fitting routine. Deviations from the best-fitting ellipse, often an indication of an underlying disk or other substructure, are quantified by expanding the intensity variations along the best-fitting ellipse in a Fourier series as:

$$I(\varphi )=I_o+\underset{n=1}{\overset{N}{}}[\stackrel{~}{A}_n\mathrm{sin}(n\varphi )+\stackrel{~}{B}_n\mathrm{cos}(n\varphi )].$$
(1)
The first- and second-order terms ($`n=1,2`$) of Eqn. (1) are zero by definition; non-zero values would indicate that the best-fitting ellipse has not been found. For $`n3`$, the quantities

$`A_n=\stackrel{~}{A}_n/[a(dI/da)],`$ (2)
$`B_n=\stackrel{~}{B}_n/[a(dI/da)],`$ (3)
measure deviations of the isophote from the best-fitting ellipse, where $`a`$ is the semi-major axis length and $`(dI/da)`$ the local intensity gradient. The quantity $`B_4`$ is similar to the quantity $`a_4/a`$ used by e.g., Bender, Doebereiner, & Moellenhoff (1988). Positive $`B_4`$ values indicate disky isophotes whereas negative values indicate boxy isophotes (Jedrzejewski, 1987). In Figure 6, we present surface brightness, ellipticity, position angle, and $`B_4`$ as a function of radius for those dEs with ESI imaging. We note that in all cases the isophotal ellipticity varies with radius; two galaxies show significant departures from zero in their $`B_4`$ profiles. For the remaining dEs in our sample for which we have only WFPC2 imaging, we present the averaged ellipticity and $`B_4`$ measurements in Table 3. We do not present the WFPC2 radial profiles since much of this data has been presented elsewhere (Geha et al., 2002; Stiavelli et al., 2001; Geha, 2003), and because these images are too shallow to meaningfully constrain the amount of substructure present. As an illustration, the existing WFPC2 images do not show detectable substructure in VCC 940; however, as mentioned above, Barazza et al. (2002) present clear evidence for an elongated structure along its major axis from deep ground-based imaging.

In the first column of Figure 7 we present $`V`$-band ESI images for the profiles presented in Figure 6. In the second column of this figure we plot the residual image resulting from subtraction of a 2D model based on the ellipse fitting (excluding higher-order components) from the original image. In the third column we present unsharp-masked images created by subtracting a boxcar-smoothed image (with $`4^{\prime \prime }`$ smoothing length) from the original, to highlight high frequency spatial structure. The unsharp-masked images have the advantage of being independent of our ellipse fitting model, but can be difficult to interpret. For example, the “structure” apparent in the unsharp-masked images of VCC 1947 and VCC 745 is due to ellipticity gradients evident in Figure 6; the model-subtracted images of these galaxies in the middle column of Figure 7 show no obvious structure. On the other-hand, the model-subtracted images of two other dEs in Figure 7, VCC 1036 and VCC 1488, do show clear signs of an underlying disk. This is seen in both the unsharp-masked images and the positive $`B_4`$ profiles in Figure 6. The rotating dE/dS0 VCC 1036 has a strong disk component, while the non-rotating dE VCC 1488 has a weaker underlying disk. Both these disks lie along the major axis defined by the outer isophotes. In addition, we confirm the faint spiral structure in VCC 856 first presented by Jerjen et al. (2000); this is strong evidence for a nearly face-disk. The remaining three dEs do not show any residuals. Most notably, the strongly rotating dE VCC 1947 shows no evidence for a disk component.

In summary, there is evidence for underlying disks and/or substructure in both rotating and non-rotating dEs, but counter examples also exist for both kinematic types which show no evidence of such structure. For the rotating dEs, we present or confirm evidence for underlying disk structure in two dEs, but observe no evidence for any substructure in a third rotating dE. For the non-rotating dEs, we present evidence for a weak disk in one galaxy, in addition to one non-rotating dE with substructure presented in the literature. Two non-rotating dEs show no evidence for underlying structure. For the remaining dEs in our sample, WFPC2 imaging is not deep enough to place limits on the presence of substructure. We conclude that there can be interesting substructure in dEs, but its presence or absence does not appear to be a good indicator of the observed dynamics.

### 3.4 Line-Strength Indices

We compute line-strength indices according to the Lick/IDS system (Worthey et al., 1994) in the wavelength region $`48006000\text{Å}`$. This index system is calibrated to a fixed spectral resolution of $`8\text{Å}`$. To match indices we must degrade the spectral resolution of our spectra. Although this means sacrificing a wealth of fine structure almost certainly sensitive to stellar populations, higher spectral resolution stellar population models do not yet exist which cover a sufficient range of ages, metallicities and wavelengths. The adopted approach also allows us to compare directly to the measured indices of more luminous elliptical galaxies.

Line-strength indices were computed by first shifting the spectra to rest frame wavelengths and convolving with a wavelength-dependent Gaussian kernel to match the spectral resolution of the Lick/IDS system. Line-strengths were then calculated according to the index definitions of Worthey et al. (1994). The size of the smoothing kernel was determined by matching the measured indices of 16 stars (spectral type F9IV–M0III) observed through the Keck/ESI setup to the values of Worthey et al. (1994). The size of the kernel ranged between $`89\text{Å}`$ (40–45 ESI spectral pixels, Gaussian sigma); the average residual between measured and published indices was $`0.15\text{Å}`$. The measured line-strengths for these standard stars are plotted against the published values in Figure 8. Small zero-point corrections due to systematic effects such as sky subtraction and flat fielding errors both in our data and the published systems (Worthey & Ottaviani, 1997) are applied to the measured indices of each galaxy. These corrections were determined from the best fitting offset between our measured standard star indices and the published values assuming a linear relation with unit slope. These corrections are listed in each panel of Figure 8 and range between 0.1 – $`0.2\text{Å}`$. We do not correct for line broadening due to the intrinsic velocity dispersion of each dE galaxy as these are much smaller than the Lick/IDS broadening function.

Error bars on the indices were computed via Monte-Carlo simulation. We added noise to a high signal-to-noise template star based on the noise spectrum of each individual galaxy and compute indices with the same procedure described above. Error bars were determined for each index of each galaxy from the rms value after 1000 noise realizations. Error bars include contributions from photon noise, read-out noise and pixel-to-pixel correlations due to Gaussian smoothing.

We present line-strength indices for our Virgo Cluster dE galaxies measured from spectra extracted in a $`0.75^{\prime \prime }\times 3^{\prime \prime }`$ aperture centered on each object. These spectra have signal-to-noise ratios ranging between 50–100 per Å. In Table 4, we list the central line-strength indices and error bars for H$`\beta `$, Mgb, Fe5270, and Fe5335 (see Worthey et al. for index definitions). In addition, we list the combined iron index $`\mathrm{Fe}`$ defined as (Fe5270 + Fe5335)/2. Our results for the central regions of VCC 1073 and VCC 543 agree, within the errors, with previously published values of H$`\beta `$ and $`\mathrm{Fe}`$ (Pedraz et al., 2002). We restrict our line-strength analysis to the central $`r<1.5^{\prime \prime }`$ to avoid galaxy light contamination in our sky spectrum. Based on the surface brightness profiles, we estimate the level of this contamination to be a few percent or less in the galaxy center, increasing to $`25\%`$ in the outer regions. A few percent contamination should not affect the central line-strength values or the kinematic profiles, but could lead to significant errors in the line strengths at large radii where the contamination level is larger.

In Figures 9 and 10, we present line-strength index diagrams comparing the H$`\beta `$, Mgb and $`\mathrm{Fe}`$ indices for our dE sample. The majority of dEs are confined to a small region in all three panels with some amount of intrinsic scatter between galaxies. The exception is VCC 1488, a non-rotating galaxy with noted non-axisymmetric features (§ 3.3), which has a significantly higher H$`\beta `$ measurement. The line-strength indices of the rotating and non-rotating dEs are similarly distributed in each index-index diagrams. Based on the K-S test discussed in § 3.2, we compute the probability that, for each index, the line-strengths of these two populations are drawn from different distributions. The K-S probability is greater than $`P_{\mathrm{KS}}=0.5`$ for all our measured indices, meaning the line-strengths of these two samples are statistically consistent with being drawn from a single distribution. We conclude that rotating and non-rotating dEs have similar stellar populations despite very different internal kinematics.

We next compare our dE line-strength indices to the single-burst stellar population models of Thomas, Maraston, & Bender (2002). These models predict line-strength indices for a wide range of metallicities ($`2.25[\mathrm{Fe}/\mathrm{H}]+0.67`$ dex) and include predictions for both solar and non-solar element abundance ratios. In Figure 9, we investigate the \[$`\alpha /\mathrm{Fe}`$\] ratio of our dE sample by comparing the measured Mgb and $`\mathrm{Fe}`$ indices to model predictions. In this diagram, effects due to age and metallicity are largely degenerate and sensitivity to abundance ratio is maximized. We assume that Mg traces the $`\alpha `$-elements. The majority of dEs in Figure 9 are consistent with solar abundance ratios, with some scatter towards both the sub- and super-solar abundance ratios between $`0.3[\alpha /\mathrm{Fe}]<+0.3`$ dex which cannot be explained by differences in age and metallicity alone. We again note that the rotating and non-rotating dEs have similar inferred abundance ratios. Gorgas et al. (1997) first suggested that Virgo dEs are consistent with solar abundance ratios based on a smaller dE sample. This is in marked contrast to the sample of classical elliptical galaxies, taken from Trager et al. (2000), also plotted in Figure 9 which have super-solar abundance ratios $`[\alpha /\mathrm{Fe}]+0.3`$. This difference in abundance ratios can be interpreted as a difference in the time-scale of star formation: $`\alpha `$-elements are created rapidly by Type II supernovae while iron is produced by supernovae Type Ia on longer timescales. It can then be argued that the bulk of star formation in classical ellipticals occurred on much shorter timescales as compared to dwarf ellipticals. Our observations are further evidence that dwarf and classical elliptical galaxies have very different star formation histories.

To determine the luminosity-weighted stellar ages and metallicities for our dE sample, we plot the Mgb and $`\mathrm{Fe}`$ indices against H$`\beta `$ in Figure 10. Note that while conclusions based on relative line-strength differences between dE galaxies are robust, the derived absolute ages and metallicities may be affected by unknown systematic errors. The best fitting age and metallicity was determined for each galaxy by simultaneously minimizing the residuals between the observed line-strengths and the predicted Mgb, $`\mathrm{Fe}`$, and H$`\beta `$ indices from the Thomas et al. (2002) solar abundance ratio models. The best fitting age and metallicity for our 17 dE sample are 5 Gyr and $`[\mathrm{Fe}/\mathrm{H}]=0.3`$ dex, with rms spreads of 3 Gyr and 0.1 dex, respectively. This is consistent with the ages and metallicities implied by the dynamically determined $`V`$-band mass-to-light ratios, $`3\mathrm{{\rm Y}}_V6`$, calculated in Geha et al. (2002) for six dEs in the present sample; the single-burst population models of Worthey (1994) predict $`V`$-band mass-to-light ratios in this range for the ages and metallities stated above. Compared to the Trager et al. sample of classical elliptical galaxies plotted in Figure 10, the average dE in our sample has stronger H$`\beta `$ indices and weaker Mgb and $`\mathrm{Fe}`$ indices, implying these dEs are younger and more metal poor than a typical classical elliptical galaxy.

Despite the clear separation in the Fundamental Plane (see § 3.2) between dEs and classical elliptical galaxies, Bender, Burstein, & Faber (1993) first noted that the magnesium line-strengths of these two galaxy types follow a tight trend with velocity dispersion. Caldwell, Rose, & Concannon (2003) investigated this correlation for a sample of early-type galaxies which included a much larger number of galaxies with velocity dispersions less than $`\sigma =100`$ km s-1. They confirm this correlation for Mgb and several other Lick/IDS indices. In addition, the scatter in the line-strengths of H$`\beta `$, Mgb, and Fe5270 was found to be in excess of the measurement error for velocity dispersions less than $`\sigma =100`$ km s-1. In Figure 11, we plot line-strengths as a function of velocity dispersion. We fit a linear relation to the classical elliptical sample of Trager et al. (2000) and compare the result to the positions of the dEs in our sample. The linear fits to classical ellipticals, extrapolated to lower velocity dispersions, are consistent with our measured dE line-strengths. Although the observed scatter for our dE sample is larger than that of the classical ellipticals, our sample size is too small to make a quantitative statement regarding the intrinsic scatter.

## 4 The Local Environment of Rotating versus Non-Rotating dEs

In the above sections we have demonstrated that dEs with and without significant rotation velocities cannot be distinguished based on their internal properties. We next examine whether or not internal rotation is correlated with a dE’s local environment within the Virgo Cluster. As shown in the left panel of Figure 1, rotating and non-rotating dEs are found at varying radii from the center of Virgo. In velocity space (Figure 1, right panels), the non-rotating dEs span the full range of radial velocities found in the Virgo, whereas the rotating dEs appear clustered near the average Virgo radial velocity of $`1000`$ km s-1. This is more clearly evident in the first panel of Figure 12. Based on the K-S test discussed in § 3.2, the radial velocity distributions of the rotating versus non-rotating dEs are not significantly different ($`P_{\mathrm{KS}}=0.3`$), although including two additional dEs from the literature (Simien & Prugniel, 2002) makes this difference marginally significant ($`P_{\mathrm{KS}}=0.06`$) in the sense that rotating dEs have a narrower range in radial velocities. Conselice et al. (2001) have argued that Virgo Cluster dEs as a population span a much larger range of radial velocities as compared to more luminous classical ellipticals. They interpret this as evidence that dEs are a more recently accreted population. If larger dE samples confirm that rotating dEs span a narrower range of radial velocities compared to non-rotating dEs, this would suggest that their history in the Virgo Cluster is more closely associated with classical elliptical galaxies.

In the remaining panels of Figure 12, we further quantify the local environment of our dE sample by examining neighboring galaxies within $`2^{}`$ (0.5 Mpc) and 300 km s-1 of each dE. These scales were chosen to probe local enhancements within the Virgo Cluster on the scale of small galaxy groups. As a population, Virgo dEs are not preferentially found around larger parent galaxies (Ferguson & Sandage, 1991) in contrast to dEs in the field; local overdensities or proximity to large galaxies would be evidence of recent accretion into the Virgo Cluster from the surrounding field/groups. We compare for the rotating and non-rotating dEs: the number of neighboring galaxies contained within the physical distance and velocity difference stated above, the number of luminous companions ($`M_V<20`$) in this same region, and the physical distance to the nearest of these bright galaxies. In all cases, the rotating and non-rotating dEs are similarly distributed based on both inspection of Figure 12 and results of the K-S test. In all three cases the K-S probability is greater than $`P_{\mathrm{KS}}=0.25`$, meaning that the distribution of the two kinematic types in these panels cannot be distinguished. We conclude that internal dE rotation properties are not correlated with proximity to bright galaxies or the local environment within the galaxy cluster.

## 5 Discussion and Conclusions

We have established that the internal dynamics of dE galaxies span a wide range in rotational support as determined from major axis spectroscopy of 17 dEs in the Virgo Cluster. In our present dE sample, the degree of rotational support does not appear to span a continuous distribution: we observe either dEs with no measurable major axis rotation, or dEs with rotation velocities approaching that expected for a rotationally-flattened object. We therefore have separated our sample into rotating and non-rotating dEs (nominally defined as galaxies with $`v_{\mathrm{rot}}/\sigma >0.1`$ and $`v_{\mathrm{rot}}/\sigma 0.1`$, respectively) and investigated whether or not other dE properties are correlated with rotation velocity. We show that rotation velocity is not correlated with a dE’s position in the Fundamental Plane, the presence or absence of underlying disks or substructure, absorption-line-strength indices, or local environment.

Currently favored formation models do not naturally predict a dichotomy in the internal dynamics of dE galaxies. One possible explanation for the varying amount of rotational support is different mechanisms for the formation of rotating and non-rotating dEs. Although our observations do not rule out multiple formation mechanisms, they do place very tight constraints on variations in observable properties between the resulting dE populations. In particular, significantly different origins for rotating and non-rotating dEs would need to result in stellar populations that are indistinguishable between the two dE types yet very different from those of more luminous classical ellipticals. It is equally challenging however to produce the range in rotational properties via a single physical process.

Our conclusion that the internal properties and local environments of rotating versus non-rotating cannot be distinguished is limited by the size of our dE sample; increasing the number of dEs, particularly rotating dEs, with spatially-resolved measurements of internal kinematics is an important step towards further understanding the formation of these galaxies. It is equally important to refine the predictions and better understand the limitations of currently proposed dE formation models. For example, does the harassment scenario in which dEs are formed from larger disk galaxies via gravitational interactions produce the observed range of rotational support, and, in particular, can it account for the large fraction of dEs without significant rotation? To what extent do these interactions disrupt the disk of a progenitor galaxy and at what level is substructure predicted in dEs? Similar questions should be asked of any proposed dE formation model. Because dEs are so numerous in nearby galaxy clusters, constraining the formation and evolution of these objects is an important step towards assembling a global picture of galaxy evolution in these regions.

We thank Ricardo Schiavon and Sandy Faber for fruitful discussions regarding this work. M.G. acknowledges a Presidential Dissertation Year Fellowship from the University of California at Santa Cruz and support from the STScI Director’s Discretionary Research Fund. P.G. would like to thank Joe Miller for his support through a UCO/Lick Observatory Director’s grant, and acknowledges partial support from NASA/STScI grants GO-08192.03A and GO-08601.04A.


format: text

text:
# Applications of Graphical Condensation for Enumerating Matchings and Tilings

## 1 Introduction

The Aztec diamond of order $`n`$ is defined as the union of all unit squares whose corners are lattice points which lie within the region $`\{(x,y):|x|+|y|n+1\}`$. A domino  is simply a 1-by-2 or 2-by-1 rectangle whose corners are lattice points. A domino tiling  of a region $`R`$ is a set of non-overlapping dominoes whose union is $`R`$. Figure 1 shows an Aztec diamond of order 4 and a sample domino tiling.

In \[GCZ\], it was conjectured that the number of tilings for the order-$`n`$ Aztec diamond is $`2^{n(n+1)/2}`$. The conjecture was proved in \[EKLP\]. As the author went about trying to enumerate domino tilings for a similar region, he discovered a new technique called graphical condensation. This technique has some far-reaching applications for proving various combinatorial identities. These identities usually take the form

$$T(R_1)T(R_2)=T(R_3)T(R_4)+T(R_5)T(R_6),$$

where $`T(R_i)`$ stands for the number of tilings for a region $`R_i`$. In our applications, the regions $`R_i`$ are complexes built out of vertices, edges, and faces, and the legal tiles correspond to pairs of faces that share an edge; a collection of such tiles constitutes a tiling if each face of $`R_i`$ belongs to exactly one tile in the collection (such tilings are sometimes called diform tilings). Each region $`R_i`$ could be represented by its dual graph $`G_i`$. The number of tilings for $`R_i`$ would equal the number of perfect matchings of $`G_i`$. Thus we could replace each term $`T(R_i)`$ in the identity with $`M(G_i)`$, which stands for the number of perfect matchings of $`G_i`$. (Hereafter, it will be understood that any use of the term “matching” refers to a perfect matching.)

Graphical condensation involves superimposing a matching of one graph onto a matching of another, and then partitioning that union into matchings of two other graphs. The phrase graphical condensation comes from the striking resemblance between Dodgson condensation of determinants and graphical condensation of Aztec diamonds. A proof of Dodgson condensation which illustrates this striking resemblance can be found in \[Z97\].

This article describes how graphical condensation can be used to prove bilinear relations among numbers of matchings of planar bipartite graphs or diform tilings of regions. Among the applications are domino tilings of Aztec diamonds (as well as some variant regions with holes in them), and rhombus (or lozenge) tilings of semiregular hexagons (equivalent to plane partitions), with or without the requirement of bilateral symmetry. The main result extends to weighted enumeration of matchings of edge-weighted graphs, and this extension gives us a simple way to apply the method to count domino tilings of rectangles and diabolo tilings of fortresses.

## 2 Enumerative Relations Among matchings of Planar Bipartite Graphs

Before we state our enumerative relations, let us introduce some notation. We will be working with a bipartite graph $`G=(V_1,V_2,E)`$ in which $`V_1`$ and $`V_2`$ are disjoint sets of vertices in $`G`$ and every edge in $`E`$ connects a vertex in $`V_1`$ to a vertex in $`V_2`$. If $`U`$ is a subset of vertices in $`G`$, then $`GU`$ is the subgraph of $`G`$ obtained by deleting the vertices in $`U`$ and all edges incident to those vertices. If $`a`$ is a vertex in $`G`$, then $`Ga=G\{a\}`$. Finally, we will let $`M(G)`$ be the number of perfect matchings of $`G`$, and $`(G)`$ be the set of all perfect matchings of $`G`$.

In order to state the enumerative relations, we must first embed $`G`$ into the plane $`^2`$. The plane graph $`G`$ divides $`^2`$ into faces, one of which is unbounded.

###### Theorem 2.1

Let $`G=(V_1,V_2,E)`$ be a plane bipartite graph in which $`|V_1|=|V_2|`$. Let vertices $`a`$, $`b`$, $`c`$, and $`d`$ appear in a cyclic order on a face of $`G`$. (See Figure 2, left. Note $`a,b,c,d`$ lie on the unbounded face.) If $`a,cV_1`$ and $`b,dV_2`$, then

$$M(G)M(G\{a,b,c,d\})=M(G\{a,b\})M(G\{c,d\})+M(G\{a,d\})M(G\{b,c\}).$$

Proof: To prove this relation, we would like to establish that the two sets $`(G)\times (G\{a,b,c,d\})`$ and $`((G\{a,b\})\times (G\{c,d\}))((G\{a,d\})\times (G\{b,c\}))`$ have the same cardinality. Consider superimposing a matching of $`G\{a,b,c,d\}`$ onto a matching of $`G`$. Whenever both matchings share a common edge, we retain both edges and place a doubled edge in the united matching. Thus in the united matching (strictly speaking a multigraph, since some edges may belong with multiplicity 2), each vertex has degree 2 except for $`a,b,c,`$ and $`d`$, which have degree 1.

Now consider superimposing a matching of $`G\{a,b\}`$ onto a matching of $`G\{c,d\}`$. Each vertex in the resulting graph has degree 2 except for $`a,b,c,`$ and $`d`$, which have degree 1. The same type of graph results from superimposing a matching of $`G\{a,d\}`$ onto a matching of $`G\{b,c\}`$.

We define $``$ to be the set of multigraphs on the vertices of $`G`$ in which vertices $`a,b,c,`$ and $`d`$ have degree 1, and all remaining vertices have degree 2. The edges of $`G`$ form cycles, doubled edges, and two paths whose endpoints are $`a,b,c,`$ and $`d`$. Each pair of graphs in $`(G)\times (G\{a,b,c,d\})`$, $`(G\{a,b\})\times (G\{c,d\})`$, and $`(G\{a,d\})\times (G\{b,c\})`$ can be merged to form a multigraph in $``$. (Hereafter, we shall drop the prefix “multi-” and refer to the elements of $``$ as simply graphs.)

Let $`H`$ be a graph in $``$. From $`a`$, we can trace a path through $`H`$ until we hit another vertex of degree 1. No vertex can be visited twice by this path since each vertex has degree at most two. Eventually we must end at one of the other vertices of degree 1. If one path connects $`a`$ to $`b`$, then the path from $`c`$ must end at the remaining degree-1 vertex $`d`$. Otherwise if $`a`$ connects to $`d`$, then $`b`$ must connect to $`c`$. And since $`a,b,c,`$ and $`d`$ occur in cyclic order around a face of $`G`$, it is impossible for one path to connect $`a`$ to $`c`$ and the other path to connect $`b`$ to $`d`$. If such paths existed, then they would have to intersect, forcing some other vertex to have a degree greater than 2.

We now show that $`H`$ can be partitioned into a matching $`M_1`$ of $`G`$ and a matching $`M_2`$ of $`G\{a,b,c,d\}`$ in $`2^k`$ ways, where $`k`$ is the number of cycles in $`H`$. Since $`H`$ is bipartite, each cycle has even length. We partition each cycle in $`H`$ so that adjacent edges go into different matchings; each vertex in a cycle is incident to one edge from each matching. Each doubled edge is split and shared between both matchings. Since the paths connect $`a`$ to $`b`$ (or $`d`$) and $`c`$ to $`d`$ (or $`b`$), one end of each path must belong to $`V_1`$ and the other end must be in $`V_2`$. Thus each path has odd length (as measured by the number of edges), so we may assign the edges at the ends of each path to $`M_1`$. The remaining edges in the paths are assigned to $`M_1`$ and $`M_2`$, and thus it is always possible to partition $`H`$ into matchings $`M_1`$ and $`M_2`$. Since there are two choices for distributing edges in each cycle of $`H`$ into matchings $`M_1`$ and $`M_2`$, there are $`2^k`$ possible ways to partition $`H`$ into matchings of $`G`$ and $`G\{a,b,c,d\}`$.

Next, we show that $`H`$ can always be partitioned into either matchings of $`G\{a,b\}`$ and $`G\{c,d\}`$, or matchings of $`G\{a,d\}`$ and $`G\{b,c\}`$, but never both. Once again, the cycles and doubled edges are split between the matchings as described earlier. Without loss of generality, assume that paths connect $`a`$ to $`b`$ and $`c`$ to $`d`$. As shown earlier, the edge incident to $`a`$ must be in the same matching as the edge incident to $`b`$. A matching of $`G\{c,d\}`$ may contain both of those edges, but matchings of $`G\{a,d\},G\{b,c\}`$, and $`G\{a,b\}`$ cannot. Likewise, the edges incident to $`c`$ and $`d`$ can both belong only to a matching of $`G\{a,b\}`$. Thus it is possible for $`H`$ to be partitioned into matchings of $`G\{a,b\}`$ and $`G\{c,d\}`$, but not into matchings of $`G\{a,d\}`$ and $`G\{b,c\}`$. And just as in the previous paragraph, the partitioning can be done in $`2^k`$ ways (where $`k`$ is the number of cycles in $`G`$). Thus the number of partitions of $`H`$ into matchings of $`G`$ and $`G\{a,b,c,d\}`$ is equal to the number of partitions into matchings of $`G\{a,b\}`$ and $`G\{c,d\}`$, or of $`G\{a,d\}`$ and $`G\{b,c\}`$.

Thus we can partition $`(G)\times (G\{a,b,c,d\})`$ and $`((G\{a,b\})\times (G\{c,d\}))((G\{a,d\})\times (G\{b,c\}))`$ into subsets such that the union of each pair of graphs within the same subset forms the same graph in $``$. Each graph $`H`$ corresponds to one subset from each of $`(G)\times (G\{a,b,c,d\})`$ and $`((G\{a,b\})\times (G\{c,d\}))((G\{a,d\})\times (G\{b,c\}))`$, and those subsets have equal size. Thus $`(G)\times (G\{a,b,c,d\})`$ and $`((G\{a,b\})\times (G\{c,d\}))((G\{a,d\})\times (G\{b,c\}))`$ have the same cardinality, so the relation is proved.

Before Theorem 2.1 was known, James Propp proved a special case in which $`a,b,c`$, and $`d`$ form a 4-cycle in $`G`$; see \[P03\].

###### Corollary 2.2

Let $`a,b,c,d`$ be four vertices forming a 4-cycle face in a plane bipartite graph $`G`$, joined by edges that we will denote by $`ab`$, $`bc`$, $`cd`$, and $`da`$. Then the proportion $`P`$ of matchings of $`G`$ that have an alternating cycle at this face (i.e., the proportion of matchings of $`G`$ that either contain edges $`ab`$ and $`cd`$ or contain edges $`bc`$ and $`da`$) is

$$P=2(p(ab)p(cd)+p(bc)p(da))$$

where $`p(uv)`$ denotes the proportion of matchings of $`G`$ that contain the specified edge $`uv`$.

Proof: We note that for each edge $`uv`$ in $`G`$,

$$p(uv)=\frac{M(G\{u,v\})}{M(G)}.$$

The number of matchings of $`G`$ that contain the alternating cycle at $`abcd`$ is twice the number of matchings of $`G\{a,b,c,d\}`$. Thus

$$P=\frac{2M(G\{a,b,c,d\})}{M(G)}.$$

Then after multiplying the relation in Theorem 2.1 by $`2/M(G)^2`$, we get our result.

With this same technique, we can prove similar theorems in which we alter the membership of $`a,b,c,`$ and $`d`$ in $`V_1`$ and $`V_2`$.

###### Theorem 2.3

Let $`G=(V_1,V_2,E)`$ be a plane bipartite graph in which $`|V_1|=|V_2|`$. Let vertices $`a`$, $`b`$, $`c`$, and $`d`$ appear in a cyclic order on a face of $`G`$ (as in Figure 2, right). If $`a,bV_1`$ and $`c,dV_2`$, then

$$M(G\{a,d\})M(G\{b,c\})=M(G)M(G\{a,b,c,d\})+M(G\{a,c\})M(G\{b,d\}).$$

Proof: The proof of this relation is similar to that of Theorem 2.1 with several differences. In this case, we show that $`(G\{a,d\})\times (G\{b,c\})`$ and $`((G)\times (G\{a,b,c,d\}))((G\{a,c\})\times (G\{b,d\}))`$ have the same cardinality. The combination of a pair of matchings from either set produces a graph in the set $``$ of graphs on the vertices of $`G`$ in which all vertices have degree 2 except for $`a,b,c,`$ and $`d`$, which have degree 1. Now consider a graph $`H`$. If paths connect $`a`$ to $`b`$ and $`c`$ to $`d`$, then each path has even length. The edges at the ends of each path must go into different matchings. Thus $`H`$ can be partitioned into matchings of $`G\{a,d\}`$ and $`G\{b,c\}`$, or into matchings of $`G\{a,c\}`$ and $`G\{b,d\}`$. Otherwise, if $`a`$ is connected to $`d`$ and $`b`$ to $`c`$, then each path has odd length. Then $`H`$ can be partitioned into matchings of $`G\{a,d\}`$ and $`G\{b,c\}`$, or into matchings of $`G`$ and $`G\{a,b,c,d\}`$.

No matter which ways the path connect, $`H`$ can always be partitioned into matchings of $`G\{a,d\}`$ and $`G\{b,c\}`$. We can also partition $`H`$ into either matchings of $`G\{a,c\}`$ and $`G\{b,d\}`$, or matchings of $`G`$ and $`G\{a,b,c,d\}`$, but not both. Moreover, the number of partitions of $`H`$ into matchings of $`G\{a,d\}`$ and $`G\{b,c\}`$ is equal to the number of partitions into matchings of $`G\{a,c\}`$ and $`G\{b,d\}`$, or of $`G`$ and $`G\{a,b,c,d\}`$. Thus $`(G\{a,d\})\times (G\{b,c\})`$ and $`((G)\times (G\{a,b,c,d\}))((G\{a,c\})\times (G\{b,d\}))`$ have the same cardinality.

We show a simple application of Theorems 2.1 and 2.3 in which our graphs are $`2\times n`$ grids. From elementary combinatorics, the number of matchings of a $`2\times n`$ grid is $`F_{n+1}`$, where $`F_1=F_2=1`$, and $`F_n=F_{n1}+F_{n2}`$. These theorems lead to a straightforward derivation for some bilinear relations among the Fibonacci numbers. Consider a $`2\times n`$ rectangle with $`a,b,c`$ and $`d`$ being the four corners, as shown in Figure 3. Theorems 2.1 and 2.3 produce the relations

$$F_{n+1}F_{n1}=\{\begin{array}{cc}F_n^2+11\hfill & \text{for even }n\text{,}\hfill \\ F_n^211\hfill & \text{for odd }n\text{,}\hfill \end{array}$$

which could be simplified to $`F_{n+1}F_{n1}=F_n^2+(1)^n`$. This is also known as Cassini’s identity. Another combinatorial proof for this relation is found in \[WZ86\].

We could go a step further by letting $`a,b,c,d`$ be somewhere in the middle of the $`2\times n`$ grid. If $`a,b`$ are in column $`i`$, and $`c,d`$ are in column $`j>i`$ (see Figure 3, bottom), then the relations become

$$F_{n+1}F_iF_{ji}F_{nj+1}=F_iF_{ni+1}F_jF_{nj+1}+(1)^{ji1}(F_iF_{nj+1})^2,$$

which simplifies to

$$F_{n+1}F_{ji}=F_{ni+1}F_j+(1)^{ji1}F_iF_{nj+1}.$$

We close this section with two additional relations applicable in situations in which $`V_1`$ and $`V_2`$ have different size.

###### Theorem 2.4

Let $`G=(V_1,V_2,E)`$ be a plane bipartite graph in which $`|V_1|=|V_2|+1`$. Let vertices $`a`$, $`b`$, $`c`$, and $`d`$ appear cyclically on a face of $`G`$. If $`a,b,cV_1`$ and $`dV_2`$, then

$$M(Gb)M(G\{a,c,d\})=M(Ga)M(G\{b,c,d\})+M(Gc)M(G\{a,b,d\}).$$

###### Theorem 2.5

Let $`G=(V_1,V_2,E)`$ be a plane bipartite graph in which $`|V_1|=|V_2|+2`$. Let vertices $`a`$, $`b`$, $`c`$, and $`d`$ appear cyclically on a face of $`G`$, and $`a,b,c,dV_1`$. Then

$$M(G\{a,c\})M(G\{b,d\})=M(G\{a,b\})M(G\{c,d\})+M(G\{a,d\})M(G\{b,c\}).$$

The proofs for these relations are similar to the proofs for Theorems 2.1 and 2.3.

## 3 Proof of Aztec Diamond Theorem

The order-$`n`$ Aztec diamond graph refers to the graph dual of the order-$`n`$ Aztec diamond. Throughout this proof, an Aztec matching will mean a matching of an Aztec diamond graph. Figure 4 shows the order-4 Aztec diamond graph and an order-4 Aztec matching. Thus counting tilings for an Aztec diamond of order $`n`$ is the same as counting Aztec matchings of order $`n`$.

To prove that the number of Aztec matchings of order $`n`$ is $`2^{n(n+1)/2}`$, we need the following recurrence relation.

###### Proposition 3.1

Let $`T(n)`$ represent the number of Aztec matchings of order $`n`$. Then

$$T(n)=\frac{2(T(n1))^2}{T(n2)}.$$

Proof: It is sufficient to show that

$$T(n)T(n2)=2(T(n1))^2.$$

To prove this relation, we show that the number of ordered pairs $`(A,B)`$ is twice the number of ordered pairs $`(C,D)`$, where $`A`$, $`B`$, $`C`$, and $`D`$ are Aztec matchings of orders $`n`$, $`n2`$, $`n1`$, and $`n1`$, respectively.

We superimpose an Aztec matching $`B`$ of order $`n2`$ with an order-$`n`$ Aztec matching $`A`$ so that the matchings are concentric. Figure 5 shows Aztec matchings of orders 3 and 5, and the result of superimposing the two matchings. In the combined graph, the white vertices are shared by both the order-3 and order-5 matchings. The black vertices are from the order-5 matching only. Note that some edges are shared by both matchings. Note also that each black vertex has degree 1 in the combined graph, whereas each white vertex has degree 2.

Now consider the two Aztec matchings of order $`n1`$ shown in Figure 6. Let us call the first and second matchings $`C`$ and $`D`$, respectively. Figure 7 shows the two possible resulting graphs by superimposing matchings $`C`$ and $`D`$ and adding two extra segments. The left graph was made by fitting matching $`C`$ to the top and matching $`D`$ to the bottom of the order-5 diamond, and then adding two side edges. The graph on the right was made by fitting matching $`C`$ to the left and matching $`D`$ to the right of the order-5 diamond, and then adding the top and bottom edges. In both cases, each of the center vertices has degree 2, and all other vertices have degree 1. The graphs resemble order-3 Aztec matchings on top of order-5 Aztec matchings.

In general, we are given a graph $`G`$ on the vertices of the order-$`n`$ Aztec diamond graph with the following properties:

1. The inner vertices in $`G`$ that form an order-$`(n2)`$ Aztec diamond have degree 2.
2. The remaining outer vertices in $`G`$ have degree 1.
3. The edges of $`G`$ form cycles, doubled edges, single edges, and lattice paths of length greater than 1.

Let us call a graph with such properties a doubled Aztec graph. For each superimposition we have described so far, the result is a doubled Aztec graph $`G`$. We want to show that the number of partitions of $`G`$ into two Aztec matchings $`A`$ and $`B`$ of orders $`n`$ and $`n2`$ is equal to the number of partitions of $`G`$ into two order-$`(n1)`$ Aztec matchings $`C`$ and $`D`$ (along with two line segments). We will show that this number is $`2^k`$, where $`k`$ is the number of cycles in $`G`$. Since $`G`$ is bipartite, all cycles have even length. These cycles are contained in the middle common vertices, as they are the only vertices with degree 2. Each cycle can then be partitioned so that every other edge will go to the same subgraph; adjacent edges go to different subgraphs. For each cycle, there are two ways to decide which half of the cycle goes to $`A`$ or $`B`$. Similarly, there are two ways to decide which half goes to $`C`$ or $`D`$. All doubled edges in $`G`$ are split and shared by each subgraph. It remains to show that the other edges must be partitioned uniquely.

We now label $`G`$ as shown in Figure 8. The vertices whose degree is 2 are labeled $`O`$. The degree-one vertices surrounding the $`O`$-vertices are labeled $`T`$, $`U`$, $`V`$, and $`W`$ such that each side is assigned a different label. Every vertex on the outer boundary of $`G`$ is labeled $`Y`$, except for four vertices, one on each corner. Those four exceptions are assigned the label ($`T,U,V,`$ or $`W`$) of the vertices on the same diagonal. We have labeled the vertices such that each vertex labeled $`Y`$ will match with exactly one vertex labeled $`T,U,V,`$ or $`W`$. For each label $`T,U,V,`$ and $`W`$, exactly one vertex will not be connected to a $`Y`$-vertex. We denote these special vertices $`T^{}`$, $`U^{}`$, $`V^{}`$, and $`W^{}`$.

In a doubled Aztec graph, there must be paths joining $`T^{}`$ to $`U^{}`$ and $`V^{}`$ to $`W^{}`$, or paths joining $`T^{}`$ to $`W^{}`$ and $`U^{}`$ to $`V^{}`$. However, we cannot have paths going from $`T^{}`$ to $`V^{}`$ and from $`U^{}`$ to $`W^{}`$. If such paths existed, then both paths would have to travel through the $`O`$-vertices and intersect, thus forcing the degree of some $`O`$-vertex to be more than 2.

Let us show that the segments from both ends of a path must belong to the same subgraph in any partition of $`G`$. Let us 2-color the vertices of $`G`$ black and white so that black vertices are adjacent to white vertices and vice versa. The $`T`$\- and $`V`$\- vertices must be the same color; let us color all the $`T`$\- and $`V`$-vertices white. Then the $`U`$\- and $`W`$-vertices must be of the other color, which is black. Therefore, any path from $`T`$ to $`U`$, from $`U`$ to $`V`$, from $`V`$ to $`W`$, or from $`W`$ to $`T`$ must have odd length since the path goes from a black to a white vertex. Thus the segments from both ends of a path must belong to the same subgraph in any partition of $`G`$.

Thus, when we partition $`G`$ into matchings $`A`$ and $`B`$ of orders $`n`$ and $`n2`$, we must always place the ending segments into $`A`$ and determine the rest of the partition thereafter. Such a partition always exists.

Next we show that $`G`$ can be partitioned into two matchings $`C`$ and $`D`$ of order $`n1`$ along with two additional side edges. There are two possible ways this partition could be done. The first is top-bottom: the top diamond contains the $`T`$\- and $`U`$-vertices, and the bottom diamond contains the $`V`$\- and $`W`$-vertices. The second is left-right: the left diamond contains the $`T`$\- and $`W`$-vertices, and the right diamond contains the $`U`$\- and $`V`$-vertices.

Without loss of generality, let the paths in $`G`$ connect $`T^{}`$ to $`U^{}`$ and $`V^{}`$ to $`W^{}`$. When $`G`$ is partitioned into two matchings $`C`$ and $`D`$, both of order $`n1`$, one matching (say $`C`$) must have both $`T^{}`$ and $`U^{}`$, as they are the ends of the same lattice path. Thus $`C`$ is the top Aztec matching containing all $`T`$\- and $`U`$\- vertices (except for one $`U`$-vertex on the far right corner). Vertices $`V^{}`$ and $`W^{}`$ must belong to the other matching $`D`$. The paths are then partitioned uniquely. Thus we can partition $`G`$ into two order-$`(n1)`$ Aztec matchings placed top-bottom (plus two edges on the sides). However, it is not possible to partition $`G`$ into two side-by-side Aztec matchings of order $`n1`$ such that one contains the $`T`$\- and $`W`$-vertices, and the other contains the $`U`$\- and $`V`$-vertices. The reason is that since the left matching has $`W^{}`$, it would then contain $`V^{}`$. The latter cannot happen, since $`V^{}`$ is in the other matching.

Hence each doubled Aztec graph can be partitioned into two order-$`(n1)`$ Aztec matchings in one way (top-bottom) or the other (left-right), but never both. The partition of the paths is uniquely determined.

The number of ways to combine Aztec matchings of orders $`n`$ and $`n2`$ is $`T(n)T(n2)`$, while the number of ways to combine two order-$`(n1)`$ matchings is $`2T(n1)^2`$. Each combination becomes a doubled Aztec graph, so the relation is proved.

There are 2 ways to tile an order-1 Aztec diamond, and 8 ways to tile an order-2 Aztec diamond. Having proved the recurrence relation, we can now compute the number of tilings of an Aztec diamond of order $`n`$. The following result is easily proved by induction on $`n`$:

###### Theorem 3.2 (Aztec Diamond Theorem)

The number of tilings of the order-$`n`$ Aztec diamond is $`2^{n(n+1)/2}`$.

## 4 Regions with holes

### 4.1 Placement Probabilities

We can use graphical condensation to derive recurrence relations for placement probabilities of dominoes in tilings of Aztec diamonds. Let domino $`D`$ be a specified pair of adjacent squares in an Aztec diamond. The placement probability of $`D`$ in an order-$`n`$ Aztec diamond is the probability that $`D`$ will appear in a tiling of the order-$`n`$ Aztec diamond, given that all tilings are equally likely.

Placement probabilities are of interest in the study of random tilings. If we look at a random tiling of an Aztec diamond of large order, we notice four regions in which the dominoes form a brickwork pattern, and a central circular region where dominoes are mixed up. The placement probability of any domino at the center of the diamond will be near 1/4. However, in the top corner, dominoes which conform to the brickwork will have probabilities near 1. All other dominoes in this corner would have probabilities near 0. For proofs of these assertions, see \[CEP96\].

We could calculate the placement probability of a domino with the following steps. First, we replace the domino with a two-square hole in the Aztec diamond. Then we compute the number of tilings of that diamond with the hole. Finally, we divide it by the number of tilings of the (complete) Aztec diamond.

We can express the number of tilings of the order-$`n`$ Aztec diamond with the hole at $`D`$ in terms of tilings of lower-order Aztec diamonds with holes. But first, let us introduce some notation. We will let $`A_nD`$ stand for the order-$`n`$ Aztec diamond with domino $`D`$ missing. The dominoes $`D_{\mathrm{up}}`$, $`D_{\mathrm{down}}`$, $`D_{\mathrm{left}}`$, and $`D_{\mathrm{right}}`$ will represent dominoes shifted up, down, left, and right by a square relative to $`D`$ in the Aztec diamond. Then $`A_{n1}D_{\mathrm{up}}`$ is the order-$`(n1)`$ diamond such that when it is placed concentrically with $`A_nD`$, the hole of $`A_{n1}D_{\mathrm{up}}`$ will match up with $`D_{\mathrm{up}}`$. The regions $`A_{n1}D_{\mathrm{down}}`$ and so forth represent similar Aztec diamonds with domino holes. Finally, $`A_{n2}D`$ is the order-$`(n2)`$ Aztec diamond such that when $`A_{n2}D`$ is placed directly over $`A_nD`$, domino $`D`$ is missing. See Figure 9 for examples. (In case $`D_{\mathrm{up}}`$, etc. lies outside $`A_{n1}`$, the region $`A_{n1}D_{\mathrm{up}}`$ will not be defined.)

By using graphical condensation, we can relate the number of tilings of these Aztec diamonds with holes:

$$T(A_nD)T(A_{n2}D)=T(A_{n1}D_{\mathrm{up}})T(A_{n1}D_{\mathrm{down}})+T(A_{n1}D_{\mathrm{left}})T(A_{n1}D_{\mathrm{right}}).$$

We also have the following relation, which relates numbers of tilings of Aztec diamonds:

$$T(A_n)T(A_{n2})=2T(A_{n1})T(A_{n1}).$$

We can then derive a relation among placement probabilities of dominoes in Aztec diamonds of orders $`n`$, $`n1`$, and $`n2`$. When we divide the first relation by the second, we get

$$P(A_n,D)P(A_{n2},D)=\frac{P(A_{n1},D_{\mathrm{up}})P(A_{n1},D_{\mathrm{down}})+P(A_{n1},D_{\mathrm{left}})P(A_{n1},D_{\mathrm{right}})}{2},$$

where $`P(R,D)`$ is the placement probability on domino $`D`$ in region $`R`$. The probability $`P(R,D)`$ was computed by dividing $`T(RD)`$ by $`T(R)`$.

### 4.2 Holey Aztec Rectangles

Another application of graphical condensation deals with regions called holey Aztec rectangles. A holey Aztec rectangle is a region similar to an Aztec diamond, except that the boundary of an $`n`$-by-$`(n+1)`$ holey Aztec rectangle consists of diagonals of length $`n`$, $`n+1`$, $`n`$, and $`n+1`$. In addition, to maintain the balance of squares of different parity so that the region can be tiled, a square is removed from its interior. Problems 9 and 10 in \[P99\] ask to enumerate tilings of a holey Aztec rectangle with a square removed in the center or adjacent to the center square, depending on the parity of $`n`$.

Let us label some of the squares in an Aztec rectangle as shown in Figure 10. We label a square only if the region becomes tileable after deleting that square. We let $`R_{n,a,b}`$ represent the $`n`$-by-$`(n1)`$ Aztec rectangle whose square $`(a,b)`$ has been deleted. Then we can apply our technique and come up with a theorem which relates the numbers of tilings among holey Aztec Rectangles.

###### Theorem 4.1

Let $`T(R)`$ stand for the number of tilings of a region $`R`$. Then for $`a`$, $`b`$ between $`1`$ and $`n1`$, the number of tilings of $`R_{n,a,b}`$ is expressed in the following relation:

$$T(R_{n,a,b})=\frac{T(R_{n1,a,b1})T(R_{n1,a1,b})+T(R_{n1,a,b})T(R_{n1,a1,b1})}{T(R_{n2,a1,b1})}.$$

Proof: The proof is very similar to that of Proposition 3.1. Instead of superimposing an order-$`n`$ Aztec matching on an order-$`(n2)`$ Aztec matching, we superimpose $`R_{n2,a1,b1}`$ on top of $`R_{n,a,b}`$ so that the holes align to the same spot. Given the graph $`G`$ resulting from the superimposition, we can partition it into two $`(n1)`$-by-$`n`$ holey Aztec rectangles. The partition can be done either left-right or top-bottom, but only one or the other. The left-right rectangles are isomorphic to $`R_{n1,a1,b}`$ and $`R_{n1,a,b1}`$. The top-bottom rectangles are isomorphic to $`R_{n1,a,b}`$ and $`R_{n1,a1,b1}`$.

Another relation can be proven for the case in which the hole is on the edge of the rectangle:

###### Theorem 4.2

If $`1an`$, then

$$T(R_{n,a,0})=\frac{T(R_{n1,a,0})T(A_n)+T(R_{n1,a1,0})T(A_n)}{T(A_{n1})}$$

where $`A_n`$ is the Aztec diamond of order $`n`$.

Proof: As an example, Figure 11 shows a matching of an order-3 Aztec diamond graph (which is shown in white vertices) on a matching of $`R_{4,3,0}`$ (which is missing the vertex $`b`$). The relation is derived in a manner analogous to Theorem 2.4.

### 4.3 “Pythagorean” regions

We can derive one more relation as a corollary to Theorem 2.5. Let $`R_n`$ be an $`n\times (n+1)`$ Aztec rectangle, where $`n`$ is even. Let $`t_1,t_2`$, and $`t_3`$ be (overlapping) trominoes in $`R_n`$, each of which contain the center square and two squares adjacent to it. Trominoes $`t_1`$ and $`t_2`$ are L-shaped, while $`t_3`$ is straight. Let $`t_1`$ point to a side of length $`n`$, and $`t_2`$ point to a side of length $`n+1`$. (See Figure 12.) Then

$$T(R_nt_1)^2+T(R_nt_2)^2=T(R_nt_3)^2.$$

In other words, we have a Pythagorean relation among the number of tilings of these regions! The proof of this relation is to set $`G`$ to be $`R_n`$ minus the center square, let $`a,b,c,d`$ be squares adjacent to the center, and then apply Theorem 2.5.

The reader may also like to puzzle over a similar “Pythagorean” relation among the numbers of tilings of rectangular (not Aztec rectangular) regions in which each region has a pentomino hole in its center. The pentominoes are shown in Figure 13.

## 5 Weighted matchings of Planar Bipartite Graphs and Aztec Diamonds

### 5.1 Weighted Planar Bipartite Graphs

We can generalize the enumerative relations proved in section 2 to cover weighted planar bipartite graphs. Given a graph $`G`$, we can assign a weight to each edge to form a weighted graph. The weight of any subgraph $`H`$ of $`G`$ is the product of the weights of all the edges in $`G`$ (in the case where $`H`$ is a multigraph, each edge-weight contributes with exponent equal to the multiplicity of the associated edge in $`H`$); e.g., the weight of a matching of $`G`$ is the product of the weights of each edge in that matching. We denote the weight of $`G`$ itself by $`w(G)`$. We also define the weighted sum $`W(G)`$ of $`G`$ to be the sum of the weights of all possible matchings on $`G`$.

We can now state and prove a weighted version of Theorem 2.1:

###### Theorem 5.1

Let $`G=(V_1,V_2,E)`$ be a weighted plane bipartite graph in which $`|V_1|=|V_2|`$. Let vertices $`a`$, $`b`$, $`c`$, and $`d`$ appear on a face of $`G`$, in that order. If $`a,cV_1`$ and $`b,dV_2`$, then

$$W(G)W(G\{a,b,c,d\})=W(G\{a,b\})W(G\{c,d\})+W(G\{a,d\})W(G\{b,c\}).$$

Proof: The proof essentially follows that of Theorem 2.1, except that we must now account for the weights. Let $``$ be the set of graphs on the vertices of $`G`$ in which vertices $`a`$, $`b`$, $`c`$, and $`d`$ have degree 1, all other vertices have degree 2, and doubled edges are permitted. Let $`H`$ be a graph in $``$. As before, $`H`$ may be partitioned into two matchings $`M_1`$ and $`M_2`$ with these possibilities:

1. $`(M_1,M_2)(G)\times (G\{a,b,c,d\})`$.
2. $`(M_1,M_2)(G\{a,b\})\times (G\{c,d\})`$.
3. $`(M_1,M_2)(G\{a,d\})\times (G\{b,c\})`$.

As we have seen before, $`H`$ can always be partitioned in choice 1, and also in either choice 2 or choice 3 (but not both). The number of possible partitions is $`2^k`$, where $`k`$ is the number of cycles in $`H`$. So

$`W(G)W(G\{a,b,c,d\})`$ $`=`$ $`{\displaystyle \underset{H}{}}2^{k(H)}w(H)`$
$`=`$ $`W(G\{a,b\})W(G\{c,d\})+W(G\{a,d\})W(G\{b,c\}),`$
where $`k(H)`$ is the number of cycles in $`H`$.

Similar relations can be generalized from Theorems 2.32.4, and 2.5:

###### Theorem 5.2

Let $`G=(V_1,V_2,E)`$ be a weighted plane bipartite graph in which $`|V_1|=|V_2|`$. Let vertices $`a`$, $`b`$, $`c`$, and $`d`$ appear on a face of $`G`$, in that order (as in Figure 2, right). If $`a,bV_1`$ and $`c,dV_2`$, then

$$W(G\{a,d\})W(G\{b,c\})=W(G)W(G\{a,b,c,d\})+W(G\{a,c\})W(G\{b,d\}).$$

###### Theorem 5.3

Let $`G=(V_1,V_2,E)`$ be a weighted plane bipartite graph in which $`|V_1|=|V_2|+1`$. Let vertices $`a`$, $`b`$, $`c`$, and $`d`$ appear on a face of $`G`$, in that order. If $`a,b,cV_1`$ and $`dV_2`$, then

$$W(Gb)W(G\{a,c,d\})=W(Ga)W(G\{b,c,d\})+W(Gc)W(G\{a,b,d\}).$$

###### Theorem 5.4

Let $`G=(V_1,V_2,E)`$ be a weighted plane bipartite graph in which $`|V_1|=|V_2|+2`$. Let vertices $`a`$, $`b`$, $`c`$, and $`d`$ appear on a face of $`G`$, in that order,and $`a,b,c,dV_1`$. Then

$$W(G\{a,c\})W(G\{b,d\})=W(G\{a,b\})W(G\{c,d\})+W(G\{a,d\})W(G\{b,c\}).$$

### 5.2 Weighted Aztec Diamonds

Consider a weighted Aztec diamond graph $`A`$ of order $`n`$. Define $`A_{\mathrm{top}}`$ to be the upper order-$`(n1)`$ Aztec sub-diamond along with its corresponding edge weights in $`A`$. Similarly, we can refer to the bottom, left, and right subgraphs of $`A`$ as $`A_{\mathrm{bottom}}`$, $`A_{\mathrm{left}}`$, and $`A_{\mathrm{right}}`$, which are all order $`n1`$ Aztec sub-diamonds. Finally, let $`A_{\mathrm{middle}}`$ be the inner order-$`(n2)`$ Aztec diamond within $`A`$. Figure 14 shows an Aztec diamond and its five sub-diamond graphs.

It turns out that the superimposition technique can also be used to establish an identity for weighted Aztec diamond graphs. The following theorem shows how the weighted sum of a weighted Aztec diamond can be expressed in terms of the weighted sums of the subdiamonds and a few edge weights.

###### Theorem 5.5

Let $`A`$ be a weighted Aztec diamond of order $`n`$. Also let $`t`$, $`b`$, $`l`$, and $`r`$ be the weights of the top, bottom, left, and right edges of $`A`$, respectively. Then

$$W(A)=\frac{lrW(A_{\mathrm{top}})W(A_{\mathrm{bottom}})+tbW(A_{\mathrm{left}})W(A_{\mathrm{right}})}{W(A_{\mathrm{middle}})}.$$

Proof: This proof is very similar to Proposition 3.1, except that we must fill in the details concerning the weights. Indeed, we want to show that

$$W(A)W(A_{\mathrm{middle}})=lrW(A_{\mathrm{top}})W(A_{\mathrm{bottom}})+tbW(A_{\mathrm{left}})W(A_{\mathrm{right}}).$$
(1)
We have seen how a doubled Aztec graph $`G`$ of order $`n`$ can be decomposed into subgraphs in two of three following ways:

1. (Big-small) Two Aztec matchings of orders $`n`$ and $`n2`$.
2. (Top-bottom) Top and bottom Aztec matchings of order $`n1`$, plus the left and right edges.
3. (Left-right) Left and right Aztec matchings of order $`n1`$, plus the top and bottom edges.

As we know, $`G`$ can always be decomposed via Big-small and by either Top-bottom or Left-right (but not both). The number of possible decompositions by either method is $`2^k`$, where $`k`$ is the number of cycles in $`G`$.

Each edge in $`G`$ becomes a part of exactly one of the subgraphs. Therefore, the product of the weights of the subgraphs will always equal to the weight of $`G`$, since each edge weight is multiplied once.

Recall that $`W(A)`$ is the sum of the weights of all possible matchings on $`A`$. Then

$$W(A)W(A_{\mathrm{middle}})=\underset{G}{}2^{k(G)}w(G)$$

where $`G`$ ranges over all doubled Aztec graphs of order $`n`$, and $`k(G)`$ is the number of cycles in $`G`$. Each term in the sum represents the weight of $`G`$ multiplied by the number of ways to partition $`G`$ via Big-small. Each partition is accounted for in $`W(A)W(A_{\mathrm{middle}}).`$ Similarly, we also have

$$lrW(A_{\mathrm{top}})W(A_{\mathrm{bottom}})+tbW(A_{\mathrm{left}})W(A_{\mathrm{right}})=\underset{G}{}2^{k(G)}w(G).$$

Thus both sides of Equation 1 are equal to a common third quantity, so the relation is proved.

Theorem 5.5 may be used to find the weighted sum of a fortress-weighted Aztec diamond. Imagine rotating an Aztec diamond graph by 45 degrees and then partitioning the edges of the graph into cells, or sets of four edges forming a cycle. In a fortress-weighted Aztec diamond, there are two types of cells: (1) cells whose edges are weight 1, and (2) cells whose edges are weight 1/2. Cells with edge-weights of 1/2 are adjacent to cells with edge-weights of 1. (See Figure 15).

There are three kinds of fortress-weighted Aztec diamonds:

1. The order $`n`$ is odd, and all edges in the corner cells have weight 1.
2. The order $`n`$ is odd, and all edges in the corner cells have weight 1/2.
3. The order $`n`$ is even, and two opposite corners have edges weighted 1/2, and the other two corners have edges weighted 1.

Let $`A_n`$, $`B_n`$, and $`C_n`$ stand for the weighted sums of the these diamonds, respectively. We then use Theorem 5.5 to establish relations among $`A_n`$, $`B_n`$, and $`C_n`$. They are

$`A_{2k+1}`$ $`=`$ $`{\displaystyle \frac{11C_{2k}C_{2k}+11C_{2k}C_{2k}}{A_{2k1}}}={\displaystyle \frac{2C_{2k}^{}{}_{}{}^{2}}{A_{2k1}}},`$
$`B_{2k+1}`$ $`=`$ $`{\displaystyle \frac{\frac{1}{2}\frac{1}{2}C_{2k}C_{2k}+\frac{1}{2}\frac{1}{2}C_{2k}C_{2k}}{B_{2k1}}}={\displaystyle \frac{\frac{1}{2}C_{2k}^{}{}_{}{}^{2}}{B_{2k1}}},`$
$`C_{2k}`$ $`=`$ $`{\displaystyle \frac{\frac{1}{2}\frac{1}{2}A_{2k1}A_{2k1}+11B_{2k1}B_{2k1}}{C_{2k2}}}={\displaystyle \frac{\frac{1}{4}A_{2k1}^{}{}_{}{}^{2}+B_{2k1}^{}{}_{}{}^{2}}{C_{2k2}}}.`$
From these relations, we can easily prove by induction that for odd $`k`$,

$`A_{2k+1}`$ $`=`$ $`(5/4)^{k(k+1)},`$
$`B_{2k+1}`$ $`=`$ $`(5/4)^{k(k+1)},`$
$`C_{2k}`$ $`=`$ $`(5/4)^{k^2}.`$
For even $`k`$,

$`A_{2k+1}`$ $`=`$ $`2(5/4)^{k(k+1)},`$
$`B_{2k+1}`$ $`=`$ $`{\displaystyle \frac{(5/4)^{k(k+1)}}{2}},`$
$`C_{2k}`$ $`=`$ $`(5/4)^{k^2}.`$
The importance of the fortress-weighted Aztec diamond comes from the problem of computing the number of diabolo tilings for a fortress. A diabolo is either an isosceles right triangle or a square, formed by joining two smaller isosceles right triangles. A fortress is a diamond shaped region that is made up of isosceles right triangles and can be tiled by diabolos. A fortress and a sample tiling by diabolos are shown in Figure 16.

To transform a fortress graph into a weighted Aztec diamond graph, we must use a method called urban renewal. This technique is explained in \[P03\] along with proofs and applications. In \[P03\], the transformation is described for the fortress, and the number of tilings for the fortress would be the weighted sum of the fortress-weighted diamond times some power of 2. Thus, graphical condensation, in combination with this known result about enumeration of fortresses, provides a very simple way to derive the formulas for the number of fortress tilings, first proven by Bo-Yin Yang \[Y91\].

A different sort of weighting scheme allows us to apply graphical condensation to count domino tilings of ordinary (non-Aztec!) rectangles. Every rectangle $`R`$ of even area can be imbedded in some Aztec diamond $`A`$ of order $`n`$ (with $`n`$ sufficiently large) in such a fashion that the complement $`AR`$ (the portion of $`A`$ that is not covered by $`R`$) can be tiled by dominoes $`d_1,\mathrm{},d_M`$. For any such tiling of $`AR`$, we can define a weighting of the Aztec diamond graph of order $`n`$ with the property that each matching of $`A`$ has weight 1 if the associated tiling of $`A`$ contains all the dominoes $`d_1,\mathrm{},d_M`$ and weight 0 otherwise. (Specifically, assign weight 1 to every edge that corresponds to one of the dominoes $`d_1,\mathrm{},d_M`$ or to a domino that lies entirely inside R, and weight 0 to every other edge.) Then the sum of the weights of the matchings of the weighted Aztec diamond graph equals the number of tilings of $`R`$.

## 6 Plane Partitions

A plane partition is a finite array of integers such that each row and column is a weakly decreasing sequence of nonnegative integers. If we represent each integer $`n`$ in the plane partition as a stack of $`n`$ cubes, then the plane partition is a collection of cubes pushed into the corner of a box. When this collection of cubes is viewed at a certain angle, these cubes will appear as a rhombus tiling of a hexagon.

In 1912, Percy MacMahon \[M12\] published a proof of a generating function that enumerates plane partitions that fit in a box $`(r,s,t)`$ with dimensions $`r\times s\times t`$.

###### Theorem 6.1

Define $`P(r,s,t)`$ as the generating function for plane partitions that fit in $`(r,s,t)`$. Then

$$P(r,s,t)=\underset{i=1}{\overset{r}{}}\underset{j=1}{\overset{s}{}}\frac{1q^{i+j+t1}}{1q^{i+j1}}.$$

Other proofs of this theorem have been published by Carlitz \[C67\], and Gessel and Viennot \[GV85\].

In this section, we will prove MacMahon’s formula with the help of graphical condensation. Using graphical condensation, we derive a relation that enables us to prove MacMahon’s formula by induction on $`r+s+t`$.

###### Theorem 6.2

$$P(r+1,s+1,t)P(r,s,t)=q^tP(r,s+1,t)P(r+1,s,t)+P(r+1,s+1,t1)P(r,s,t+1).$$

Proof: Let us take the dual graph of a hexagonal region of triangles in which $`r`$ is the length of the bottom right side, $`s`$ is the length of the bottom left side, and $`t`$ is the height of the vertical side. In this dual graph, all edges that are not horizontal are weighted 1. The horizontal edges are weighted as follows: the $`r`$ edges along the bottom right diagonal are each weighted 1. On the next diagonal higher up, each edge is weighted $`q`$, and the weights of the edges on each subsequent diagonal are $`q`$ times the weights of the previous diagonal. Thus the range of weights should be from $`1`$ to $`q^{s+t1}`$. (See Figure 17.) Call this weighted graph $`H(r,s,t)`$.

This weighting scheme is specifically designed so that, if a matching consists of the bottom edge (weighted $`q^i`$) and two other edges of a 6-cycle, then by replacing those edges with the other three edges, we have dropped the $`q^i`$-weighted edge in favor of the $`q^{i+1}`$-weighted edge. (See Figure 18.) The matching would then gain a factor of $`q`$, resembling the action of adding a new block (weighted $`q`$) to a plane partition. The minimum weight of a matching of this graph is $`q^{rs(s1)/2}`$, corresponding to the $`rs`$ horizontal edges that would make up the “floor” of the empty plane partition. The weighted sum of the graph is therefore $`q^{rs(s1)/2}P(r,s,t)`$.

Now the proof of this relation is very similar to the proofs of Theorem 2.1 and Proposition 3.1. We superimpose the two weighted hexagonal graphs $`H(r+1,s+1,t)`$ and $`H(r,s,t)`$ such that the bottom edge common to sides $`r`$ and $`s`$ of $`H(r,s,t)`$ coincides with the bottom edge of $`H_{r1,s1,t}`$. The two hexagons completely overlap except for four outer strips of triangles from $`H(r+1,s+1,t)`$. Let us number these strips 1, 2, 3, and 4. (See Figure 19.) When we superimpose the two matchings in the manner described above, we get once again a collection of cycles, doubled edges, single edges, and two paths. Each vertex inside $`H(r,s,t)`$ has degree 2, and each vertex in the four outer strips has degree 1.

Within each strip, all but one of the vertices are matched with each other. Those four unmatched vertices are the endpoints of the two paths. If one path runs between vertices on strips 1 and 2, and the other runs between vertices on strips 3 and 4, then the collection can be partitioned into matchings of the duals of $`H(r,s+1,t)`$ and $`H(r+1,s,t)`$, plus the edge on the corner of strips 2 and 3 (of weight $`q^{s+t1}`$). The graph $`H(r,s+1,t)`$ lacks strips 3 and 4, while $`H(r+1,s,t)`$ is the graph without strips 1 and 2. Alternatively, if the paths run from strip 1 to strip 4, and from strip 2 to strip 3, then the collection can be partitioned into matchings of $`H(r,s,t+1)`$ (the graph without strips 1 and 4) and $`H(r+1,s+1,t1)`$ (the graph without strips 2 and 3), plus two additional corner edges. In both cases, it is possible to partition the collection into matchings of $`H(r+1,s+1,t)`$ and $`H(r,s,t)`$. Finally, it is impossible for the paths to run from strips 1 to strip 3 and from strip 2 to strip 4 without intersecting. Thus

$`q^{(r+1)(s+1)s/2}P(r+1,s+1,t)q^{rs(s1)/2}P(r,s,t)=`$
$`q^{s+t}q^{r(s+1)s/2}P(r,s+1,t)q^{(r+1)s(s1)/2}P(r+1,s,t)+`$
$`q^{(r+1)(s+1)s/2}P(r+1,s+1,t1)q^{rs(s1)/2}P(r,s,t+1).`$
Note how the factor of $`q^{s+t}`$ in the right-hand side comes from the edge of weight $`q^{s+t}`$ that was not covered by either subgraph $`H(r,s+1,t)`$ or $`H(r+1,s,t)`$.

We simplify this relation by dividing through by $`q^{(r+1)(s+1)s/2+rs(s1)/2}`$ to get the desired relation:

$$P(r+1,s+1,t)P(r,s,t)=q^tP(r,s+1,t)P(r+1,s,t)+P(r+1,s+1,t1)P(r,s,t+1).$$

Now we can prove MacMahon’s formula for $`P(a,b,c)`$ by induction on $`a+b+c`$. When any of $`a`$, $`b`$, or $`c`$ are 0, $`P(a,b,c)=1`$. Now suppose MacMahon’s formula holds for all $`a,b,c`$ such that $`a+b+cr+s+t+1`$. We show MacMahon’s formula holds for $`(a,b,c)=(r+1,s+1,t)`$:

$`P(r,s+1,t)P(r+1,s,t)`$ $`=`$ $`\left({\displaystyle \underset{i=1}{\overset{r}{}}}{\displaystyle \underset{j=1}{\overset{s}{}}}{\displaystyle \frac{1q^{i+j+t1}}{1q^{i+j1}}}\right)^2\left({\displaystyle \underset{j=1}{\overset{s}{}}}{\displaystyle \frac{1q^{j+r+t}}{1q^{j+r}}}\right)\left({\displaystyle \underset{i=1}{\overset{r}{}}}{\displaystyle \frac{1q^{i+s+t}}{1q^{i+s}}}\right)`$
$`=`$ $`P(r,s,t){\displaystyle \frac{1q^{r+s1}}{1q^{r+s+t1}}}{\displaystyle \underset{i=1}{\overset{r+1}{}}}{\displaystyle \underset{j=1}{\overset{s+1}{}}}{\displaystyle \frac{1q^{i+j+t1}}{1q^{i+j1}}}`$
$`P(r+1,s+1,t1)P(r,s,t+1)`$ $`=`$ $`{\displaystyle \frac{_{i=1}^{r+1}_{j=1}^{s+1}(1q^{i+j+t2})_{i=1}^r_{j=1}^s(1q^{i+j+t})}{_{i=1}^{r+1}_{j=1}^{s+1}(1q^{i+j1})_{i=1}^r_{j=1}^s(1q^{i+j1})}}`$
$`=`$ $`{\displaystyle \underset{i=1}{\overset{r}{}}}{\displaystyle \underset{j=1}{\overset{s}{}}}{\displaystyle \frac{1q^{i+j+t1}}{1q^{i+j1}}}{\displaystyle \frac{(1q^t)_{i=1}^{r+1}_{j=1}^s(1q^{i+j+t1})_{j=1}^r(1q^{j+s+t})}{_{i=1}^r_{j=1}^s1q^{i+j1}}}`$
$`=`$ $`P(r,s,t){\displaystyle \frac{1q^t}{1q^{r+s+t1}}}{\displaystyle \underset{i=1}{\overset{r+1}{}}}{\displaystyle \underset{j=1}{\overset{s+1}{}}}{\displaystyle \frac{1q^{i+j+t1}}{1q^{i+j1}}}`$
$`P(r+1,s+1,t)P(r,s,t)`$ $`=`$ $`q^tP(r,s+1,t)P(r+1,s,t)+P(r+1,s+1,t1)P(r,s,t+1)`$
$`=`$ $`{\displaystyle \frac{q^t(1q^{r+s1})+(1q^t)}{1q^{r+s+t1}}}P(r,s,t){\displaystyle \underset{i=1}{\overset{r+1}{}}}{\displaystyle \underset{j=1}{\overset{s+1}{}}}{\displaystyle \frac{1q^{i+j+t1}}{1q^{i+j1}}}`$
$`=`$ $`P(r,s,t){\displaystyle \underset{i=1}{\overset{r+1}{}}}{\displaystyle \underset{j=1}{\overset{s+1}{}}}{\displaystyle \frac{1q^{i+j+t1}}{1q^{i+j1}}}.`$
Thus

$$P(r+1,s+1,t)=\underset{i=1}{\overset{r+1}{}}\underset{j=1}{\overset{s+1}{}}\frac{1q^{i+j+t1}}{1q^{i+j1}}.$$

It is interesting to note a similarity between Theorems 2.1 and 6.2. In the proof of each theorem, the two paths always run between vertices of opposite parity. We can find additional bilinear relations with MacMahon’s formula that are analogous to Theorems 2.3 and 2.4. For instance, if we partition a hexagonal graph as shown in Figure 20(a), we get

$`q^{(r+2)s(s1)/2}P(r+2,s,t)q^{rs(s1)/2}P(r,s,t)=`$
$`(q^{(r+1)s(s1)/2}P(r+1,s,t))^2`$
$`q^{(r+1)(s1)(s2)/2}P(r+1,s1,t+1)q^{(r+1)(s+1)s/2}P(r+1,s+1,t1).`$
After dividing through by $`q^{(r+1)s(s1)}`$, we get

$$P(r+2,s,t)P(r,s,t)=P(r+1,s,t)^2q^{r+1}P(r+1,s1,t+1)P(r+1,s+1,t1).$$

The relation analogous to Theorem 2.4 is:

$`q^{rs(s1)/2}P(r,s,t+1)q^{rs(s1)/2}P(r,s,t)=`$
$`q^{(r+1)s(s1)/2}P(r+1,s,t)q^{(r1)s(s1)/2}P(r1,s,t+1)+`$
$`q^{r(s+1)s/2}P(r,s+1,t)q^{r(s1)(s2)/2}P(r,s1,t+1),`$
which simplifies to

$$P(r,s,t+1)P(r,s,t)=P(r+1,s,t)P(r1,s,t+1)+q^rP(r,s+1,t)P(r,s1,t+1).$$

Figure 20(b) shows how to prove this relation. The graph has sides $`r,s+1,t,r+1,s,t+1`$. For each pair of hexagons, one is missing one of the strips along the sides of length $`r`$, $`t`$, or $`s`$, and the other hexagon is missing the other three strips (but contains the strip that the first hexagon is missing).

By taking the limit as $`q1`$, we derive relations among the numbers of plane partitions fitting in $`(r,s,t)`$. These numbers also enumerate rhombus tilings of semiregular hexagons with sides $`r,s,t,r,s,t`$. In particular, the following relation was proven by Doron Zeilberger in \[Z96\]:

$$N(r,s,t+1)N(r,s,t)=N(r+1,s,t)N(r1,s,t)+N(r,s+1,t)N(r,s1,t+1)$$

where $`N(r,s,t)`$ is $`lim_{q1}P(r,s,t)`$.

## 7 Transpose Complement Plane Partitions

If we view a plane partition as a collection of stacks of cubes, certain plane partitions will exhibit some symmetry. Such symmetry classes are outlined in \[B99\]. The complement of a plane partition $`\pi `$ in the box of dimensions $`r\times s\times t`$ is the set of cubes in the box that are not in $`\pi `$, reflected through the center of the box. A transpose complement plane partition (TCPP) $`\pi `$ is one for which the complement is the same as the reflection of $`\pi `$ in the plane $`y=x`$. If we visualize a TCPP as a rhombus tiling of a hexagon, the line of symmetry goes through the midpoints of two sides of the hexagon. Note that the sides of the hexagon must be of the form $`r,r,2t,r,r,2t`$, and the line of symmetry goes through the sides of length $`2t`$. The following theorem about the number of TCPPs was proved in \[P88\]:

###### Theorem 7.1

The number of TCPPs in an $`r\times r\times 2t`$ box is

$$\left(\genfrac{}{}{0pt}{}{t+r1}{r1}\right)\underset{1ijr2}{}\frac{2t+i+j+1}{i+j+1}.$$

Let $`N(r,r,2t)`$ be the the number of TCPPs in an $`r\times r\times 2t`$ box.

###### Proposition 7.2

If $`r2`$ and $`t1`$, then

$$N(r,r,2t)N(r2,r2,2t)=N(r1,r1,2t)^2+N(r,r,2t2)N(r2,r2,2t+2).$$

Proof: Because of the symmetry of a TCPP, we only need to consider the number of ways to tile one half of an $`(r,r,2t,r,r,2t)`$-hexagon. Also note that the triangles that lie on the line of symmetry must join to form rhombi. We can cut the hexagon in half to form an $`(r,t)`$-semihexagon. We can strip this semihexagon even further since rhombi are forced along the sides of length $`t`$. (This also shortens the sides of length $`r`$ by one.) See Figure 21, left. Let us label the four strips of triangles 1, 2, 3, and 4, so that strips 1 and 4 are along the sides of length $`t`$, and strips 2 and 3 are along the sides of length $`r1`$ (see Figure 21, right). Removing all four strips would produce an $`(r2,t)`$-semihexagon. Removing only strips 1 and 2 (or only strips 3 and 4) would produce a region with the same number of tilings as an $`(r1,t)`$-semihexagon. If we remove only strips 2 and 3, we shorten $`t`$ by one to form an $`(r,t1)`$\- semihexagon (with its outer edges stripped). Finally, if we remove only strips 1 and 4, we get an $`(r1,t+1)`$-semihexagon. The relation follows from graphical condensation.

This relation was noted by Michael Somos in a private communication.

We can now prove Theorem 7.1 by induction on $`r+t`$. The relevant base cases are $`N(r,r,0)=1`$ for all $`r`$, and $`N(0,0,2t)=1`$ and $`N(1,1,2t)=1`$ for all $`t`$. These cases are trivially established. We now use Proposition 7.2 to prove the inductive step. Given that the formula holds for $`N(r2,r2,2t),N(r1,r1,2t),N(r,r,2t2)`$, and $`N(r2,r2,2t+2)`$, we show that it holds also for $`N(r,r,2t)`$. We need to verify that

$`\left({\displaystyle \genfrac{}{}{0pt}{}{t+r1}{r1}}\right)\left({\displaystyle \genfrac{}{}{0pt}{}{t+r3}{r3}}\right){\displaystyle \underset{1ijr2}{}}{\displaystyle \frac{2t+i+j+1}{i+j+1}}{\displaystyle \underset{1ijr4}{}}{\displaystyle \frac{2t+i+j+1}{i+j+1}}=`$
$`\left({\displaystyle \genfrac{}{}{0pt}{}{t+r2}{r2}}\right)^2\left({\displaystyle \underset{1ijr3}{}}{\displaystyle \frac{2t+i+j+1}{i+j+1}}\right)^2+`$
$`\left({\displaystyle \genfrac{}{}{0pt}{}{t+r2}{r1}}\right)\left({\displaystyle \genfrac{}{}{0pt}{}{t+r2}{r3}}\right){\displaystyle \underset{1ijr2}{}}{\displaystyle \frac{2t2+i+j+1}{i+j+1}}{\displaystyle \underset{1ijr4}{}}{\displaystyle \frac{2t+2+i+j+1}{i+j+1}}.`$
We divide the right hand side by the left hand side to obtain

$`{\displaystyle \frac{r1}{t+r1}}{\displaystyle \frac{t+r2}{r2}}{\displaystyle \underset{1ir2}{}}{\displaystyle \frac{i+(r2)+1}{2t+i+(r2)+1}}{\displaystyle \underset{1ir3}{}}{\displaystyle \frac{2t+i+(r3)+1}{i+(r3)+1}}`$
$`+`$ $`{\displaystyle \frac{t}{t+r1}}{\displaystyle \frac{t+r2}{t+1}}{\displaystyle \underset{1ijr2}{}}{\displaystyle \frac{2t+i+j1}{2t+i+j+1}}{\displaystyle \underset{1ijr4}{}}{\displaystyle \frac{2t+i+j+3}{2t+i+j+1}}.`$
After a heavy dose of cancellations, this expression simplifies to

$`{\displaystyle \frac{(r1)(t+r2)(2r3)(2r4)(2t+r1)}{(t+r1)(r2)(r1)(2t+2r3)(2t+2r4)}}+{\displaystyle \frac{t(t+r2)(2t+1)(2t+2)}{(t+r1)(t+1)(2t+r3)(2t+2r4)}}`$
$`=`$ $`{\displaystyle \frac{(2r3)(2t+r1)}{(t+r1)(2t+2r3)}}+{\displaystyle \frac{t(2t+1)}{(t+r1)(2t+2r3)}}={\displaystyle \frac{(4rt+2r^25r6t+3)+(2t^2+t)}{2t^2+2r^2+4rt5t5r+3}}=1`$
and thus the inductive step and Theorem 7.1 follows.

## 8 Acknowledgments

Great thanks go to James Propp for suggesting the Holey Aztec Rectangle problem, to which this paper owes its existence; for suggesting some applications of graphical condensation, including domino tilings of fortresses and (non-Aztec) rectangles; and for editing and revising this article, making many very helpful suggestions along the way. Thanks also to Henry Cohn for pointing out the similarity between the relations in Theorems 4.1 and Corollary 2.2, thus providing me an inspiration for graphical condensation; and for applying graphical condensation to placement probabilities in Aztec Diamonds. Thanks to David Wilson for creating the software that enabled the enumeration of tilings of Aztec rectangles, and finally thanks to the referees for providing some very helpful comments for this article.