text:
# Mapping the Galactic Halo II: Photometric Survey

## 1 Introduction

A revolution is underway in our understanding of how galaxies form: The idea of a monolithic collapse of a single system at earliest times (Eggen et al., 1962) has been challenged by observations at high redshift and by increasingly sophisticated models of the evolution of structures within the basic framework of the Hot Big Bang model (Steinmetz & Mueller, 1994). These findings imply that we should see clear evidence of hierarchical formation processes within nearby galaxies. Indeed, some of the earliest work that suggested complex and possibly hierarchical evolutionary histories for galaxies such as ours came from studies of the stellar populations of the outer halo of the Milky Way (Searle & Zinn, 1978). Studies of nearby and high-redshift systems represent complementary approaches. No viable model of galaxy formation can be considered successful unless the evidence from both sources can be understood within a single framework.

The fossil record of the local galaxian population remains sparsely sampled. The halo is the most likely component to retain information of the Galaxy’s formation history. Apart from the isolated (and possibly peculiar) star clusters and dwarf galaxies, much of our knowledge of the halo derives from a relatively small number of nearby stars ‘passing through’ the solar neighborhood. Surveys that extend a few kpc from the Sun isolate halo stars more effectively, but even so, contamination by thick disk stars and background galaxies can be significant. The remoteness of the Magellanic Clouds and M31 make direct efforts to identify substructure in their halos extremely challenging.

Despite the difficulties, recent studies of our Galaxy have begun to reveal tantalizing evidence of possible substructure in the halo (Majewski, 1992; Côté et al., 1993; Arnold & Gilmore, 1992; Helmi et al., 1999; Yanny et al., 2000). More spectacularly, the discovery of the SGR dwarf galaxy (Ibata et al., 1994) provides indisputable evidence that our Galaxy’s halo is accreting stars and clusters that formed and evolved in an independent galaxy. The question has now shifted from ‘Did accretion play any role in the formation of the Galaxy?’ to ‘How much of the Galaxy formed from accretion of hierarchical fragments?’

This paper continues a series that describes our efforts to address this second question by identifying substructure directly within the Galactic halo. An overview of this survey was presented in Morrison et al. (2000a, Paper I). To summarize, we are carrying out a large-scale study of high-latitude fields optimized to identify distant halo stars as potential tracers of substructure in the outer Galaxy. Our observational approach is sensitive to a variety of halo stellar inhabitants, including (a) distant halo blue horizontal branch stars, (b) blue metal-poor stars (Preston et al., 1994, BMP); observationally, these are field analogs of blue stragglers found in star clusters (Bailyn, 1995), (c) halo turnoff stars, and (d) red giants. The bluer stars can be identified photometrically with relative ease using any number of combinations of broad-band colors. The Sloan Digital Sky Survey (Yanny et al., 2000) and our survey (Paper I) have already proven very effective at doing so. These can be considered wide-field extensions of the surveys of Hawkins (Norris & Hawkins, 1991).

Identification of the red giants, however, demands more precise and specialized photometric observations and added care to identify and remove contaminants. But this effort does have important rewards: red giants are the most luminous tracers found in significant numbers in the halo and hence allow us to probe to the greatest depth. Conceivably, luminous giants can be identified at distances as large as 200 kpc in our survey, though the giant-branch luminosity function ensures that the bulk of the stars we find will be between 20-100 kpc distant. Certain important biases that are inherent in the studies of horizontal branch stars (Kinman et al., 1994) are also avoided by isolating red giants whose properties are well understood as a function of age and metallicity. In addition, studies of the chemical evolution of the outer halo will be possible via detailed abundance analysis of halo giants using 10m-class telescopes. These studies are much more difficult for the hotter horizontal-branch stars.

The purpose of this paper is twofold: to describe the procedures we have developed to carry out the photometric observations of our survey, and to publish the photometry of photometrically calibrated fields. Our approach employs the modified Washington photometric system (Canterna, 1976; Geisler, 1984) to provide indices that can be used to isolate the four classes of stars described above. We use four filters in our survey to produce indices sensitive to temperature ($`MT2`$), surface gravity/luminosity ($`M51`$), and metallicity ($`CM`$). These indices provide the means of selecting halo giants from the blanket of thin and thick disk stars, and unresolved galaxies, the sum of which dominate the point sources in any halo field. It should be noted that the luminosity discrimination of the 51 filter is based on the strength of Mg hydride band and Mg b lines. Thus, at low metallicities the ability to photometrically distinguish subdwarfs from giants disappears (Morrison et al., 2000b).

Our observational procedures were first developed for use at the Burrell Schmidt 111Observations were made with the Burrell Schmidt of the Warner and Swassey Observatory, Case Western Reserve University and CTIO Schmidt telescopes. The basic approach was subsequently carried over to the NOAO 4m telescopes where our survey efficiency is much higher. The first of these runs employed the BTC camera on the CTIO 4m telescope in April 1999; it has proven to be the most successful run to date.

A subset of photometric red giant and horizontal branch candidates produced from these data sets have been observed spectroscopically. These observations provide a test for our photometric selection techniques and will be briefly discussed here. More details on the spectroscopy can be found in Paper I and in future papers of this series. Two important conclusions from these spectroscopic observations are worth stating here.

First, selection of distant red giants demands high-quality photometry to not only define the luminosity index ($`M51`$), but also to minimize contamination from the many stellar and galaxian contaminants found in all fields. When foreground dwarfs outnumber the rare giants by orders of magnitude, even three- or four-sigma errors can produce red-giant imposters. Our photometric procedures represent a balance between the need for precise photometric indices, and the need for an efficient, deep, survey of a significant fraction of the halo. Second, even with perfect photometric observations and a highly restrictive set of selection criteria, a photometric sample of distant red giants will be contaminated by metal-poor subdwarfs within the halo. Spectroscopic confirmation is necessary to identify and remove these relatively nearby stars from any deep halo survey such as ours (Morrison et al., 2000b).

The price of an efficient survey employing mosaics of CCD cameras is a very high data rate; on good nights we obtain 10-15 Gbytes of raw imaging data with the NOAO Mosaic imagers. These data must be reduced quickly to avoid serious backlogs and, more importantly, to promptly identify halo candidates that can be subsequently observed spectroscopically. Our imaging and spectroscopic observations are often scheduled within a few weeks of each other to be able to survey the same high-latitude regions in a given season. Throughout this survey – which has seen an increase in the data rate of over a factor of 50 in 1.5 years – we have aimed to carry out the full processing and photometric reductions of our imaging data in near real-time at the telescope. We have developed software that makes it possible to achieve this goal without using any additional programs or packages such as IRAF or IDL and the associated overheads and costs. This process is robust and flexible enough to handle the inevitable problem images within a large data set.

The following section summarizes the observations, and describes the fields that have been observed as of June 2000. Section 3 describes the automated pipeline for processing images and measuring photometry and, ultimately, astrometry of sufficient precision to support single-slit or multi-object spectroscopy. Section 4 presents the photometric results, emphasizing the precision that we achieve and the efficiency of our photometric selection procedure.

## 2 Observation Summary

### 2.1 Field Selection

The goal of this survey is to identify distant halo stars. It is advantageous to avoid the confusion of fields near the Galactic plane where the fraction of halo stars is extremely small. Thus, with a few exceptions, all fields were chosen to have a Galactic latitude of $`|b|25`$.

Furthermore, we wish to avoid highly reddened areas to avoid the possibility of differential reddening across a field, and to prevent distant halo stars being extincted below detection limits. All potential fields are checked on the reddening maps of Schlegel et al. (1998). Fields with high extinction, or spatially varying reddening are removed. With 1 exception, all fields have $`E(BV)<0.13`$.

Finally, we wish to avoid placing very bright stars in the images. These will saturate the surrounding region of the CCD chip, and add diffraction spikes that can confuse photometric reductions. Depending on how bright such a star is, this saturation can also remove up to 10% or more of a single CCD from the survey area. The Ohio State overlays of the POSS survey were used to choose fields with no stars as bright as SAO stars (Dixon, 1981).

Thus far we have imaged 134 fields covering a total area of 52 square degrees. These fields are listed in Table 1. Figs. Mapping the Galactic Halo II: Photometric Survey and Mapping the Galactic Halo II: Photometric Survey show the location of these fields in both Galactic and equatorial coordinates.

### 2.2 Instrumentation and Observing Strategy

As of June 2000, we have had 6 observing runs since October 1998. The observations were taken with 4 different instruments, and three different telescopes. The instruments are as follows: the Burrell Schmidt on KPNO, which used a single SITe 2048x4096 CCD with a pixel scale of 1.45″/pixel, and a total area of 1.4 square degrees per field; the BTC camera on the CTIO 4m telescope, which consisted of 4 2048x2048 CCDs with 0.43″/pixel and a total area of 0.24 square degrees per field; the first NOAO Mosaic camera, used on the KPNO 4m with 0.27″/pixel and a total area of 0.38 square degrees per field; the second NOAO Mosaic camera used on the CTIO 4m with 0.25″/pixel, and a total area of 0.38 square degrees per field.

The most successful observing run was in April 1999 with the BTC camera in which we imaged 53 fields. These data proved to be of excellent quality. This is essential for distinguishing halo candidates from foreground dwarfs. As discussed in Sec. 4, we were highly successful in identifying halo giants from these data.

All four nights in April 1999 were judged photometric through the entire night, so, these fields are fully calibrated. All other observing runs had weather related difficulties for at least part of the run, and are only partially calibrated. In subsequent sections we describe the April 1999 reduction procedures as a template for the general reduction procedures used for this survey. Along the way we describe necessary differences specific to each of the other instruments.

Each field’s observation consists of a single exposure in each of four filters: $`C`$, $`M`$, $`T2`$, and $`DDO51`$ (Canterna, 1976; Geisler, 1984). The respective exposure times for each filter were typically 100, 500, 120, and 250 seconds. With limited success we tried to adjust the exposure times to match the variations in seeing so that every image would have the same photometric sensitivity. The exposure times, and observing conditions, for each field are listed in Table 2. With only one exception, the airmass of each exposure is $`<1.8`$, and most exposures were taken with an airmass $`<1.5`$. The seeing ranged from 0.7″to 3.3″.

The exceptions to this observing strategy are the 8 fields observed with the Burrell Schmidt. Because it is not possible to achieve the necessary photometric depth in a single exposure with this instrument, each field was observed at least 4 times under good conditions. Each exposure was 1200-second long in each filter. We do not list the airmass and seeing measurements for individual exposures. Poor images are removed, and photometry from the remaining images are averaged prior to being calibrated (see Sec. 3.4 for a full discussion).

For the 4m runs, focus offsets for each filter were determined at the beginning of the run. The telescope was then focussed in a single filter at the beginning of each night, and during the night if necessary. The focus was adjusted as the temperature changed throughout the night using the standard formula for the 4m telescopes. Focus for the Schmidt observations was adjusted throughout the night as required.

There is one logistic oddity concerning the BTC chip numbers. The chip numbers referred to in this paper are not the conventional numbers for the BTC camera. It was determined that chips 1 and 2 had been exchanged in the readout electronics accidentally during instrument setup. Thus, chip 1 for these observations actually corresponds to the traditional chip 2, while chip 2 is actually the traditional chip 1. For internal consistency we will refer to each chip by the number assigned during this observation run.

### 2.3 Photometric Calibration

It is essential that the data be photometrically calibrated. Candidate selection is based on specific color index criteria. Furthermore, distance estimates are based on the temperature index and magnitude. It is possible to select candidates based on relative positions in the color-color diagrams, however, such candiates will need to be calibrated to make them useful. Photometric standards for the Washington filter set (Geisler, 1990, 1996) were observed on all photometric nights. The strategy was to place a standard field on every chip and in every filter at least once during each run to obtain zero-point offsets between the chips. In addition, standard fields were observed in all filters with a single chip throughout each night to obtain the color term and extinction coefficients.

Some of the fields were observed in non-photometric conditions. Even if a photometric calibration solution is obtained for the instrument that took these data, the fields can not be reliably calibrated without additional observations. We have plans to reobserve these fields with smaller telescopes, and will publish these data when they are fully calibrated. We have spectroscopically confirmed giants in many of these fields, but, of course, do not know their distance.

The only run that was completely photometric was in April 1999 using the BTC camera. We discuss below the determination of this solution. We also have standard field observations for the Schmidt, and Mosaic-S (Mosaic South on the CTIO 4m; we will refer to the Northern KPNO Mosaic camera as Mosaic-N) taken under photometric conditions. However, we reserve discussion of these solutions until the full data set from these runs is published.

The photometric calibration solution for the BTC used three standard fields. Both SA 98 and SA 110 were observed with all four of the BTC chips, while NGC 3680 was observed only with chip 4. The photometric standard fields were observed over an airmass range of 1.03 to 1.82, encompassing the airmass range of the BTC target fields. A single calibration solution was used for all four nights. The data were examined for variations from night to night, but none were found to a precision of $`0.005`$ magnitudes.

The photometric calibration solution took the form

$`M=`$ $`m+Z_m0.1424\times X+0.1538\times (mt2)`$ $`\pm \text{0.020 (62 stars)}`$ (1a)
$`CM=`$ $`Z_{cm}0.2052\times X+1.043\times (cm)`$ $`\pm \text{0.023 (63 stars)}`$ (1b)
$`MT2=`$ $`Z_{mt2}0.09551\times X+1.158\times (mt2)`$ $`\pm \text{0.017 (61 stars)}`$ (1c)
$`M51=`$ $`m51^{}+Z_{m51}+0.0107\times X+0.1655\times (mt2)`$ $`\pm \text{0.018 (65 stars)}`$ (1d)
where $`M`$, $`C`$, $`T2`$ and $`51`$ correspond to calibrated magnitudes; $`m`$, $`c`$, $`t2`$ and $`51^{}`$ correspond to instrumental magnitudes; $`X`$ is the airmass; and $`Z`$ is the zero point. The color terms and the extinction terms were determined using the observations of chip 4; no significant differences were found among the color-terms of the other chips. The RMS residuals and the number of stars used in the fit are listed to the right of the equations above. A zero point offset was then determined for each of the other chips. The zero points are listed in Table 3. There were 5-10 stars available for the fit of each chip offset. The RMS residual ranged from 0.015 to 0.025.

The final step in our photometric calibration process is to remove interstellar reddening. For this purpose we have used the reddening maps of Schlegel et al. (1998) to estimate the reddening toward each star. The extinction values for each filter were derived from the relations given in Harris & Canterna (1979), and Geisler (1984). These relations are,

$`{\displaystyle \frac{A_C}{E(BV)}}`$ $`=`$ $`4.71`$ (2a)
$`{\displaystyle \frac{A_M}{E(BV)}}`$ $`=`$ $`3.64`$ (2b)
$`{\displaystyle \frac{A_{51}}{E(BV)}}`$ $`=`$ $`3.61`$ (2c)
$`{\displaystyle \frac{A_{T2}}{E(BV)}}`$ $`=`$ $`2.05`$ (2d)
assuming $`R_V=3.3`$. These are high latitude fields, and the reddening is quite low by design (see Sec. 2.1), so errors due to differential reddening are not significant. In addition, the $`M51`$ index is almost reddening-free.

## 3 Photometric Pipeline

The processing pipeline for this survey has four main tasks: (1) organize the images and associated data files; (2) apply instrumental calibration to the images; (3) measure stellar photometry from the images; (4) record relevant information about each of these steps. Because of the large amount of data, it is also crucial that this process is flexible enough to be stopped and started at any point. This allows us, for example, to perform some of the processing during the observing run, and finish the processing at our home institutions. Finally, we require the process to be robust against computer crashes, missing header information, and other inevitable mishaps that arise during an observing run. Elements of our approach follow the OGLE pipelines.

The essence of our pipeline is to maintain a flag file for each image. We chose to keep a separate flag for each chip in the mosaic field, although it is possible to maintain a single flag for all the chips of a given exposure. This flag file stores information needed by each step in the pipeline, namely the location of the image in the computer system, and the current reduction state of the image. The former is simply data stored in the file itself, while the later is indicated in the flag file name. For instance, suppose image spag001.fits has been flat-fielded and photometered, while spag002.fits has only been flat-fielded. The corresponding flag files might be spag001.phot and spag002.flat. This system allows one to glance at a directory of files and know immediately the progress of the pipeline.

We have split each step of the process into a separate program or script. These are designed to run continuously as daemon processes. Each daemon scans the directory of flag files for images that are ready for its step in the process. When such an image is found, it is processed, the flag file is updated, and a log file is appended with information about the image relevant to that step. A separate log is maintained by each of the daemons. Because the pipeline is so modular, it is easy to modify or even skip steps without affecting other steps in the process.

Fig. Mapping the Galactic Halo II: Photometric Survey is a flowchart representation of the reduction process. The shaded region is the instrumental calibration branch. These processes are not automated, and must be completed before the third daemon can run. A full description of the instrumental calibration steps is discussed in Sec. 3.3. In addition, photometric calibration and astrometry determinations are not currently automated. We are working on automating the astrometry process.

### 3.1 Daemon 1: Pipeline Initiation

The first daemon initiates an image into the pipeline by creating a flag file and copying the image to the working area. Since the flag files don’t yet exist, this daemon must rely on other clues to determine when an image is ready to be processed. For instance, if the images are being processed during the observing run, this daemon can scan the acquisition directory, and process any new images that appear. The indications that an image is ready are instrument dependent. One can use the size of the image file, but only if the instrument does not pre-allocate the memory for this file at the beginning of readout. To overcome this, once an image file appears the daemon can wait for a delay time that is at least as long as the readout time.

### 3.2 Daemon 2: Organization

Most often the names generated by the instrument have a prefix and a running number, such as spag005. The second daemon organizes the images with convenient names and directories so that images from the same field are grouped together. This daemon renames the file, and copies it to the appropriate directory for the field, creating the directory if necessary. A log is created for translating between the original name and the new name. Finally, the new name is placed in the flag file so that subsequent daemons know the location of the file.

For our survey, the adopted naming convention is

$$l[longitude]b[p/m][latitude]\mathrm{\_}[chip]\mathrm{\_}[filter]\mathrm{\_}[number].$$
(3)
Bracketed information is variable, and image specific. We found that the nearest degree for longitude and latitude was not quite accurate enough to uniquely distinguish different fields. Hence, the nearest tenth of a degree is placed in the name, with no decimal point. The sign of the latitude is indicated by p for the Northern Galactic hemisphere and m for the Southern Galactic hemisphere. The filter is given a letter code (M for $`M`$, G for $`DDO51`$, I for $`T2`$, and C for $`C`$), and a reference number. The reference number is necessary because our survey uses several different telescopes, which can have different filter sets, and, thus, substantially different color-terms from run to run. Thus, it is necessary to distinguish the $`T2`$ filter of one instrument from the $`T2`$ filter of another. Finally, there may be more than one image with the same filter in a given field. A running number is appended to the end to distinguish these images. As an example, consider the second exposure of chip 4 from a field at $`l=100.1`$ and $`b=45.5`$, with an M filter from the filter set with reference code 1. This would have the name l1001bm455\_4\_M1\_2.fits.

Position, filter, and chip information is read from the header. In those cases where the header information is missing, the daemon stops and queries the user to enter the information by hand. There are also cases where images from the same field can be given slightly different names. If the coordinates of different exposures are different by just enough to change the nearest tenth of a degree in either Galactic latitude or longitude, the names will be different. An additional program was necessary to correct the names of such images. This program changes the name, updates the logs to reflect the change, and copies the image and associated data files to the correct field directory.

The images from each chip of the Mosaic cameras are grouped together in a single FITS file when read from the instrument. Subsequent steps in our pipeline work with single image files. This daemon was modified to split the group file into a separate file for each chip.

### 3.3 Daemon 3: Instrumental Calibration

The third daemon applies the instrumental calibration to the images. This includes trimming the images, subtracting the bias, subtracting the zero-current, applying a flat-field correction, applying an illumination correction, and applying a dark sky flat correction. Creation of these instrumental calibration images, as described below, is not automated (see Fig. Mapping the Galactic Halo II: Photometric Survey).

In addition, the instrumental calibration images must be completed before this daemon can run. This presents some limitations in our ability to achieve true real-time reduction at the telescope. The most problematic are the dark sky flats, because these come from the target images themselves. We have found that dark sky flats are essential for the Mosaic cameras to obtain the best photometry. We are currently testing the reliability of re-using certain calibration images, especially the dark sky flats, from previous runs with the same instrument.

This daemon was originally written as an IRAF222IRAF is distributed by the National Optical Astronomy Observatories, which are operated by the Association of Universities for Research in Astronomy, Inc., under cooperative agreement with the National Science Foundation. script to take advantage of the many routines that exist to process images. We have subsequently written a stand-alone program to perform these processes. We achieve an 8-fold speed increase over the IRAF script due to optimizing disk access. This speed increase is imperative to achieve real-time reduction.

The BTC data were processed with the IRAF script. In this case the overscan region of each line was averaged along the readout direction. A first order Legendre polynomial was then fit to these average values. Points which deviated by more than 3 standard deviations were eliminated from the fit. The evaluation of this smooth fit determined the bias level subtracted from each line of the image. The algorithm used in all other data sets does not use a smooth fit for the bias subtraction. Instead, the bias for each row was determined separately from the average of the overscan region for that row. This later algorithm is also the one used in our stand-alone program. We found this to work better for the Schmidt and Mosaic cameras. There was no significant difference between the two algorithms for BTC images.

Zero-current images are averaged together after being trimmed and bias subtracted. Flat field images are created from dome flats. They are trimmed, bias subtracted, zero subtracted, and median combined to form a single image for each chip and each filter.

Illumination corrections are made from twilight sky flat images. The twilight images are trimmed, bias-subtracted, zero-subtracted, flat-field corrected, and median combined. A polynomial with order between 3 and 5 is then used to fit the large scale structure, producing an illumination correction. The exact order of the fit varies depending on instrument, and is chosen as low as possible while still reasonably matching the large scale structure.

When combining these instrumental calibration images, they must first be scaled. A significant number of extreme value pixels, from cosmic rays or bad pixels, can alter the statistics of the image. These same extreme values also affect the illumination correction fits adversely. Therefore, if necessary, we replace these extreme values with more appropriate values, such as zero, or the saturation level.

Finally dark sky flats are made from target data. In the case of the April 1999 BTC data, the target images taken on the first two nights (April 6 and 7) were used. The target data are first processed normally, including being trimmed, bias-subtracted, zero-subtracted, flat-field corrected, and illumination corrected. The images are then median combined. The median images are examined to be sure all objects are adequately removed. If the objects are not removed, clipping is applied during the median combination.

This dark sky flat also serves to remove the fringe pattern in the $`T2`$ images. The fringing level is a small fraction of the sky, which allows one to represent the fringe as $`fringe=ϵ\times sky`$, where $`ϵ<<1`$ and is approximately constant. Thus, the net count in the image is $`sky+fringe=sky(1+ϵ)`$. The fringe pattern has been stable within a given observing run for the instruments we have used. Thus, the normalized dark sky flat contains $`(1+ϵ)`$. Division of target images by the dark sky flat leaves just $`sky`$.

The assumption that $`ϵ`$ is constant is only approximately true. However, because $`ϵ<<1`$, small changes in $`ϵ`$ lead to even smaller errors in the fringe removal. For example, if $`ϵ`$ is the dark sky value, while $`ϵ^{}`$ is the target image value, the ratio $`(1+ϵ^{})/(1+ϵ)=1+(ϵ^{}ϵ)/(1+ϵ)`$. Thus, if $`ϵ^{}`$ is 10% different from $`ϵ`$, the fringe correction error is approximately $`0.1ϵ`$, which is very small since $`ϵ<<1`$.

It was found that the BTC data did not require a dark sky correction, with the exception of fringe removal. The magnitude of the dark sky correction indicates how well the dome and twilight images flat-field the data, as well as provides an indication of flat-field variability. The standard deviation of this correction in the central quarter of each of the BTC chips was 0.7%, 0.6%, 1.4%, and 0.5% in $`C`$, $`M`$, $`DDO51`$, and $`T2`$ respectively. These small corrections indicate the chips are remarkably stable, leading to high quality photometry.

Stellar photometry is performed with the DoPHOT (Schechter, Mateo, & Saha, 1993) program (see section 3.4). The version of DoPHOT used so far in this survey requires the image data to be 2 byte integers. This restricts the count values to $`32000`$. The saturation level is typically larger than this by a factor of two. To maintain this dynamic range, the image values are reduced by a factor of 2 before they are converted to 2 byte integers. The gain is then effectively twice the previous value. After division by two the noise in the images was still well-sampled.

#### 3.3.1 Mosaic Cameras

Both Mosaic instruments received significant benefit from the dark sky flat, in addition to fringe removal. This necessity makes it difficult to achieve true real-time processing because many target images are needed before a dark sky flat can be constructed. For future runs we will be testing the possibility of using dark sky flats made from images taken in previous runs. The success of this will depend on the long-term stability of the instruments, including the fringe pattern.

In addition to the basic reduction steps described above, the Mosaic cameras require the removal of cross-talk between amplifiers of adjoining pairs of chips. Properly removing this effect requires calibrating two chips simultaneously. This can be done with IRAF, and has been implemented in our stand-alone processing code.

#### 3.3.2 Schmidt Camera

Prior to being instrumentally calibrated, the Schmidt images require some pre-processing. First, the data values are saved by the instrument as type short, but actually have the full range of unsigned short by using negative values. Thus, the data have to be converted to unsigned short and then floating-point to be processed properly.

Second, while the saturation level is constant across the chip, the illumination is not. There is a large flat-field correction at the edges compared to the center because of vignetting. Thus, after flat-fielding the images, there is a large variation in the effective saturation level. Current versions of DoPHOT only allow a single saturation level for each chip. Unsaturated, but bright, stars away from the center of the chip are pushed above the saturation level by the flat-field correction.

If the saturation level is chosen appropriately for the center of the chip, these bright stars are flagged as saturated and ignored by DoPHOT. These bright stars are needed to define the PSF shape and aperture corrections in the outer regions of the chip. This is critical because the PSF is variable. On the other hand, if the saturation is chosen appropriately for the outer regions of the chip, saturated stars in the center are accepted as unsaturated resulting in inaccurate photometry, and misguided PSF fits.

To overcome this problem, we adjust the saturation level prior to flat-fielding the images, but after converting to type float. All values greater than the saturation level are set to an extremely high value. This value must be larger than the saturation level near the edges after the flat-field correction is applied. When the data are converted to 2-byte integers for DoPHOT, these extremely high values are set to the maximum allowed value to ensure they will be flagged by DoPHOT as saturated.

In principle, we could apply this same technique to data from the BTC and Mosaic cameras as well. However, the vignetting for these instruments is less severe than the Schmidt’s, and the flat-field correction varies less across a single chip ($``$10%). Thus, by setting the saturation level to the lowest effective value , we miss only a few of the brightest unsaturated stars.

Finally, because of the large field of view of the Schmidt camera, it is difficult to obtain good dome flat images. Instead, we relied on twilight sky images for the flat-field correction. These are processed identically to other twilight sky flats as described above, except we do not fit a smooth function to the combined image.

### 3.4 Photometry Measurement

The final daemon measures stellar photometry from the instrumentally calibrated images. We use the program DoPHOT (Schechter, Mateo, & Saha, 1993) for this measurement. The first step is to create a parameter file for the image. The parameters must include an estimate for the FWHM and the sky level. We wrote a program to estimate these values and output a parameter list appropriate for DoPHOT. The sky is estimated as the median pixel value.

The FWHM is estimated by finding local maxima in the image, and measuring the width at half the peak value. This is done only in one dimension to save computational time. The median value of these widths is used as the estimate. Because this estimate works in only one dimension, some care is needed in restricting the allowed range of widths. Permitting narrow widths, as from cosmic rays or bad pixels, produces a FWHM estimate that is too small. Permitting wide widths from a large number of background galaxies, or saturated stars, produces a FWHM estimate that is too large. These limits have to be adjusted as the seeing varies. Thus, the PSF determined by DoPHOT is monitored carefully to ensure that the FWHM estimate does not lead the program astray.

We set the object detection threshold to 2.5 times the noise standard deviation above the background. The PSF parameters are allowed to vary with the third power of position. The variations are small for the BTC, less than 10% from center to corner within a single chip.

We use an aperture radius of 12 pixels (5.2″) for determining aperture corrections. This radius was constrained by two factors. First, the aperture must be sufficiently large to contain all the flux from the star. This can be determined by plotting the aperture photometry as a function of radius. The aperture photometry will converge to a constant value, within the background noise, as the radius increases. Second, the aperture should be as small as possible to minimize the noise contribution from the background and neighboring stars.

We have added a routine to DoPHOT for automatically determining and applying aperture corrections. We found that the functional form of the aperture correction position variation was the same for the full aperture as it was for smaller apertures, provided the smaller aperture enclosed the stellar core. The only difference between the smaller aperture function and the full aperture function was a constant additive offset. In effect, the aperture correction did vary across a chip, and the shape of this variation could be determined from any aperture (within bounds). Therefore, the functional form of the position variation was determined by using a smaller, and hence less noisy, aperture. The aperture correction function determined from this smaller aperture was then corrected to a larger aperture with a constant offset.

The aperture corrections are determined with a third power positional fit. Only stars with internal errors better than 0.04 magnitudes are used in this fit. To reduce the noise in the fit, the least squares determination was made with an aperture radius of 3.6″. A constant offset was applied to obtain the 5.2″radius correction. The same procedure is applied to other data sets with similar aperture sizes.

The photometry must also be corrected for variable pixel scale. DoPHOT works best when the background is truly flat. Therefore, we allow the flat-field process to make the background flat before doing photometry. However, because the pixel scale varies across the field, photometric calibration of point sources will be in error systematically between the center and edge of the field. The correction varies smoothly, and slowly compared to the PSF size. Therefore, we can apply this correction directly to the photometry. Care must also be taken to apply the same correction to standard star observations.

Scale variation solutions for both Mosaic instruments are available with the MSCRED IRAF reduction package. We also have a scale variation solution for the BTC derived from observations of UNSO standard fields (Fischer, P., private communication). The camera on the Burrell Schmidt does not have significant pixel area variation.

Once the final photometry is obtained for all four filters, the stars are matched and calibrated. The star lists of each filter are matched to within a 0.5 pixel radius. All stars with multiple matches within this radius are rejected. The photometric calibration solution is then applied. In order for the color term to be applied, the star must be detected in both the $`M`$ and $`T2`$ filter. The stars do not have to be detected in $`C`$ or $`DDO51`$. Such stars will not be selected as halo giant candidates, although they could be selected among the blue halo candidates.

#### 3.4.1 Schmidt Photometry

The 8 fields obtained with the Schmidt require a more complicated scheme. Prior to matching between filters, the stellar photometry from all of the images in a single filter are matched and averaged. The images are often taken on different nights, so the pointing can vary from image to image. Thus, a master image is chosen, and all star list coordinates are transformed to this system.

The master also serves as a photometric master. When averaging photometry they must be on the same calibration system. The zero-point can vary from image to image because of clouds, or differences in airmass. A photometric zero-point difference is measured and applied to each frame to put them on the same photometric system as the master image. Finally, only stars that were found on $`80\%`$ of the images are retained.

In addition to averaging the photometry, the coordinates are also averaged. The coordinates from each star list are transformed to the coordinate system of the master image. The transformation is fit with equations of the form

$`x`$ $`=`$ $`\delta x+a_xx+b_xy`$ (4a)
$`y`$ $`=`$ $`\delta y+a_yx+b_yy`$ (4b)
where $`x`$ and $`y`$ are coordinates in the master system, and $`\delta x`$ and $`\delta y`$ are constants. With all the coordinates in the same system, the coordinates of each star are averaged together. This is necessary to improve positional accuracy because of the large pixels of this camera.

### 3.5 Astrometry

We determined astrometry solutions using the IRAF package FINDER. The USNO-A2 catalog (Monet et al., 1998) was used as a reference for the solution. Unfortunately the position information written to the image headers of the BTC files was not consistent. It varied randomly from the true pointing by several arcminutes. Thus, we were forced to find a solution for each chip of each field separately.

The number of reference stars on each chip varied greatly with field position, ranging from $`<200`$ to $`>1000`$. Because of this the accuracy of the solution varied greatly. In the low density regions the residual RMS from the fit was $`0.5\mathrm{}`$, but was as good as $`0.2\mathrm{}`$ in the high density regions. The position information presented in Sec. 4 should not be considered accurate enough for fiber spectroscopy. However, it is good enough to uniquely identify each star. We are working on an automated process for determining the astrometric solutions.

The images taken with the Schmidt camera are often deep enough that many astrometric standard stars are saturated. Thus, to achieve an accurate astrometric solution we take several short exposures in $`M`$ of each field. We average the coordinates of stars detected on these short exposures, as we did for the deeper images described in Sec. 3.4.1. This allows us to find an astrometric solution which can be tied to the master frame of the deeper images. This hybrid procedure has produced superb results which have been successfully used with fiber-spectroscopes. Further details of these astrometry calculations will be described in a later Paper that discusses our fiber spectroscopy. However, it is worth noting that, ultimately, the solution accuracy is limited by the unknown proper motions of stars in the USNO-A2 catalog.

## 4 Photometry Results

Table 4 lists a single star from each of the 53 BTC fields. The complete list of stars with errors $`<0.04`$ can be accessed in the electronic version of this paper, as well as through ADC (http://adc.gsfc.nasa.gov/). Data sets from other observing runs have not yet been fully photometrically calibrated because of problematic weather. As these data sets are calibrated we will add them to the ADC database, and describe them in subsequent papers in this series.

We found that the photometry from the BTC chip 1 (our notation; traditional chip 2) is not as reliable as that from the other three chips. This chip contained a residual flat-field pattern, and the photometric calibration data had more scatter.

We have also seen evidence for non-linearity in other data sets with this chip. For example, Fig. Mapping the Galactic Halo II: Photometric Survey shows a star by star comparison of photometry measured from two images of the same uncrowded field in chip 1. The two images were taken in December 1998 two nights apart. They were processed identically, and photometry was measured in the same manner. They are different in two ways. Frame 2 was taken when the sky was $`4`$ times brighter than for Frame 1. Frame 2 was also taken under better seeing conditions. They have the same exposure time. The frame with higher counts (due to the sky) returns brighter values for the faint magnitudes. This behavior is not seen in the other three chips of these same exposures. We believe the difference is due to non-linear response of the chip.

We have included the stars from chip 1 (traditional chip 2) in the plots and tables because we have successfully found halo giants from candidates on this chip. Also,removing these stars from the plots does not alter the appearance of the plots, nor decrease the scatter. However, the chip number is listed in Table 4 so the reader can identify these stars if desired.

The DoPHOT internal error distributions for all stars in all fields is shown in Fig. Mapping the Galactic Halo II: Photometric Survey. For reference, the average errors for a star at $`M=18.5`$ are 0.009, 0.008, 0.011, and 0.009 for $`C`$, $`M`$, $`DDO51`$, and $`T2`$ respectively. Selection for halo candidacy was restricted to stars with internal errors better than 0.04. These stars (Table 4) are shown in black, while stars not selected are shown in gray. The error must have been less than this cutoff in all filters where the star was detected to have been a possible candidate.

The turn-up of stars to higher errors at faint magnitudes is rather broad. This is because we have included stars from all 53 fields. The distribution from an individual field is much narrower. We achieved different depths for each field because of variations in sky brightness and seeing. For example, the photometric depth for an average $`M`$ error of 0.04 ranges from $`M=20.8`$ in field l3263bp386 to $`M=22.3`$ in field l2637bp330.

Fig. Mapping the Galactic Halo II: Photometric Survey shows the color-magnitude diagram for stars with errors below the cutoff, and for all 53 fields. We have included lines indicating the halo turnoff color index ($`MT2=0.64`$) and the thick disk turnoff color index ($`MT2=0.80`$) (see Paper I for the determination of these color indices).

The high quality of these data make two populations readily apparent. The thick disk turnoff stars show a concentration with $`16M18.5`$ just redward of $`MT2=0.80`$. The halo turnoff stars are found just redward of $`MT2=0.64`$. They are found at all magnitudes, but increase in number towards fainter magnitudes. As discussed in Paper I, stars between these two color indices comprise our halo turnoff candidate stars. Notice that these two populations have sharp cutoffs in color index. This indicates the photometry calibration is extremely accurate, so as not to blur these populations when combining data from different chips and different fields.

Figs. Mapping the Galactic Halo II: Photometric Survey and Mapping the Galactic Halo II: Photometric Survey are the color-color diagrams for stars with errors below the cutoff, and for all 53 fields. The narrow sequences in these diagrams attest to the high quality of these data, as well as the excellence of the relative calibration between fields. These diagrams are used for identifying halo giant candidates. The details of this selection process are outlined in Paper I. Below we provide a brief overview of this process to demonstrate our photometric accuracy, and the limitations of photometric selection.

$`CM`$ is our primary metallicity indicator. Lower metallicity stars of a given effective temperature will have a bluer $`CM`$ value. Halo stars are expected to be lower metallicity than disk and thick disk stars. Hence, they are found on the right side of the stellar sequence in Fig. Mapping the Galactic Halo II: Photometric Survey. $`M51`$ is sensitive to surface gravity. The dwarfs define a clear sequence that dips to low $`M51`$ values (Geisler, 1984; Paltoglou & Bell, 1994). Giant stars, by contrast, are expected to follow a different sequence with $`M51`$ values that remain near zero (see Paper I).

We have no over-lapping fields to test the relative photometric calibration between fields. However, we can assess the quality from the narrowness of the sequence of stars in the color-color diagrams. For instance, the RMS deviation of stars about the locus of points in Fig. Mapping the Galactic Halo II: Photometric Survey is approximately 0.07. The scatter for a single field is also approximately 0.07. Hence, the increased scatter due to relative calibration errors is at most 0.02. To provide a visual impression of this quality, we have plotted a color-color diagram for a single field (Fig. Mapping the Galactic Halo II: Photometric Survey). Each of the BTC chips is marked with a different symbol. None of the chips shows an obvious offset with respect to the others. Hence, we have judged the relative photometry between chips and between fields to be excellent.

Halo giant candidates are chosen from among those stars that occupy both the low metallicity region in Fig. Mapping the Galactic Halo II: Photometric Survey and the giant region of Fig. Mapping the Galactic Halo II: Photometric Survey. It is evident from Fig. Mapping the Galactic Halo II: Photometric Survey that dwarfs far outnumber giants. In fact, there are not enough giants to form a clear sequence.

We have added symbols to Figs. Mapping the Galactic Halo II: Photometric Survey, Mapping the Galactic Halo II: Photometric Survey, and Mapping the Galactic Halo II: Photometric Survey to indicate preliminary results of spectral follow-up on a subset of the giant candidates. The star-symbols indicate stars that have been confirmed to be halo giants, square-symbols indicate metal-poor subdwarfs, x-symbols indicate dwarfs, and asterisk-symbols indicate non-stellar objects. Our selection of candidates was meant to explore the regions of these diagrams and identify the most efficient means of selecting giant candidates.

These figures indicate that giant stars are readily found in the correct locations, but there is some contamination from dwarfs. The dwarf population arises from two sources. First, and most problematic, are low metallicity subdwarfs. These are photometrically indistinguishable from giants, and we can not eliminate them using photometric observations alone. Second are normal disk dwarfs whose photometric errors scatter them into the selection region. These can largely be eliminated with high-precision photometry, and by using selections based on both luminosity ($`M51`$) and metallicity ($`CM`$).

As expected, this contamination is worse for fainter stars. Fig. Mapping the Galactic Halo II: Photometric Survey is divided into three magnitude bins to demonstrate this effect. The confirmed giants occupy a fairly well bounded region defined by $`0.02(M51)0.09`$, and $`1.1(MT2)1.8`$. This region is marked in Fig. Mapping the Galactic Halo II: Photometric Survey. Note that we have observed some stars spectroscopically outside this region in order to explore the diagram and optimize future candidate selection. In fact, it was this exploration that helped define this region. The candidates with $`(M51)0.02`$ turn out to be predominately dwarfs. The giants not within this bounding box have a fairly high metallicity (\[Fe/H\]$`0.6`$), and would not normally pass the $`CM`$ criteria (see Fig. Mapping the Galactic Halo II: Photometric Survey).

The number of observed candidates within the bounding box defined above is 40. Of these, 22 are confirmed giants for a global identification efficiency of 55%. However, this efficiency is a strong function of magnitude, and the overall giant selection efficiencies are 75%, 59%, and 36% for $`M<17.5`$, $`17.5<M<18.5`$, and $`18.5<M<19.5`$ respectively.

It is more instructive to break these numbers up by subdwarf versus dwarf. The only true failures of the photometric selection are the dwarfs, which scatter into the giant region by measurement errors. The subdwarfs and non-stellar objects will always be found within this region, and cannot be separated from giants by photometry alone. If we restrict the failure count to only dwarfs, the efficiencies, as a function of magnitude, are 100%, 94%, and 82% for $`M<17.5`$, $`17.5<M<18.5`$, and $`18.5<M<19.5`$ respectively. These are very high efficiencies due to the excellent quality of the photometry.

The ratios of giant to subdwarf are 3, 2, and 1 for $`M<17.5`$, $`17.5<M<18.5`$, and $`18.5<M<19.5`$ respectively. This makes going after faint, distant giants difficult. However, we have learned much from these first observations, and by adjusting our selection criteria we can eliminate many of these subdwarfs. For example, by increasing the lower bound of the selection region (Fig. Mapping the Galactic Halo II: Photometric Survey), most of the subdwarfs are eliminated, at the expense of missing several giants. At this point it is unclear where the optimal bounds are to maximize the number of giants. Employing such modifications, we expect our future efficiency to be even higher. Morrison et al. (2000b) explores how this efficiency is affected by photometric precision, and how to further optimize halo candidate selection.

## 5 Summary

We are conducting an imaging survey of high Galactic latitude fields to examine the structure of the Galactic halo. Thus far we have observed 134 separate fields covering a total area of 52 square degrees. We have used 3 different telescopes, and 4 different instruments. We present the details of our automated pipeline reductions designed to handle this large volume of data.

We present results from our most successful observing run using the BTC camera on the CTIO 4m in April 1999. These data are available in the electronic version of this paper, as well as through ADC (http://adc.gsfc.nasa.gov/). All other observing runs occurred in partially bad weather, and are thus not fully calibrated. These data will be published and made available on-line in the future as calibrating observations are obtained.

We discuss preliminary results in identifying halo giants using the Washington filter set. We achieve an overall giant identification efficiency of 66% for $`M<18.5`$. However, most of the non-giant candidates are low-metallicity subdwarfs, which cannot be distinguished from giants using photometric selection alone. The contamination by dwarfs that scatter into the selection region due to photometric errors is only 3% for $`M<18.5`$. This high efficiency is only possible with very accurate photometry. We have also learned much from these first observations, and we expect to improve the efficiency through refinements in the selection technique. Details of our efficiency and refinements in the selection process will appear in a future paper (Morrison et al., 2000b).

We would like to thank Doug Geisler, whose efforts with the Washington filter set have made this work possible. This work was supported by NSF grants AST 96-19490 to HLM, AST 95-28367, AST 96-19632, and AST 98-20608 to MM, and AST 96-19524 to EWO.


format: text

text:
# Cellular Structures determined by Polygons and Trees

## 1. The Real Moduli Space

### 1.1.

The Riemann moduli space $`_g^n`$ of surfaces of genus $`g`$ with $`n`$ marked points has become a central object in mathematical physics. Introduced in Algebraic Geometry, there is a natural compactification $`\overline{}_g^n`$ of these spaces; their importance was emphasized by Grothendieck in his famous *Esquisse d’un programme* . The special case when $`g=0`$, the space $`\overline{}{}_{0}{}^{n}()`$ of $`n`$ punctures on the sphere $`^1`$, is a building block leading to higher genera. They play a crucial role in the theory of Gromov-Witten invariants and symplectic geometry. Furthermore, they appear in the work of Kontsevich on quantum cohomology, and are closely related to the operads of homotopy theory. We look at the real points $`\overline{}{}_{0}{}^{n}()`$ of this space; these are the set of fixed points under complex conjugation. This moduli space will provide the motivation to study certain combinatorial objects.

###### Definition 1.1.1.

The real Deligne-Mumford-Knudsen moduli space $`\overline{}{}_{0}{}^{n}()`$ is a compactification of the configurations of $`n`$ labeled points on $`^1`$ quotiented by the action of $`\mathrm{Gl}_2()`$.

$`\overline{}{}_{0}{}^{n}()`$ is a manifold without boundary of real dimension $`n3`$. The moduli space is a point when $`n=3`$ and $`^1`$ when $`n=4`$. For $`n>4`$, these spaces become non-orientable. Figure 1 shows $`\overline{}{}_{0}{}^{5}()`$ (shaded) as the connected sum of five copies of $`^2`$, with the four hexagonal ‘boundaries’ and the outer circle carrying antipodal action. In general, $`\overline{}{}_{0}{}^{n}()`$ can be described as the iterated blow-ups of real projective spaces (see \[16, §4\], \[8, §4\]), getting extremely complicated as $`n`$ increases.

###### Remark.

The diagram shown in Figure 1 is first found in the work of Brahana and Coble in $`1926`$ \[5, §1\], relating to possibilities of maps with twelve five-sided countries.

### 1.2.

A beautiful fact about the moduli space is its tiling by the convex polytope known as the associahedron $`K_n`$. It is the geometric realization of the poset of all meaningful bracketings on $`n`$ variables. Originally defined for use in homotopy theory by Stasheff \[30, §2\], it was later given a convex polytope realization by Lee . We use an alternative definition:

###### Definition 1.2.1.

The associahedron $`K_n`$ is a convex polytope of dim $`n2`$ with codimension $`k`$ faces corresponding to using $`k`$ sets of non-intersecting diagonals on an $`(n+1)`$-gon.

###### Example 1.2.2.

The associahedron $`K_2`$ is a point. Figure 2 shows the associahedra $`K_3`$, $`K_4`$, and $`K_5`$. For instance, the polytope $`K_4`$ is a pentagon whose sides (codim one faces) are labeled with 5-gons with one diagonal and whose vertices (codim two faces) are labeled with 5-gons with two diagonals.111Mention of diagonals will henceforth mean non-intersecting ones.

We redraw our pictures of dissected polygons so that every region of the dissection becomes a regular polygon without diagonals. In the nomenclature of , we denote the resulting object as a cluster, where each regular polygon of the cluster is called a cell. Thus the polygon shown in Figure 3a with five diagonals is redrawn as a cluster in Figure 3b having six cells. Clearly dissected polygons and clusters are equinumerous, and it is sometimes easier to work with clusters rather than with dissections, as the following important property of the associahedron demonstrates.

###### Proposition 1.2.3.

\[30, §2\] Each face of $`K_n`$ is a product of lower dimensional associahedra.

###### Example 1.2.4.

We look at the top (codim one) faces of $`K_5`$. The three-dimensional $`K_5`$ corresponds to a 6-gon, which has two distinct ways of adding a diagonal. One way, in Figure 4a, shows the $`6`$-gon as a cluster of two $`4`$-gon cells; each cell corresponds to the line segment $`K_3`$, where the product of two such is a square. Alternatively, Figure 4b illustrates the other type of face, which is the product of $`K_2`$ (point) and $`K_4`$ (pentagon).

### 1.3.

It was shown in \[8, §2\] that $`\overline{}{}_{0}{}^{n}()`$ is tessellated by exactly $`\frac{1}{2}(n1)!`$ copies of $`K_{n1}`$. For example, observe from Figure 1 that $`\overline{}{}_{0}{}^{5}()`$ is tiled by twelve $`K_4`$ pentagons. The reasoning is as follows: There are $`n!`$ possible ways of labeling the sides of an $`n`$-gon, each corresponding to an associahedron. However, since there exists a copy of the dihedral group $`D_n`$ of order $`2n`$ in $`\mathrm{Gl}_2()`$, and since $`\overline{}{}_{0}{}^{n}()`$ is defined as a quotient by $`\mathrm{Gl}_2()`$, two labeled polygons (associahedra) are identified by an action of $`D_n`$. Therefore, in some sense, each associahedral domain of $`\overline{}{}_{0}{}^{n}()`$ corresponds to a labeled $`n`$-gon up to rotation and reflection.

###### Definition 1.3.1.

Let $`𝒢(n,k)`$ be the set of equivalence classes of labeled regular $`n`$-gons with $`k`$ diagonals up to the action of $`D_n`$. Let $`G`$ be an element of $`𝒢(n,k)`$ and $`d`$ be a diagonal of $`G`$. The twist of $`G`$ along $`d`$, denoted by $`_d(G)`$, is the polygon in $`𝒢(n,k)`$ obtained by separating $`G`$ along $`d`$ into two parts, ‘twisting’ (reflecting) one of the pieces, and gluing them back (Figure 5). It does not matter which piece is twisted since the two results are identified by an action of $`D_n`$.

###### Theorem 1.3.2.

\[8, §4\] Two polygons, $`G_1,G_2𝒢(n,k)`$, representing codim $`k`$ faces of associahedra, are identified in $`\overline{}{}_{0}{}^{n}()`$ if there exist diagonals $`d_1,\mathrm{},d_r`$ of $`G_1`$ such that

$$(_{d_1}\mathrm{}_{d_r})(G_1)=G_2.$$

The previous statement shows how copies of associahedron glue together to form the moduli space. Figure 6 demonstrates $`\overline{}{}_{0}{}^{4}()`$ tiled by three labeled $`K_3`$’s.

## 2. Categories of Faces

### 2.1.

Recall that faces of associahedra can be represented by dissected polygons. We give the following definitions that categorize the faces of $`K_n`$.

###### Definition 2.1.1.

Two polygons $`G_1`$ and $`G_2`$ are of the same …

*dimension* if their corresponding faces are of the same dimension.

*type* if their corresponding faces are the same polytope.

*class* if they are identified under the actions of $`D_n`$ and twisting.

Dimension, type and class are in increasing order of finer partitions.

###### Example 2.1.2.

In Figure 7, we note the difference between the categories of polygons belonging to $`K_5`$. Recall that the number of diagonals of a polygon is equal to the codim of its face; polygons (a) and (b) are of dim two, and (c) through (e) are of dim zero. In particular, polygons (c) through (e) are of the same type (points) whereas (a) and (b) are not; the polytope (a) is a square and (b) a pentagon. Only (d) and (e) are of the same class; that is, twisting along a diagonal of (d) will result in (e).

It makes sense to decompose the faces into dimensions and polytopes, but what does it mean to talk about classes? The two different classes of points discussed above correspond to the following: At one class (c), three pentagons meet; there are two such points in $`K_5`$. The other class (d) is where two pentagons and one square meet; there are twelve such points. Therefore, classes categorize the different ways polytopes intersect in $`K_n`$. This idea can be extended to better understand the structure of $`\overline{}{}_{0}{}^{n}()`$.

### 2.2.

The combinatorics involving dimensions are handled in . We recall

###### Lemma 2.2.1.

The number of faces in $`K_n`$ of codim $`k`$ is

$$\frac{1}{k+1}\left(\genfrac{}{}{0pt}{}{n+k}{k}\right)\left(\genfrac{}{}{0pt}{}{n2}{k}\right).$$

In other words, given the $`f`$-vector of the polytope $`K_n`$ to be $`f=(f_0,\mathrm{},f_{n3})`$, the number above is $`f_{nk2}`$.

###### Proof.

This was originally proved by Professor A. Cayley in 1891 in finding the number of partitions of an $`(n+1)`$-gon into $`k`$ parts . The recent work of Przytycki and Sikora gives a short and elementary proof while providing relations to knot theory . ∎

###### Remark.

The number of faces in $`K_n`$ of codim $`n2`$ is the well-known Catalan number $`c_n=\frac{1}{n+1}\left(\genfrac{}{}{0pt}{}{2n}{2}\right)`$. That is, there are $`c_n`$ vertices in the associahedron $`K_n`$. It is interesting to note that Stanley shows sixty-six ways to represent the Catalan numbers \[29, Exercise 6.19\]. ∎

These are the three fundamental problems addressed in this paper:

P1. How many different types/classes of codim $`k`$ are there in $`K_n`$ ?

P2. What are the different types/classes in $`K_n`$ of codim $`k`$?

P3. How many faces of $`K_n`$ belong to a given type/class?

In some sense, faces of the associahedron correspond to polygons and faces of the moduli space to labeled polygons. Therefore, since types and classes were defined regardless of labeling, the answers to P1 and P2 both carry over to the moduli space. This is not the case for P3 . However, we find in  a formula (that follows from Theorem 1.3.2) which addresses this dilemma.

###### Proposition 2.2.2.

Let $`\mathrm{\Lambda }(k,𝔛)`$ denote the number of codim $`k`$ faces in the CW-complex $`𝔛`$. Then

$$\mathrm{\Lambda }(k,\overline{}{}_{0}{}^{n+1}())=\frac{n!}{2^{k+1}}\mathrm{\Lambda }(k,K_n).$$

### 2.3.

In what follows, we find solutions to our fundamental problems regarding the classification of types. We try to clarify the situation with the following example.

###### Example 2.3.1.

Looking at the case of $`K_6`$, Lemma 2.2.1 shows there to be $`14`$ codim one faces. Figure 8 shows there to be two different types of such faces (answers P1 ), one being $`K_6`$ and the other a pentagonal prism (answers P2 ). Out of the 14 faces, there turn out to be seven faces of each type (answers P3 ).

Polygons are of the same type if their corresponding associahedral faces have identical polytopal structure. As Proposition 1.2.3 indicates, the polytope structure is solely determined by the number of different cells, not the way these cells are glued to form the cluster. The following notation is well-defined: A face is of type $`3^{m_3}:4^{m_4}:\mathrm{}`$ if it corresponds to a cluster that has $`m_i`$ number of $`i`$-sided cells. The superscript $`m_i=1`$ as well as the terms with $`m_i=0`$ are omitted. For example, the three types in Figure 7 are, respectively,

$$3^0:4^2=4^23^1:4^0:5^1=3:53^4.$$

Define $`p_k(n)`$ to be the number of partitions of $`n`$ into exactly $`k`$ integers $`n_1,\mathrm{},n_k`$, where $`n_i>0`$ and $`n=n_1+\mathrm{}+n_k`$. There is no closed form for $`p_k(n)`$ but the following recurrence relation provides a means to calculate it:

(2.1)
$$p_k(n)=p_{k1}(n1)+p_k(nk).$$

###### Theorem 2.3.2 (Solution to P1 and P2 ).

The number of different types in $`K_n`$ of codim $`k`$ is $`p_{k+1}(n1)`$. The different partitions correspond to the different types, where $`n1=n_1+\mathrm{}+n_{k+1}`$ is associated with the polytope $`K_{n_1}\times \mathrm{}\times K_{n_{k+1}}`$.

###### Proof.

An $`(n+1)`$-gon with $`k`$ diagonals (that is, a cluster containing $`k+1`$ cells) represents a codim $`k`$ face of $`K_n`$. The type of a face depends on the polytope structure; this is soley determined by the cells forming the cluster, not the way in which they are arranged to form the $`(n+1)`$-gon. Associating an $`(n+1)`$-gon to the integer $`n1`$, observe that partitioning the polygon into $`k+1`$ cells is identical to partitioning the integer into $`k+1`$ parts. ∎

###### Theorem 2.3.3 (Solution to P3 ).

When $`k=1+m_i`$ and $`n=1+(i2)m_i`$, the number of faces in $`K_n`$ of type $`3^{m_3}:4^{m_4}:\mathrm{}`$ is

$$\frac{1}{k+1}\left(\genfrac{}{}{0pt}{}{n+k}{k}\right)\frac{(m_3+m_4+\mathrm{})!}{m_3!m_4!\mathrm{}}.$$

###### Proof.

This is proven by Goulden and Jackson \[13, Exercise 2.7.14\]. Their argument is similar to the proof given below for the enumeration of $`A`$-clusters (see §3.1), but without the twist operation and with the extra variables $`m_i`$ in the generating function to mark the numbers of $`i`$-sided regions. From the recursive equation for the generating function, the coefficients (functions of $`m_i`$) are obtained by Lagrange’s theorem and then expanded using the multinomial theorem. ∎

Values computed are shown in Table 1 using Equation 2.1. For each size of polygon, and each distribution of sizes of the cells in the dissection, it gives the number of polygons which have that distribution. An example of an entry for the partition of a 10-gon shows that there are 660 polygons of type $`3^2:4:6`$. That is, there are 660 faces in $`K_9`$ that have the polyhedral structure of $`K_2\times K_2\times K_3\times K_5`$.

## 3. Classes and the Combinatorics of Twisting

### 3.1.

Unlike types, the problem with regard to classes is no longer classical. Counting the number of dissected polygons up to rotation and reflection was studied in .222This is equinumerous to the set of outerplanar graphs. The difference now comes from imposing the additional equivalence relation of twisting. The method used to enumerate classes naturally follows as an extension of .

###### Definition 3.1.1.

A cluster is said to be rooted at an outside edge if one edge (the root) of its perimeter is distinguished from the others. Figure 9a shows the root edge as a thicker line. For convenience, we refer to clusters rooted at an outside edge as $`A`$-clusters.

Let $`a_{m,n}`$ be the number of $`A`$-clusters having $`m`$ cells and $`n`$ outside edges not counting the root edge. Define the generating function

(3.1)
$$A(x,y)=a_{m,n}x^my^n,$$

where for the moment the limits for $`m`$ and $`n`$ are unspecified. For an $`A`$-cluster, there will be one cell with the root edge on its boundary; we can call this the root cell. Assume this cell has $`k`$ unrooted edges. At each of these edges we have the option of gluing the root of some $`A`$-cluster to it.333This gluing is identical to the composition map for operads in the context of rooted trees. Each of these glued clusters contributes its values of $`m`$ and $`n`$ to those of the resulting $`A`$-cluster. For the edges of the root cell at which nothing was glued, the contributions to $`m`$ and $`n`$ are 0 and 1 respectively. Hence the generating function $`A(x,y)`$ will contain the term $`y`$. In the rest of $`A(x,y)`$, $`m`$ goes from 1 upwards and $`n`$ from $`2`$ upwards.

We now have a typical Pólya-class problem.444For information on such problems, see , , . There are $`k`$ sites around the root cell at each of which we can place a figure, an $`A`$-cluster or just an edge, and the parameters $`m`$ and $`n`$ are additive. The figure counting series is the function $`A(x,y)`$ just defined. To accommodate the twisting operation, we must regard an $`A`$-cluster as being equivalent to the one obtained by reversing the root edge — as in Figure 9a and 9b. This reversal interchanges the sites in pairs if $`k`$ is even; if $`k`$ is odd then one site remains fixed while the others interchange in pairs. Hence the cycle-index for this problem is

$`{\displaystyle \frac{1}{2}}(s_1^{2\alpha }+s_2^\alpha )`$ $`k=2\alpha `$
$`{\displaystyle \frac{1}{2}}s_1(s_1^{2\alpha }+s_2^\alpha )`$ $`k=2\alpha +1.`$
By Pólya’s theorem, the generating function for $`A`$-clusters for which the root cell has $`k`$ unrooted edges is obtained by putting $`s_1=A(x,y)\text{ and }s_2=A(x^2,y^2)`$ in the appropriate formula above. Summing for $`k`$ from 2 upwards we get a function of $`s_1`$ and $`s_2`$,

$$\frac{1}{2}\underset{k2}{}s_1^k+\frac{1}{2}(1+s_1)\underset{\alpha 1}{}s_2^\alpha ,$$

which reduces to

$$\frac{1}{2}\left[\frac{s_1^2}{1s_1}+\frac{(1+s_1)s_2}{1s_2}\right].$$

By substituting $`s_1=A(x,y)\text{ and }s_2=A(x^2,y^2)`$ in this expression, multiplying by $`x`$ to account for the root cell, and adding the term $`y`$ which we know must be present, we recover the generaing function $`A(x,y)`$ for $`A`$-clusters. This gives the recursive equation

(3.2)
$$A(x,y)=y+\frac{1}{2}\left[\frac{A(x,y)^2}{1A(x,y)}+\frac{(1+A(x,y))A(x^2,y^2)}{1A(x^2,y^2)}\right].$$

The occurrence of $`A(x^2,y^2)`$ in this equation makes it impossible to obtain a closed form for the coefficients $`a_{m,n}`$ but they can be successively computed as far as one wishes (see Table 2).

###### Remark.

Another proof of Lemma 2.2.1 is obtained by computing the corresponding result above when twisting is not allowed. Then the relevant permutation group is the identity group, with cycle-index $`s_1^k`$, and the analog of Equation 3.2 is

$$V(x,y)=v_{m,n}x^my^n=y+\frac{xV^2(x,y)}{1V(x,y)},$$

where the numbers $`v_{m,n}`$ are the counterparts to the $`a_{m,n}`$ under the new conditions. In this case, as was shown in , a closed result is possible:

$$v_{m,n}=\frac{1}{m}\left(\genfrac{}{}{0pt}{}{n2}{m1}\right)\left(\genfrac{}{}{0pt}{}{m+n1}{n}\right).$$

That is, $`v_{m,n}`$ is the number of codim $`m1`$ faces in $`K_n`$; values are given in Table 3.

### 3.2.

We now turn to clusters rooted at a cell, denoted as $`B`$-clusters. Figure 10 shows a typical $`B`$-cluster, having a distinguished cell (shown shaded) called the root cell. A $`B`$-cluster is obtained by gluing $`A`$-clusters (including possibly the empty $`A`$-cluster) by their roots to the edges of the root cell. If the root cell is $`k`$-sided, we have a Pólya-class problem for which the figure counting series is $`A(x,y)`$ and the permutation group is the dihedral group $`D_k`$.

Since the twisting operation is allowed, the way that the $`A`$-clusters are attached is not important. For this reason we are spared the tiresome necessity of distinguishing between symmetric and asymmetric clusters which had greatly complicated the enumerations performed in . The cycle-index of $`D_k`$ is

$`{\displaystyle \frac{1}{2k}}{\displaystyle \underset{r|k}{}}\phi (r)s_r^{k/r}+{\displaystyle \frac{1}{4}}(s_1^2s_2^{\alpha 1}+s_2^\alpha )`$ $`k=2\alpha `$
$`{\displaystyle \frac{1}{2k}}{\displaystyle \underset{r|k}{}}\phi (r)s_r^{k/r}+{\displaystyle \frac{1}{2}}s_1s_2^\alpha `$ $`k=2\alpha +1.`$
The $`B`$-clusters for a given value of $`k`$ are enumerated by substituting $`A(x,y)`$ in this cycle-index to get the generating function denoted by $`Z(D_k,A(x,y))`$. Hence the set of all $`B`$-clusters is enumerated by

$$B(x,y)=b_{m,n}x^my^n=x\underset{k3}{}Z(D_k,A(x,y)).$$

There seems to be no way of simplifying this expression, but the coefficients can be easily computed as far as desired. Some values for $`b_{m,n}`$ are given in Table 4.

### 3.3.

The next enumeration is for clusters rooted at an inside edge which are asymmetrical about that edge; that is, for which the two clusters at the edge are different (Figure 11). Clearly these $`C`$-clusters, as they can be called, are formed by gluing together two different $`A`$-clusters, neither of which is the empty cluster, at their root edges.

Pólya’s theorem shows the generating function for these clusters would be obtained by substituting $`A(x,y)y`$ in the cycle-index of the symmetric group $`𝕊_2`$, namely $`\frac{1}{2}(s_1^2+s_2)`$, but for the fact that we want the two $`A`$-clusters to be different. A variant of Pólya’s theorem, which is well-known but in any case easily verified, provides the required result by substituting instead in the expression $`\frac{1}{2}(s_1^2s_2)`$. Calling the resulting generating function $`C(x,y)`$, we have

$$C(x,y)=\frac{1}{2}[(A(x,y)y)^2(A(x^2,y^2)y^2)].$$

The final step, going from the generating function for cell-rooted clusters to free clusters (those not rooted at all), is carried out by means of a theorem originally due to Otter  (also see , \[25, §4\]). It states that the generating function for these free clusters, call it $`F(x,y)`$, is obtained by subtracting $`C(x,y)`$ from $`B(x,y)`$. The number $`f_{m,n}`$ of clusters with $`m`$ cells and $`n`$ outside edges, is found from

$$F(x,y)=B(x,y)C(x,y)=f_{m,n}x^my^n.$$

Some values for $`f_{m,n}`$ are given in Table 5. We have just proved

###### Theorem 3.3.1 (Solution to P1 ).

The number of different classes of $`K_n`$ of codim $`k`$ is $`f_{k+1,n+1}`$.

## 4. Trees and the Complex Moduli Space

### 4.1.

As a help in the study of the various classes, we prepared a set of drawings of the corresponding dissected polygons up to ten vertices. Figures 22-26 illustrate the different classes, labeled as $`n.k.i`$ to denote an $`n`$-gon with $`k`$ diagonals where $`i`$ ranges from one to $`f_{n+1,k+1}`$. The computer algorithm for doing this was nothing out of the ordinary, but a few comments on how the drawings were produced may be of some interest. We exploited the connection between dissected polygons and trees as illustrated in Figure 12.555Considering dissected polygons as plane graphs, we obtain trees by taking their weak dual.

Trees dual to dissected polygons are homeomorphically irreducible, having no vertices of degree two.666They are also known as topological or reduced trees. Henceforth, mention of trees will imply homeomorphically irreducible ones. To each dissected polygon, we associate a tree imbedded in the plane. For each diagonal of the polygon, there is a tree edge connecting the two vertices on either side. The twist operation corresponds to reflecting one of the two subtrees at the ends of a given edge. Classes correspond to planar imbeddings of trees up to twisting. In other words, for a given class, each vertex of the tree is given the addition information of preserving the cyclic order of edges around that vertex. The problem was therefore to produce one such tree for each class.

Since the trees needed were quite small, it was not worth devising a clever algorithm; both elegance and efficiency were sacrificed for ease of programming. Rooted trees, the root being a vertex of the tree, were generated step by step according to height. There is one tree of height zero, and those of height one are the stars777Also known as a corolla, a star is a collection of edges meeting at a common vertex. with three or more edges at the root. Those of height two were obtained by grafting a subtree of height at most one, by its root, to the terminal vertices of these stars. In general, trees of height $`k`$ were obtained by grafting trees of height at most $`k1`$. At each stage, if two trees were reflections of each other, only one was retained, thus taking care of the twist operation. This corresponds to producing clusters rooted at an edge, which made possible a check that the right numbers of trees were being produced.

The resulting lists of rooted trees would usually contain several copies of the same unrooted tree. The unwanted duplicates were weeded out by computing for each tree a code similar to that described in  and eliminating all but one of those with the same code. The actual program contained some refinements to the procedure just described but we shall skip the details. It was a fairly simple task to go from trees to dissected polygons. The diagrams888Although diagrams were created for ten-sided polygons, we do not include them here for the sake of space. were then produced automatically using programs that had already been developed for the production of the book An Atlas of Graphs .

###### Proposition 4.1.1 (Solution to P2 ).

The different classes correspond to the different pictures in Figures 22 - 26.

At a later stage we decided to compute for each class the number of fixed dissections of that class. Had we thought of this earlier, it could have been done more easily along with the generation of the classes, but as it was, we derived these numbers directly from the data on the dissected polygons. For each such polygon, we produced the fixed polygons obtainable from it by rotations or by combinations of the twist operation. Note that twisting about some chords leaves the diagram unchanged, in which case there is no point in performing the twist. For example, those chords which have a single polygon on one side fall into this category, and are easily recognised. For ease of programming, only the chords of this kind were exempted from the twist operation; no attempt was made to recognize any others. As a result, duplicates could, and were, produced. However, for polygons with at most ten sides there can be at most five such chords, so the number of duplicates was small. They were eliminated by a suitable coding procedure, similar to that mentioned above for trees. It is reassuring that by summing these numbers for the appropriate sets of classes we recover the numbers given in Table 1.

###### Proposition 4.1.2 (Solution to P3 ).

The number of faces of $`K_n`$ of a particular class is indicated in the top right-hand corner of each picture in Figures 22 - 26.

### 4.2.

As mentioned above, there is a duality between clusters and trees. Clearly each cell of a cluster corresonds to a star in the tree. A face of the associahedron of a given type only recognizes the set of stars, not the way in which they are grafted to form the tree. However, a given class not only sees the underlying tree, but the additional cyclic order of edges around each vertex. Hence, faces of associahedra can be categorized by types, trees, and classes, in increasing order of refinement.

###### Example 4.2.1.

Figure 13 shows three different trees and their corresponding (dual) polygons. All of them are of the same type $`[4^2:5]`$ and all fall into different classes. Note, however, that the first two correspond to the same tree, whereas the third does not. By not preserving the cyclic order of edges, we obtain a distinction that falls between the categories of type and class.

The enumeration of all trees (not just homeomorphically irreducible ones) by their degree partitions is given by Harary and Prins \[15, §4\]. They provide a method for computing the generating function

$$\overline{H}(x,t_1,t_2,\mathrm{})=\overline{h}x^mt_1^{m_1}t_2^{m_2}\mathrm{},$$

where $`\overline{h}`$ is the number of trees having $`n`$ vertices altogether, with $`n_i`$ vertices of degree $`i`$. To get the number of homeomorphically irreducible trees $`h`$ partitioned by degree, we remove the possibility of any degree being two (letting $`t_2=0`$). This involves only standard enumerative procedures and the details are omitted. We give below the equations that determine the required generating function for homeomorphically irreducible trees.999The symmetric function notation for cycle-indexes has been used (see ). For example, we write $`h_n[P]`$ in place of $`Z(𝕊_n,P(x,t_1,t_2,\mathrm{}))`$.

$`P`$ $`=`$ $`x(t_1+t_3h_2[P]+t_4h_3[P]+\mathrm{})`$
$`R`$ $`=`$ $`x(t_1P+t_3h_3[P]+t_4h_4[P]+\mathrm{})`$
$`H`$ $`=`$ $`Ra_2[P]`$
###### Theorem 4.2.2.

The number of different trees in $`K_n`$ of codim $`k`$ is given by the above generating function

$$H=H(x,t_1,t_3,\mathrm{})=hx^mt_1^{m_1}t_3^{m_3}\mathrm{},$$

where $`m=n+k+1`$, $`m_1=n`$, and $`{\displaystyle \underset{i3}{}}m_i=k+1`$.

We note in passing that all homeomorphically irreducible trees up to $`16`$ vertices are depicted in  together with their degree partitions.

### 4.3.

Roughly speaking, faces of the associahedron correspond to polygons and faces of the moduli space to labeled polygons. Both types (polytope structures) and classes (intersections of polytopes) are natural objects in the associahedron and the moduli space. We extend our idea of trees by labeling their external vertices. Unfortunately, labeled trees are of little use to $`\overline{}{}_{0}{}^{n}()`$; the trees shown in Figure 14 are identical considered as labeled trees and yet distinct as faces in $`\overline{}{}_{0}{}^{n}()`$.

However, labeled trees are exactly what are needed to understand the points of the complex moduli space $`\overline{}{}_{0}{}^{n}()`$. A rough sketch for this is as follows: The real moduli space $`\overline{}{}_{0}{}^{n}()`$ comes from a configuration of labeled points on $`^1`$ (viewed as a circle). Keeping track of the cyclic ordering of these points is crucial, since two adjacent labeled points can switch places only by first colliding with each other. Points on a circle give rise to the planarity of trees, and the collision/permutation of adjacent points are kept track of with the twist operation. The situation is different for the complex case. $`\overline{}{}_{0}{}^{n}()`$ is based on a configuration of labeled points on $`^1`$ (viewed as a sphere). There are diffeomorphisms of the sphere which can permute any two labeled points without their need to collide, giving rise to non-planar trees. This is the fundamental reason that the underlying structures are classes for $`\overline{}{}_{0}{}^{n}()`$ and trees for $`\overline{}{}_{0}{}^{n}()`$.

###### Remark.

We point out a few observations about moduli spaces and trees.

1. The codim $`k`$ faces of $`\overline{}{}_{0}{}^{n}()`$ correspond to labeled trees with $`n`$ external vertices and $`k+1`$ internal vertices. In particular, both $`\overline{}{}_{0}{}^{n}()`$ and $`\overline{}{}_{0}{}^{n}()`$ have the same number of zero dim cells, enumerated by binary trees with labeled external vertices. In other words, the twist operation on planar binary trees removes the restriction of planarity.

2. There are operad structures related to the moduli spaces $`\overline{}{}_{0}{}^{n}()`$  and $`\overline{}{}_{0}{}^{n}()`$ , classically described in terms of labeled trees \[4, §1.4\]. The associahedron is related to $`A_{\mathrm{}}`$ structures, whereas $`\overline{}{}_{0}{}^{n}()`$ seems to play a similar role in Fukaya’s Lagrangian Floer cohomology.

3. Kapranov  has defined a natural double cover of the moduli space $`\overline{}{}_{0}{}^{n}()`$ by fixing one of the $`n`$ distinct labeled points in $`^1`$ to be $`\mathrm{}`$. Similar to $`\overline{}{}_{0}{}^{n}()`$, this double cover also has an underlying structure of labeled trees \[8, §4.3\] with two exceptions. First, the trees are no longer free but rooted at the label $`\mathrm{}`$. Second, twisting is allowed except along the edge containing the root.

4. The reason for these moduli spaces to be characterized by trees without degree two vertices is due to the stability condition coming from Geometric Invariant Theory \[18, §8\]. GIT gives a natural compactification of the space of genus zero algebraic curves which are stable in the sense of having only finitely many automorphisms; that is, the curves cannot have just two distinguished points. ∎

## 5. The Isotropy Group

### 5.1.

There is a natural action of the symmetric group $`𝕊_n`$ on $`\overline{}{}_{0}{}^{n}()`$ which permutes the labelings of the $`n`$-gon. This action is certainly not free; therefore, for a given face $`f`$ in $`\overline{}{}_{0}{}^{n}()`$, its isotropy group $`𝔖_f𝕊_n`$ need not be trivial, where

$$𝔖_f=\{\sigma 𝕊_n|\sigma (f)=f\}.$$

Given two distinct faces of $`\overline{}{}_{0}{}^{n}()`$ which are of the same class, their isotropy groups are isomorphic; in fact, they are conjugate subgroups in $`𝕊_n`$. We wish to determine, up to isomorphism, the isotropy group of a given class; we interchangably write $`𝔖_f`$ to denote the isotropy group of $`f`$ and its isomorphism class.

###### Example 5.1.1.

Let $`f`$ be the face of $`\overline{}{}_{0}{}^{8}()`$ given in Figure 15a; its class is $`\mathrm{8.2.7}`$. Its isotropy group is generated by the reflections $`\{(68),(35),(12)(83)(74)(65)\}`$. Since the reflections commute, $`𝔖_f`$ is isomorphic to the direct product $`_2^3`$. As discussed above, all isotropy groups of class $`\mathrm{8.2.7}`$ will be isomorphic. In particular, a face $`g`$ of the same class, as shown in Figure 15b, will have a conjugate subgroup $`𝔖_g=(24)(567)𝔖_f(765)(42)`$.

###### Corollary 5.1.2.

For a given class $`n.k.i`$, let $`\kappa `$ be the number of faces in $`K_{n1}`$ of this class. The number of faces in $`\overline{}{}_{0}{}^{n}()`$ of the class $`n.k.i`$ is

$$\kappa \frac{(n1)!}{2^{k+1}}.$$

###### Proof.

This immediately follows from Propositions 2.2.2 and 4.1.2. ∎

This can be obtained using another approach: Choose a dissected polygon representing the class $`n.k.i`$. Under all possible labelings, there are $`n!`$ such polygons, many of which are identified in $`\overline{}{}_{0}{}^{n}()`$. Since the isotropy group maps the polygon to itself in the moduli space, we quotient $`n!`$ by the order of the isotropy group $`|𝔖_f|`$, where $`f`$ is any face in $`\overline{}{}_{0}{}^{n}()`$ of the given class. This provides another answer to for the Corollary above; combining the results, we find a solution to P3 alternate to the one given in Proposition 4.1.2.

###### Proposition 5.1.3.

The number of faces in $`K_{n1}`$ of the class $`n.k.i`$ is

$$\frac{n2^{k+1}}{|𝔖_f|}.$$

### 5.2.

The following sketches one possible algorithm for finding the group $`𝔖_f`$. This is done locally (looking at each cell of the cluster under twisting) and globally (looking at the entire dissected polygon under the dihedral group).

###### Definition 5.2.1.

For a connected graph $`G`$, the distance between two vertices $`x,y`$ is the minimum of the lengths of paths containing $`x`$ and $`y`$. The eccentricity of a vertex is the maximum of its distances to all other vertices. The center of $`G`$ is the subgraph induced by the vertices of minimum eccentricity.

It is a classic result of graph theory that the center of a tree is either one vertex or one edge. Taking the dual, the center of the dissected polygon is either a cell or a diagonal.

Non-central cells: For each non-central cell of the polygon, observe if there exists an automorphism of the cell obtained by twisting along diagonals. If such a map exists, then this contributes $`_2`$ to $`𝔖_f`$. Figure 16b shows the class $`\mathrm{9.4.10}`$ as a cluster, with the central cell shaded. Out of the four non-central cells, three of them have a $`_2`$ action (Figure 16c), contributing $`_2^3`$ to the isotropy group.

Central diagonal: If the center is a diagonal, there are two possibilites: Observe whether or not there exists a (global) reflection along the central diagonal. Figure 17 shows class $`\mathrm{8.3.8}`$ with reflection and class $`\mathrm{8.3.10}`$ without.

Central cell: If the center is a cell, there are three possibilites. Figure 18a shows class $`\mathrm{9.5.3}`$ with the central cell (shaded) having no symmetry. The cell could also have just a reflection action (class $`\mathrm{9.3.11}`$), as in Figure 18b. Finally, for an $`n`$-gon, there could be a dihedral action $`D_k`$ on the central cell, where $`k`$ divides $`n`$. Figure 18c shows class $`\mathrm{9.6.4}`$ with the $`D_3`$ group action.101010Although the picture shown has obvious $`_3`$ rotation symmetry, reflection is also possible due to twisting.

Since there are no intersecting diagonals, the different twists and reflections, along with any dihedral group action, all commute. Therefore, to find the isotropy group, we look at the contribution of each local and global action and simply take their direct product. For example, the isotropy groups (up to isomorphism) for the polygons of Figure 18 are $`_2^4`$, $`_2^4`$, and $`_2^3\times D_3`$, respectively. Using Proposition 5.1.3, we calculate $`\kappa `$ for each of the classes to be $`36`$, $`9`$, and $`24`$, respectively, matching the values obtained from Proposition 4.1.2.

###### Remark.

Each class corresponds to a polytope. By definition, each element of the isotropy group maps the polytope to itself; but what type of map is it? Using Figure 15a as an example of a face $`f`$, we show how the generators of $`𝔖_f`$ act on the polytope. Note that the polytope structure of $`f`$ is a cube, the product of three line segments, as labeled in Figure 19. The actions of the three generators of $`𝔖_f`$ given in Example 5.1.1 are the reflections along the shaded planes.

## 6. Applications

### 6.1.

We first point out a few interesting similarities to classical combinatorics \[7, §1.15\]. As noted above, partitioning of an $`n`$-gon using $`k`$ diagonals corresponds to using $`k`$ sets of brackets meaningfully on $`n1`$ non-commutative variables (see Figure 20).

The Generalized bracketing problem of Schröder is to find the number $`s_n`$ of different bracketings of $`n`$ variables using an arbitrary number of brackets (where each bracket must contain at least two elements). Lemma 2.2.1 gives us the number of different bracketing for a fixed set of $`k`$ brackets. Summing up, we find

$$s_n=\underset{k=0}{\overset{n2}{}}\frac{1}{k+1}\left(\genfrac{}{}{0pt}{}{n+k}{k}\right)\left(\genfrac{}{}{0pt}{}{n2}{k}\right).$$

The Wedderburn-Etherington commutative bracketing problem is to find the number $`w_n`$ of ways of using $`n2`$ sets of brackets meaningfully on $`n`$ commutative variables. In other words, it is the number of different bracketings that arise from commuting binary subproducts. It is not too hard to see that $`w_n`$ gives the number of $`(n+1)`$-gons with maximal diagonals rooted at an outside edge, identified up to reflection along the root edge and twisting along diagonals, but not rotation. It follows that $`w_n=a_{n1,n}`$ (see Table 2). Figure 21 shows $`w_4=2`$ and $`w_5=3`$ as polygon and bracketing representations.

###### Remark.

The coefficients of the generating function of Equation 3.1 generalize the Wedderburn-Etherington numbers: The possible ways of using $`k`$ brackets on $`n`$ commutative variables is $`a_{k+1,n}`$.

### 6.2.

We mention two occurrences outside mathematics that encode information using labeled trees. The first is in biology; in particular, the areas of genetics and evolution . The theory of evolution conjectures that there exist links between certain species to common ancestors using the evidence from protein sequences. An evolutionary tree, or phylogeny, is a means of organizing this data: The external (labeled) vertices represent species for which data is available whereas the internal (unlabeled) vertices are the hypothetical ancestors for which no direct evidence is known. Phylogenies usually have no vertices of degree two. The following emumerates the number of phylogenies having a fixed set of leaves.

###### Proposition 6.2.1.

\[10, §2\] For $`n`$ external vertices, the number $`T_n`$ of labeled trees is given by the following recurrence relation, where $`T_2=T_1=1`$:

$$T_n=(2n)T_{n1}+\underset{1in2}{}T_{i+1}T_{ni}\left(\genfrac{}{}{0pt}{}{n1}{i}\right).$$

###### Remark.

A few observations follow:

1. Just as the generalized bracketing problem of Schröder sums over all cells of $`K_n`$, the Proposition above sums over all the cells of $`\overline{}{}_{0}{}^{n}()`$.

2. A rooted phylogeny is a rooted labeled tree where the root does not receive a label. The root of a phylogeny represents the ancestor of all organisms of the tree. For $`n`$ labeled external vertices, the number $`P_n`$ of distinct rooted phylogenies is $`P_n=T_{n+1}`$ \[10, §2\].

3. There exist many possible metrics on phylogenetic trees . It was also noted in  that one can give lengths to the edges of labeled trees, making them weighted, which hold data on the time estimate of evolution taking place between two species of the tree. Recently, a space of phylogenetic trees was constructed, closely related to the ‘dual’ of $`\overline{}{}_{0}{}^{n}()`$ ; the metric on this tree space inherits some properties from the natural metric on $`\overline{}{}_{0}{}^{n}()`$ \[8, §2.2\].

4. The idea of phylogeny even extends to literature, in understanding the authenticity of the manuscripts of The Canterbury Tales . ∎

### 6.3.

Another appearance of labeled trees is in physics; in particular, the quantum theory of angular momentum. Given a system of $`n`$ independent parts, each with its own angular momentum, the theory deals with constructing the total angular momentum by coupling the given $`n`$ momenta sequentially in pairs using $`SU(2)`$ Wigner coefficients. Biedenharn and Louck further relate this to the Racah-Wigner algebra and the 6-$`j`$ symbols \[2, §5\]. Enumerating the various binary coupling schemes gives a total of $`c_n`$ possibilities, thought of as counting maximal bracketings on $`n`$ variables (zero dim cells of $`K_n`$). Permuting two angular momenta implies a phase change in their state vectors. Considering binary coupling schemes over all such permutations yield $`n!c_n`$ possibilites (zero dim cells in $`n!`$ copies of $`K_n`$). However, in quantum physics it is not possible to distinguish state vectors differing by phase factors; schemes are identified by commuting binary subproducts. This yields $`(2n3)!!`$ possible coupling schemes (zero dim cells in $`\overline{}{}_{0}{}^{n+1}()`$). As noted, the idea of binary coupling closely follows the gluing of associahedra to form the moduli space, at least in the zero dimensional case. Although combinatorially the idea of coupling momenta can be generalized beyond binary pairs (by possibly counting the codim $`k`$ cells of moduli spaces), the meaning of this in the context of theoretical physics is not yet well understood.

###### Acknowledgments.

The authors would like to acknowledge their indebtedness to, and admiration for, the work of Professor Arthur Cayley, who not only addressed a dissection problem similar to the one in this paper, but also laid the foundations for the enumerative study of tree-like structures in general. This pioneering work is all the more remarkable in that it was only a small part of the mathematical output of this eminent Victorian.

###### Remark.

For size limitations, we have not included Figures 22-26 in this paper. One can obtain the paper with the figures at: www.math.ohio-state.edu/$``$ devadoss.