text:
# Distribution of star-forming complexes in dwarf irregular galaxies

## 1 Introduction

Dwarf irregular galaxies exhibit peculiar morphologies that are dominated by the flashy but seemingly irregular presence of star-forming regions. Unlike with more massive disk systems that modulate star formation by spiral density waves, dwarf irregulars in the field — or non-interacting irregulars in general — constitute ideal testbeds for the study of genuine processes regulating local and global star formation and consequently of galactic evolution. A review addressing several key questions concerning large-scale star formation in irregular galaxies is given by Hunter (1997), and an evaluation among simple models for the onset of star formation in irregulars is provided by Hunter, Elmegreen, & Baker (1998).

Important clues as to hidden constraints shaping the heterogeneous appearance of dwarf irregular galaxies may emerge from detailed investigations concerning the spatial distribution of star-forming regions (e.g., Feitzinger & Braunsfurth 1984). In recent years several studies on the distribution of H II regions and of young, compact star clusters in late-type spirals and in dwarf irregular galaxies have appeared (Telles, Melnick, & Terlevich 1997; Brosch, Heller, & Almoznino 1998; Elmegreen & Salzer 1999; Heller et al. 2000; Roye & Hunter 2000; Billett, Hunter, & Elmegreen 2002). Applying measures like concentration, asymmetry, and fractional-luminosity indices these authors found the star forming regions to be distributed rather randomly, with some tendency to central concentrations particularly for star-bursting systems.

In this paper we extend these previous studies by analysing the distribution of bright spots or lumps in the $`B`$-band images of a sample of 72 late-type (“irregular”) dwarf galaxies. The general equivalence of bright lumps in H$`\alpha `$ and in broad band blue images as tracers of star formation complexes can be appreciated by comparing galaxy images filtered at the two corresponding wavelengths (e.g., Elmegreen & Salzer 1999; Sparke & Gallagher 2000, pp. 139 and 229). With our homogeneous and relatively large sample at hand we aim at comparing three morphological indices with each other (as applied to lumps within irregulars), none of which has been previously reported in the form presented here or within our context. Indices often serve as the quantitative counterparts to qualitative physical concepts. In particular, lump spreading within a galaxy may be described by concentration indices of different apertures; lump clustering may be represented by the correlation dimension for the two-dimensional lump distribution; finally, the lumpiness (or flocculency) of a galaxy may be measured by means of some fractional light index. Table 1 gives a summary of terms and indices that will be more carefully introduced in the subsequent sections.

Comparing relations among morphological indices, we may deepen our insights into the various mechanisms responsible for the morphology of irregulars. The interstellar matter of dwarf irregulars with different global properties may be different (e.g., metallicity, mean gas density, turbulence, gravitational potential), implying differences in the conditions for the formation of stars. Thus aspects concerning the abundance and distribution of star-forming regions within the galaxies, like clustering and star formation rates, may turn out to vary correspondingly. We adress this issue by means of the clustering parameter. Another goal of the paper is to contribute to the discussion concerning the influence of shear due to differential rotation on star formation in gas-rich late-type galaxies (Roye & Hunter 2000; Elmegreen, Palouš, Ehlerová 2002). Based on cellular automata simulations we introduce a possible criterium to be checked for in radial lump number distributions; we show that a few of our galaxies indeed meet the criterium, but more research is needed for conclusive results.

The paper is organised as follows. Section 2 gives an overview of the galaxy sample used and presents a table with basic galaxy parameters as well as the parameter values deduced in the subsequent sections. Section 3 describes the adopted lump detection method and introduces a first index, the lumpiness index. Section 4 presents the radial number and number density distributions for the bright lumps of all the galaxies. A concentration index that is normalized according to the galaxies being exponential-disk systems is introduced and applied to the bright lump distribution. We then extensively discuss the possible reason for a peculiarity seen in the lump number distribution, namely the occurence and relative locations of major and minor peaks. In Section 5 we determine the cluster or correlation dimension for the two-dimensional lump patterns, relate it to galaxy absolute magnitude, and deduce a model mean porosity that is linked to the current star formation rate. In Section 6 we check for relations among the three indices introduced in the previous sections. We end with a discussion and the conclusions in Section 7. Image processing was performed throughout within the IRAF111IRAF is distributed by the National Optical Astronomy Observatories; http://iraf.noao.edu. package.

## 2 The sample

The sample of 72 irregular dwarf galaxies is a compilation of Im, BCD, and late-type S galaxies fainter than $`M_B=18`$ mag — dwarf “irregulars” for short — used previously for an analysis of exponential-disk model parameters relating photometric, kinematic, and environmental properties (Parodi, Barazza, & Binggeli 2002). The galaxies are lying in the field or in groups within the nearby 10 Mpc volume. They were imaged with 1.2-m to 1.5-m telescopes with resolutions of 0.39-0.77 arcsecs per pixel and under seeing conditions varying between 0.8 and 4.0 arcsecs. Data reduction was performed consistently by our team along the usual prescriptions. $`B`$-band galaxy image galleries can be found in Parodi et al. (2002) and the references given therein (or at the bottom of Table 2 in the present paper).

In Table 2 we list basic galaxy data as well as parametric data as deduced in the subsequent sections. The first nine columns are mostly taken over from Table 1 in Parodi et al. (2002), while the seven other columns correspond to results obtained in the present paper. The columns read as follows:
Columns 1 and 2 give the galaxy name and the galaxy type;
columns 3 and 4 list the $`B`$-band absolute magnitude and — from fitting an exponential law to the observed surface brightness profile — the extrapolated central surface brightness, both corrected for galactic extinction;
columns 5, 6, and 7 give the $`B`$-band disk scale length along the semi-major axis (in parsecs), the radius of the 25th-mag/arcsec2 isophote (in parsecs), and the axis ratio of the elliptical isophote, respectively;
column 8 lists the rotational velocities of the galaxies as far as measured. The four entries for the southern hemisphere galaxies ESO473-G024, IC2038, ESO490-G017, and ESO059-G001 are based on HIPASS 222The HI Parkes All-Sky Survey, or HIPASS, is a 21-cm HI survey of the southern sky undertaken with a multibeam receiver on the Parkes telescope in Australia. The one-dimensional spectral data for a freely choosable position is available for downloading in a variety of different formats at http://www.atnf.csiro.au/research/multibeam/release/. public data, treated as in Parodi et al. (2002);
column 9 points to the five published papers of our series with original and detailed observational and photometric data on the galaxies. Cf. the reference notes on the bottom of Table 2;
column 10 indicates the number of bright lumps found in residual galaxy images (Section 3);
columns 11, 12, and 13 give the scale length of the radial number density distribution of the bright lumps (Section 4.2), the radius of the highest peak in the radial lump number distribution, and the peak radius of a possible secondary, minor peak, respectively (Section 4.4) (all lengths in units of scale length $`R_d`$);
columns 14, 15, and 16 list the values for the following indices: the normalized concentration index $`CI`$ measured using $`R_{25}`$ as the outer aperture radius (Section 4.3), the reduced cluster (or correlation) dimension $`D`$ (Section 5), and the lumpiness index $`\chi `$(Sections 3 and 6), respectively.

## 3 Lump detection and lumpiness index

A residual image highlighting bright star-forming complexes — comprising H II regions and young clusters — was constructed by subtracting a smoothed version from the original $`B`$-band image for each galaxy. To obtain the former image a convenient method is to median filter the original image with a sliding square window. Relying instead on adaptive filtering techniques (i.e., on the IRAF task ADAPTIVE) did not improve on the results, thus we kept applying the simple median filtering method. For the window $`w`$ some characteristic metric size should be chosen: we adopted $`w=0.2R_{\mathrm{eff}}`$, with $`R_{\mathrm{eff}}`$ being the effective radius of the galaxy. An example of images processed this way can be seen in Fig. 1. The galaxy shown is ESO 473-G024, with the left frame containing the original image, and the right frame presenting the residual image. From these latter, high-spatial frequency images we extract the following information:

(i) we detect and tabulate the locations of the bright lumps, thus constructing a data base for the distribution analysis below. Detection of bright lumps was done automatically and thus consistently for all galaxies. First, the sky-subtracted residual image is cleaned around and, concerning obvious foreground stars, within the galaxy. The few foreground stars that probably went undetected should have no potential to fake the statistical outcomes of this paper. Second, an appropriate point spread function (PSF) was looked for: a routine checks for the maximum pixel value corresponding to the brightest lump and determines its PSF. It may happen that the brightest lump takes part in a compact cluster of lumps; thus if the PSF’s full-width-at-half-maximum was more than 10 pixels the routine assumed blending and searched for a smaller lump with a narrower PSF. Similarly, if the PSF was very peaky, an overseen foreground star was assumed and a broader PSF was applied for the lump search. Third, this PSF is then used by the IRAF task DAOFIND to search for all other lumps above a detection threshold of 3 sky sigmas. In ESO 473-G024, for example, 22 bright lumps were thus counted. Some galaxies are too fuzzy-looking to have any lumps detected. Finally, lump coordinates are stored in physical units with the center and the major axes of the 25th-mag/arcsec2 isophotal ellipse providing the origin and the axes of the coordinate system; assuming axisymmetry, the lump coordinates will be deprojected to zero ellipticity for all applications. Note that we do not estimate lump luminosities in order to compare lump brightnesses or to provide luminosity functions; for blue luminosity functions of star-forming complexes in spiral and irregular galaxies see Elmegreen & Salzer (1999).

(ii) We determine the galaxy’s lumpiness index $`\chi `$. Lumpiness (or flocculency) of a galaxy may be quantified by the high spatial frequency power $`\chi `$, pioneered by Isserstedt & Schindler (1986) and recently applied by Elmegreen & Salzer (1999) to spiral and irregular galaxies and by Takamiya (1999) to HDF-N galaxies with the aim of having a galaxy structural parameter at hand that is related to the current star formation rate. Following the notation of Takamiya (1999) it is defined as the ratio of the flux from the bright lumps, $`f_l`$, and the total flux $`f_g`$ of the galaxy, thus

$$\chi =\frac{f_l}{f_g}.$$

By measureing the total fluxes of the residual and the original images for each galaxy, we obtained the $`\chi `$ values listed in Table 2. The lumpiness index will be applied below in Section 6.

## 4 Radial distributions of detected bright lumps

### 4.1 Number distribution

In Fig. 2 we show for all galaxies of the sample the binned radial number distributions of the detected bright lumps. Histogram bins correspond to concentric elliptical annuli with semi-major axes successively growing by half a scale length $`R_d`$ and shown out to 8 $`R_d`$; the last bin included in the panels comprises all the detected lumps at radii larger than 7.5 $`R_d`$. The number of counts per bin, $`N_{\mathrm{norm}}`$, is normalized by the largest bin value within 7.5 $`R_d`$; the largest bin value as well as the total number of counts are printed within each panel. This kind of normalization was imposed to minimize the effects of different resolutions and seeing conditions for the following inquiry.

The accumulated radial number distribution $`N_{\mathrm{norm}}^{\mathrm{total}}`$ for the lumps of all the galaxies, i.e. summing up all the profiles of Fig. 2, is shown as histogram in Fig. 4. The bright-lump distribution of many galaxies thrown together is represented by a radius-weighted exponential distribution that is indicated by the solid line obeying $`N(R)Rexp(R/R_l)`$ with $`R_l=0.86R_d`$ (cf. Section 4.2). This basically reflects the exponential light profiles of dwarf irregular galaxies in general with, however, a slightly shorter scale length than is seen for the $`B`$-band continuum light (dashed line). Note that bright lumps or star-forming complexes not only are found way out to large radii, but that they constitute a nice tail in the radial number distribution out to at least six optical scale lengths, a point we come back to in the discussions of Section 7.

The similar exponential structure for two components of the disk is comparable to H II region distributions in other types of exponential-disk galaxies. In intermediate-type spirals (Athanassoula et al. 1993) and in irregular galaxies (Hunter et al. 1998) the azimuthally averaged radial distribution of H II regions follows the stellar light distribution as well. In our dwarf irregular galaxies bright lumps are exhibiting this same behaviour, indicating them to be representative for the distribution of H II regions, as expected. We can put this statement on a still firmer basis tracking down also the radial number density distribution of the bright lumps.

### 4.2 Number density distribution

Radial number density distributions for the bright lumps are obtained by dividing the number of counts in a given bin by the surface of the corresponding elliptical annulus (cf. Hodge 1969, Athanassoula et al. 1993). The bright-lump number density profiles for our galaxies are shown in Fig. 3. Solid lines represent exponential fits for galaxies with a total of at least 10 detected lumps; their scale lengths $`R_l`$ are given in each panel in units of $`B`$-band continuum light scale lengths $`R_d`$ and are listed in Table 2. For the whole sample we find a mean of

$$<R_l/R_d>=0.86\pm 0.06,\sigma =0.41.$$
(1)
Thus, while the number density distributions of bright lumps are — at least partially — also exponential, their slopes are on average steeper than those for the density distributions of the underlying stellar light. We note that this very same quantitative behaviour was also observed for the number density distribution of H II regions in intermediate-type spiral galaxies: Athanassoula et al. (1993) found $`<R_{HII}/R_d>=0.8`$, $`\sigma =0.4`$.

Concluding this subsection we state that dwarf irregular galaxies show azimuthally summed-up bright-lump profiles that are quantitatively comparable to those of H II regions in exponential-disk systems. Thus, as expected, bright star-forming complexes largely represent H II regions. In particular, the scale lengths for H II regions, for bright lumps on $`B`$-band images, and for $`B`$\- and $`R`$-band continuum light images (Parodi et al. 2002) obey on average the ratio equation $`R_{HII}:R_l:R_d(B):R_d(R)0.8:0.9:1.0:1.1`$, i.e. the older the underlying population the larger the scale lengths. This general trend in star-forming dwarfs has been observed before, and we discuss some implications in Section 7.

### 4.3 Concentration index

The concentration index $`CI`$ of a galaxy is a convenient parameter to quantify galaxy morphology of low- and high-redshift galaxies. It compares the light content for different radial intervals. Various definitions have been used, none of which takes into account the exponential-disk constraint. It is, however, a trivial observation that in scale length-versus-luminosity diagrams the scatter in scale length around the mean relation correlates with the concentration index. To have a scale length-independent concentration index we will explicitely factor in this underlying disk feature. Following Heller et al. (2000) for the sake of comparision, the concentration index $`CI(R)`$ is taken as the ratio of the flux or, in our case, the number of complexes within an elliptical aperture of semi-major radius $`R/2`$, i.e. from the inner part of the galaxy, to the flux or number of complexes from its outer annulus with inner and outer semi-major radii of $`R/2`$ and $`R`$, respectively. Opposite to Heller et al. (2000) — who suspect linear radial distributions of the (flux from) star forming regions — we do not bring the two numbers to an equal-area basis by dividing the outer number of lumps by a factor of three. Instead, we want to relate the measured lump $`CI`$ to the corresponding one for an assumed underlying radial number distribution $`N(R)Rexp(R/R_d)`$ (or, as it is more adequate for lumps, $`Rexp(R/R_l)`$; see below). We thus normalize our galaxy concentration index with $`CI_0(R)=_0^{R/2}N(r)𝑑r/_{R/2}^RN(r)𝑑r`$. Expressing the total radius $`R`$ in terms of the disk scale length $`R_d`$, $`R=xR_d`$, one finds

$$CI_0(x)=\frac{\left[1(1+x/2)e^{x/2}\right]}{\left[(1+x/2)e^{x/2}(1+x)e^x\right]}.$$
(2)
Thus our normalization constant $`CI_0(x)`$ depends on the chosen outer radius $`R`$, or $`x`$, respectively, used to determine the concentration index. On a statistical footing the 72 dwarf irregular galaxies of our sample share the mean ratios $`R_d:R_{eff}:R_{25}:R_{995}`$ $``$ $`1:1.5:3:5.1`$ in the continuum $`B`$-band light, where $`R_{eff}`$ is the effective radius, $`R_{25}`$ is the 25th-mag/arcsec2 isophotal radius, and $`R_{995}`$ is the radius equivalent to an aperture with 99.5% of the total flux. Theoretically, pure exponential-light decays yield $`R_d:R_{eff}:R_{25}:R_{995}`$ $`=`$ $`1:1.7:4.1:7.4`$, where the value for $`R_{25}`$ was interpolated using the observed mean ratios given above. The fact that our galaxies exhibit on average smaller radii is a consequence of the exponential-disk description being only an approximation; in particular, there is a large fraction of bright galaxies with central light cusps. The appropriate normalization constants corresponding to the above radii are then $`CI_0(1)`$=0.52, $`CI_0(1.5)`$=0.64, $`CI_0(3)`$=1.23, and $`CI_0(5.1)`$=3.01.

With this normalization we expect the concentration indices to be $`CI1`$. Deviations from this canonical value provide information on the actual shapes of the profiles. For example, the median values of the concentration indices obtained by Heller et al. (2000) for their dwarf irregular (BCD + LSB) galaxy sample are — corrected to our normalization by adopting their limit $`R=R_{25}`$ and thus applying $`CI_0=1.23`$ — (4.23/3)/1.23 = 1.15 and (3.43/3)/1.23=0.93 for the H$`\alpha `$-flux and the continuum images, respectively. Thus BCD and LSB galaxies are rather well represented by exponential light profiles on large parts. However, the values for the BCDs typically lie above and those for the LSBs below these median values, reflecting the fact that the former galaxies are more actively star forming in the center regions than the latter. Returning to our sample, we arrive at values $`CI=`$0.94, 1.26, 1.32, 1.73 for outer radii $`R=`$2, 3, 4, 5 $`R_d`$, respectively. These values typically being larger than one and even increasing with larger outer radii is due to the normalization used so far that was based on the continuum light scale length $`R_d`$.

However, if the lump scale length $`R_l`$ is used for the normalization instead of $`R_d`$, one indeed recovers $`CI1`$. This is shown in Fig. 5 where we have plotted the normalized concentration indices $`CI(x)`$ of our galaxies for various aperture radii $`R=xR_l`$ against their rotational velocities, now adopting the mean scale length $`R_l=0.86R_d`$ found for the lumps in Section 4.2. Actually, one would prefer to adopt for each galaxy its particular lump scale length, but given the uncertainties in determining them, we are content with the mean value given in equation (1). Only galaxies with at least five detected lumps are included, leaving about 50 galaxies. Infinite values result for $`CI`$s in the case of no outer-annuli lump detections; in the plots they are included as triangle symbols with values fixed at $`CI=13`$. Data for the upper right panel is listed in Table 2. The panel’s median $`CI`$ values, plotted as dashed lines and ignoring the $`CI`$=$`\mathrm{}`$ cases, are 0.83, 1.24, 0.95, and 1.04. Lying all in the vicinity of one, this is consistent with the annulus-integrated exponential distribution for the summed lump number distribution seen in Fig. 4 out to large radii.

Thus, applying the analytic tool of the concentration index, we have again demonstrated that the radial distribution of star forming regions is non-linear but follows an annulus-integrated exponential distribution. This implies a non-uniform random spread of the star forming regions throughout the disk, which explains the discrepancy found by Heller et al. (2000) between the $`CI_{H\alpha }`$ values for actual galaxies and the lower ones for simulated galaxies with random star formation region positions. Roye & Hunter (2000) pointed out an increased scatter of concentration indices for faster rotating galaxies of their sample. In the upper right panel, data from Roye & Hunter (2000), adopted to our normalization using $`CI_0(3.5)=1.53`$ (assuming $`R_{25}`$=3$`R_d`$=3.5$`R_l`$) and with a median $`CI`$ value of only 0.58, are plotted, too; however, we no longer see this effect in any panel with our larger sample.

### 4.4 Peak number distribution: shear-enhanced star formation at work?

For the sample as a whole the radial locations of bright lumps mirror the exponential intensity distribution of the underlying population. This is, however, only a rule-of-thumb. Individual galaxies may exhibit strong deviations from this mean statistical behaviour (cf. Fig. 2). For example, the primary peak in the radial number distribution (i.e. the bin with the highest value) appears not around one scale length, but is shifted to smaller or higher radii. The histogram for the radial distributions of primary peaks only is shown in Fig. 6, left (thin-lined bars). Only galaxies with peaks corresponding to at least three counts are included. The expected maximum of occurences of primary peaks around one scale length is clearly recovered; a Gaussian with a mean at one scale length and a standard deviation of 1.4$`R_\mathrm{d}`$ is overplotted as the dashed line. However, another particular feature of individual lump number histograms is the frequent presence of a secondary peak that is lower than the main peak (instead of monotonicly smaller bin heights on both sides of the main peak); this is the case for about a third of our galaxies (cf. Fig. 2). The radii of primary peaks (with at least three counts) and secondary peaks are listed in Table 2; in a few cases of equal height peaks we refered to 0.1 $`R_d`$-bin width number distributions to decide which of the peaks is the primary or the secondary one. While the primary peaks of those galaxies exhibiting a second, minor peak as well are crowded around one scale length (thick-lined bars), the corresponding distribution of secondary peaks reveals a pronounced maximum at about two scale lengths (shaded bars).

Is this excess of bright stellar complexes at radii larger than about two scale lengths a statistical fluctuation or is it a manifestation of some underlying mechanism? A candidate mechanism that deserves closer inspection is shearing due to differential rotation within the outer part of the disk. We thus discuss the physical plausibility for the influence of shearing on the generation of star-forming complexes within dwarf galaxies. Two questions will be adressed: First, is shearing in dwarf galaxies a viable mechanism? And second, can it account for the observed peak distribution?

A compilation of 20 high quality dwarf galaxy rotation curves by Swaters (2001) shows them to look much like those of spiral galaxies, with rotation curves rising steeply in the inner parts and flattening in the outer parts. In particular, most dwarf galaxy rotation curves start to flatten around two disk scale lengths, and no dwarf galaxy shows solid-body rotation beyond three disk scale lengths anymore. Concerning our observed occurence of minor peaks in the bright lump distribution, starting at and being most pronounced at about two scale lengths as well, we may wonder whether it is related to the transition from solid-body to differential rotation. Affirmative signals arrive both from theory and simulations. (i) Larson (1983) suggested that the SF rate increases with higher shear rate via the “swing amplifier” mechanism: citing Toomre he points out that shear itself contributes strongly to the growth of gravitational instabilities, leading to gas density enhancements and subsequent star formation. For dIs, however, lacking spiral-density waves, swing amplification may seem an inappropriate mechanism to rely on. (ii) Alternatively, in their review Seiden & Schulman (1990, p. 40) remind that in models for stochastic self-propagating star formation (SSPSF) shearing increases the density of star-forming regions: gas-rich, potential star-forming regions are transported to and mixed with former star-forming regions, giving space for new star formation. (iii) Additionally, while it has been questioned whether shear may cause any visible effect at all given dwarf galaxies being rather slowly rotating systems (Hunter et al. 1998), it becomes more and more evident that some irregular galaxies like the Large Magellanic Cloud or NGC4449 possess regular, large-scale magnetic fields (e.g., Otmianowska-Mazur et al. 2000), and thus it similarly becomes feasible that the magneto-rotational instability (e.g., Balbus & Hawley 1998) comes into play, effectively strengthening the effects of shear. Bearing in mind this possibility, we nevertheless restrain the discussion in the following on the second of these scenarios only.

Self-propagating star formation is observed with many galactic as well within many extragalactic objects. It is thought of as a locally important SF triggering mechanism in all types of galaxies. For example, modulated by density waves, long-lived spiral arms may be formed in bright disk galaxies (Smith, Elmegreen, & Elmegreen 1984); the surface filling factor of bubbles and the locations of molecular rings in observed disk galaxies can be quantitatively explained by SSPSF (Palouš, Tenorio-Tagle, & Franco 1994); age gradients in star-bursting galaxies can be accounted for by means of triggered star formation (Thuan, Izotov, & Foltz 1999; Harris & Zaritsky 1999); and last but not least, the general burst characteristics of compact and irregular dwarf galaxies is long known to partially be understood by means of SSPSF (Gerola, Seiden, & Schulman 1980; Comins 1984).

Relying ourselves on a two-dimensional SSPSF model, we numerically tested the hypothesis that the onset of shear-induced star formation around the turnover radius may leave its imprint in an overabundance of SF regions or of bright stellar complexes beyond two scale lengths. In the Appendix we describe the particular implementation. A general finding of our simulations is that the inclusion of shear (i.e. rotation) allows for about five to ten percent more star forming cells, the exact value depending on the particular parameters used. Being mainly interested in the azimuthally summed-up radial distribution of lumps under different rotational conditions, we compare simulation runs with and without a transition to a flat rotation curve. In the top panel of Fig. 6, right, a typical outcome for a simulation of 20 galaxies with rigidly rotating disks is plotted. The highest peaks are found to be located around one scale length, while the secondary peaks show occurences at many radii but with a preference for locations around two scale lengths. This coincides with our observed peak distributions. For comparision, in the bottom panel of Fig. 6, right, a representative peak distribution for a simulation run of 20 galaxies that exhibit a continuous transition from solid-body to (strong) differential rotation at two scale lengths is shown. Interestingly, the primary peaks now occur preferentially at around two scale lengths indicating a strong influence of shear on star formation around the turnover radius. While this is not the general picture observed with our sample, some of the brighter galaxies actually do match this pattern: IC 1959, ESO 154-G023, Ho I, NGC 5477.

We thus conclude that the observed pattern of primary peaks at one scale length manifests the underlying exponential-disk systems, and that the frequent occurence of secondary peaks at about two scale lengths is not necessarily related to the onset of strong shear in rotating disks. As the simulations show, it is however consistent with the idea of triggered star formation based on a stochastic self-regulation scenario. Some of the larger galaxies are exhibiting pronounced primary peaks at two scale lengths but show minor peaks at one scale length; with these galaxies we may be directly witnessing shear-induced star formation. The possible role of bars will be reflected in Section 7.

## 5 Clustering properties of bright lumps: cluster dimensions on scales of a few 100 pc

Star-forming complexes in dwarf galaxies form non-random point patterns also in a sense different from that discussed in Section 4.3. Their positions correlate according to a self-similar (fractal) arrangement. In this Section we substantiate this claim studying an index devoted to spatial statistics, namely the correlation or clustering dimension, as applied to two-dimensional bright-lump distributions.

As observed by Elmegreen & Elmegreen (2001), the distribution of bright-lump center positions on a kiloparsec scale in spiral and irregular galaxies obey a power-law behaviour similar to the fractal structure of the interstellar gas with fractal dimension $`D_3=2.3`$. Thus the center positions of star-forming aggregates within isolated areas of large galaxies are fractal. Here we address the question whether star-forming complexes that are scattered over the entire disks of dwarf galaxies are non-randomly distributed as well. We restrict our inquiry to the dwarfs of our sample that exhibit more than 20 bright lumps. Given our photometry with image scales of typically well above 10 parsecs/pixel and seeing conditions of a few pixels we expect to only dissolve structures larger than about 100 parsecs. Thus small-scale clustering and the accompagning blending effects (Elmegreen & Elmegreen 2001) are of no concern to our study. To quantify the spatial clustering of the position patterns we adopt the cumulative distance method (Hastings & Sugihara 1996): a power law relationship $`N(r)r^D`$ is assumed for the cumulative number of points $`N(r)`$ within a distance $`r`$ around each point. If the distribution is (at least partially) self-similar this will be manifested in a $`log(N)`$-$`log(r)`$ diagram as a straight line with slope $`D`$, called the cluster (or correlation) dimension,

$$D=\frac{d\mathrm{log}N(r)}{d\mathrm{log}r}.$$

The more highly clustered the points (at all relevant scales), the lower the cluster dimension. For a random or Poissonian distribution of points on a two-dimensional plane one has $`D2`$, independent of the number of points involved, which only governs the error estimate. The graphs for six observed galaxies with 20-30 lumps and for five galaxies with about 200-300 lumps are shown in Fig.7, left, plotted with thin and thick lines, respectively. For both groups the relevant scaling range, i.e. the straight part of the curve, lies between about 100 ($`\sqrt{2}^{13}`$) and 1000 ($`\sqrt{2}^{20}`$) parsecs. The galaxies with lower lump numbers exhibit smaller cluster dimensions ($`D1.5`$) than the galaxies with many detected lumps ($`D1.9`$). However, plotting $`D`$ versus $`N_{lumps}`$ for all our data (not shown), no clear relation between the two quantities is seen anymore. There nevertheless is a hidden dependence between the two variables: it emerges from the non-uniform distribution of lumps in exponential-disk systems (as discussed in Section 4), and it is to be corrected for. We do so by, first, simulating point patterns with exponential radial number density distributions and indeed are recovering the observed dependence of the cluster dimension on the number of lumps. In particular, accepting a linear regression we obtain $`D_{simul}=0.0013N_{lumps}+1.471`$. Actually, a function converging asymtotically toward $`D`$=2 for large lump numbers would be more appropriate; having no clue as to its exact form, though, we stay within the linear approximation. Then, second, instead of using the observed cluster dimensions as inferred from galaxy images, we introduce reduced cluster dimensions defined by $`DD_{obs}0.0013N_{lumps}`$, i.e. all measured cluster dimensions are made comparable by formally adjusting them to the common number $`N_{lumps}`$=0. Other values could have been chosen; however, the adopted value (or other low values, say $`N_{lumps}`$$`\stackrel{_<}{_{}}`$50) yields consistently cluster dimensions of about or below the theoretical maximum value of two. We show in Fig.7, right, the reduced cluster dimension as a function of the extrapolated central surface brightness for all galaxies. There is a weak but significant trend that fainter dwarf galaxies exhibit lower cluster dimensions, i.e. more strongly clustered star-forming regions, than brighter dwarf galaxies. The same statement holds if instead of central surface brightness we take the absolute magnitude of the galaxy.

We have also determined the cluster dimensions for 15 selected sub-galactic areas (consisting of about 30 lumps within a circle of about 1.5 kpc diameter) within larger galaxies (each with a total of more than about 200 lumps). With a mean of $`D`$$``$1.85 and a scatter of only about 0.1, these areas show relatively high cluster dimensions that are typically lying above their galaxies’ values. It furthermore implies that cluster dimensions for local lump aggregates scatter less than those for entire galaxies.

We now attempt to give an interpretation of the reduced cluster dimension in terms of intragalactic gas porosity and star formation rate. The volume filling factor $`f`$ of the empty or low-density regions of a self-similar medium, the porosity, can be related to the medium’s fractal dimension in three dimensions, $`D_3`$, by

$$f=1\left(\frac{r_l}{r_u}\right)^{3D_3},$$

where $`r_l`$ and $`r_u`$ are the lower and upper boundary of the relevant scaling range (e.g., Turcotte 1992). From Fig.7, left, and as mentioned above, we infer $`r_l100`$ pc and $`r_u1000`$ pc. This approach to galaxy porosity is analogous to Elmegreen’s (1997) treatment of fractal interstellar gas clouds, the porosity of which was characterized by $`f_{ICM}=1C^{(D_3/3)1}`$, with a maximum density contrast of $`C10^310^4`$ for the intracloud gas. The two approaches are formally and numerically similar if we identify $`C=(r_u/r_l)^310^3`$. Qualitatively, dwarf irregular galaxies may thus be considered as huge star-forming clouds similar to fractal intragalactic star-forming clouds. Solving for the dimension, we obtain

$`D_3`$ $``$ $`3+log(1f).`$ (3)
Interpreting Fig.7, right, in terms of galaxy porosity, we have to take into account that the scaling dimension of a projected isotropic self-similiar object is one less than the true dimension (Elmegreen & Elmegreen 2001), thus $`D_3=D+1`$. We then learn that on average fainter galaxies with on average lower cluster dimensions, i.e. with stronger clustering properties, are also more porous ($`D1.5`$, $`f0.7`$) than brighter galaxies ($`D1.9`$, $`f0.2`$).
Theoretically porosity is thought to be crucial for the self-regulation of disks, and one expects an increasing star-formation rate to be accompagnied with decreasing porosity (Silk 1997, equ. 7). This holds empirically as well, as we will sketch now. For dwarf irregular galaxies the area-normalized star formation rate is correlated with the galaxy’s extrapolated central surface brightness: from Fig. 7a in van Zee (2001) we infer $`\mu _B^01.79_{\pm 0.18}\mathrm{log}(SFR/area)+18.214_{\pm 0.334}`$, with $`area\pi (1.5R_d)^2`$ and $`R_d`$ being the exponential-model scale length in kpc. On the other hand, an ordinary least-squares bisector fit (Isobe et al. 1990) to the data of Fig. 7, right, yields $`\mu _B^0=3.25_{\pm 1.01}D+26.862_{\pm 1.560}`$, shown as line in the figure. Equating the two expressions, inserting equation (3), and remembering $`D=D_31`$, we finally deduce

$`SFR[\mathrm{M}_{}\mathrm{yr}^1]`$ $``$ $`0.45(1f)^{1.8}(R_d[\mathrm{kpc}])^2.`$ (4)
Within our model treatment of dwarf irregular galaxies being self-similar objects we thus have semi-empirically established a statistical relation between SFR, scale length, and porosity, in the sense that for a given scale length galaxies with higher SFRs are also less porous. Note that for a given scale length, equation (4) predicts a maximum SFR. However, porosity as defined above has to be understood as a conceptual parameter and not as a quantity describing reality in detail. The parameters possibly influencing the mean porosity of a galaxy are manyfold (gas density, gas pressure or velocity dispersion, gas metallicity, supernova energy release), forming an intricate, interdependent parameter set (Silk 1997).

## 6 Comparing clustering, spreading, and relative luminosity of the lumps

In the course of this paper we encountered three indices, namely the lumpiness index $`\chi `$(Section 3), the concentration index $`CI`$ (Section 4.3), and the cluster dimension $`D`$ (Section 5). The first one has been introduced only, but has not been applied until now. To make up leeway and to draw some first conclusions, we plot in Fig. 8 the values resulting from applying the three indices against each other. Several distinctive features are present. First, and most notable, the lumpiness index $`\chi `$ anticorrelates with cluster dimension (upper left panel): the higher the lumpiness index , i.e. the higher the fraction of total galaxy light in the lumps, the smaller the cluster dimension, i.e. the more clustered are the bright lumps. Without plotting the corresponding graphs, we note that the lumpiness index shows no dependence on galaxy luminosity; this is contrary to the behaviour of the cluster dimension. In terms of porosity, this behaviour means that lumpier galaxies are also more porous, and vice versa.

Second, the degree of lumpiness and concentration behave such that the galaxies with the highest values for the lumpiness index all have low values for the concentration index (lower panel). In other words, high fractional lump luminosities come with star-forming complexes that are widely scattered within a galaxy disk. On the other hand, those galaxies with lumps very centrally concentrated, i.e. with $`CI`$$`>`$3, come with low fractional lump luminosities, i.e. with low $`\chi `$values. This is somewhat surprising because there are BCD- and BCD-like galaxies with central starbursts (high $`CI`$) that are expected to be very lumpy (high $`\chi `$) at the same time. But indeed, no galaxy with high fractional lump luminosity is observed, not even a BCD galaxy, to be centrally concentrated. This means that even for actively star-forming galaxies the main body of light is still clearly dominated by the total galaxy light. We disclaim a selection bias to the disadvantage of dwarfs with central starbursts in the next section by providing two representative examples.

Finally, no relation seems to hold between concentration index and cluster dimension (right panel). In particular, galaxies with highest lump concentrations present any cluster dimensions. In other words, lump location and the degree of self-similar clustering are independent of each other; this argues, as done in Section 4, for the introduction of some mean galaxy porosity that may vary among galaxies.

## 7 Discussion and conclusions

Regarding the azimuthally integrated, radial distribution of bright lumps — corresponding to star-forming complexes — in dwarf irregular galaxies, we find them non-uniformly distributed. While in individual galaxies the number distribution is non-monotonic and rugged, the summed-up distribution for all galaxies of our sample manifests the hidden constraint, which is a $`re^r`$-distribution closely tracing the underlying older population. More precisely, in terms of radial number density distribution the lumps follow an exponential decay with scale length about 10 percent smaller on average than that of the blue continuum light. This is consistent with studies of the radial distribution of H II regions in intermediate-type spiral galaxies (Athanassoula et al. 1998). The fact that each component of the average disk — from star-forming site number density to surface brightness of the total light — is approximately exponential is a hint that luminous exponential disks are born rather than made, consistent with the accretion scenario for the viscous evolution of galaxy disks (e.g., Ferguson & Clarke 2001). Star-forming complexes in irregular dwarf galaxies can be found out to large radii, as already emphasized by Schulte-Ladbeck & Hopp (1998), Brosch et al. (1998), and Roye & Hunter (2000). The presence of a tail in the accumulated radial number distribution of star forming regions out to at least six optical scale lengths (Fig. 4) indicates that the distributions of dwarf irregulars are truncated at rather low gas density thresholds for star formation. (van Zee et al. 1997, Hunter et al. 1998, Pisano et al. 2000); this seems to be different with many spiral galaxies for which sharp to weak truncations, starting at galactocentric radii of 2-4 near-infrared or 3-5 optical scale lengths, have persistently been reported (e.g., recently, Florido et al. 2001, Kregel et al. 2002, Pohlen et al. 2002).

Beside the presence of main or primary peaks in the radial lump number distribution at slightly less than one optical scale length on average, there is — contrary to the expectations for exponential-disk systems — the frequent occurence of secondary peaks at about two scale lengths. As simple simulations show, it is consistent with the idea of triggered star formation based on a stochastic self-regulation scenario. However, some of the brighter, larger galaxies exhibit pronounced primary peaks at two scale lengths and show minor, secondary peaks around one scale length. For these galaxies with a reversed peak pattern the simulations indicate that shear-induced star formation around the disk’s turnover to differential rotation could be at work; we feel this issue worth a deeper investigation: given a lump statistics based on higher-resolution images and linked to detailed rotational velocity data, and possibly supplemented with information on large-scale magnetic field structures, this may lead to some subtle but decisive insights related to star formation in irregular galaxies. Also, the possible role of bars or bar-like central features should be carefully considered. However, as none of our four galaxies with principal peaks appering around two scale lengths is classified as “barred”, and because Roye & Hunter (2000) did not see a preferential location of H II regions towards the ends of bars in the two candidate galaxies of their sample, we do not consider this mechanism as being effective in shaping the number distribution of lumps.

The observation that the scale lengths are the larger the older the underlying respective population is, goes in hand with the finding that in star-forming dwarf galaxies the oldest populations are also the most extended ones (Gardiner & Hatzidimitriou 1992, Minniti & Zijlstra 1996, Minniti et al. 1999, Harris & Zaritsky 1999). The common interpretation is that of an age-related dispersion of stars. Because dynamical disk heating tends to saturate at a fixed velocity dispersion (Freeman & Bland-Hawthorn 2002) the amount of radial spread introduced by dynamical heating is expected to be larger in smaller galaxies with lower gravitational binding energies (J. Gallagher, private communication). Indeed, the fact noted in Parodi et al. (2002) that with increasing scale length the disk color gradients become systematically less positive and even start being weakly negative when going from dwarf irregular to low-surface brightness and spiral galaxies — which is equivalent to larger galaxies having red-to-blue band scale length ratios below one — seems to support the idea that the extent of the red component decreases as galaxy mass increases. However, for spirals part of this colour trend is most certainly a metallicity effect.

We provide no investigation of the azimuthal lump distribution; where necessary we assumed axisymmetry. Applying different asymmetry indices to dwarf and normal irregulars, Heller et al. (2000) and Roye & Hunter (2000) obtained opposing results that were dependent on the definition of the chosen index (asymmetry as a question of perception). Also, it was found that while the conveniently applied rotational asymmetry index may be used as a first discriminator between (distant) elliptical and spiral/irregular galaxies (Schade et al. 1995, Conselice et al. 2000), this parameter actually is strongly dependent on recent star formation (Takamiya 1999, Mayya & Romano 2001) and thus must be correlated with the lumpiness index as adopted in the present paper. As we have no data for the star formation rate of our galaxies, an immediate comparision cannot be offered, however.

Applying a concentration index $`CI`$ that is normalized according to the exponential-disk structure of a mean lump distribution leads to consistent results for varying aperture sizes. It may also remove the discrepancy found by Heller et al. (2000) between the $`CI_{H\alpha }`$ values for actual galaxies and the lower ones for simulated galaxies with random star formation region positions. Roye & Hunter (2000) pointed out an increased scatter of concentration indices for faster rotating galaxies of their sample; we no longer see this effect with our larger sample.

Comparing concentration ($`CI`$) with lumpiness ($`\chi `$) we find the galaxies with a high percentage ($`>10\%`$) of light stemming from the lumps showing low to moderate concentrations ($`CI\stackrel{_<}{_{}}2`$), i.e., galaxies with lumps that are widely scatterd within the disk maintain a higher fraction of the total $`B`$ luminosity (Fig. 8). On the other hand, for very concentrated galaxies ($`CI\stackrel{_>}{_{}}2`$) less than about 10 percent of the light is due to the lumps; actually, for these galaxies the values for the lumpiness index $`\chi `$ fluctuate around the sharp value of 7% attributed to most of the (barred) spiral and irregular galaxies observed by Elmegreen & Salzer (1999). They suggested the similarity of the blue-band light fraction in complexes for several galaxies of different Hubble types and different total luminosities being due to similar star formation efficiencies.

It remains, however, remarkable that galaxies with very high lump concentrations are not among the galaxies showing high $`B`$ luminosity fractions of the lumps (Fig. 8, bottom panel). One may wonder whether some of the nearby, well-known BCDs with central starbursts would agree with this conclusion as well, i.e. whether their central bursts should not dominate the total light content. We therefore examined where the typical starburst dwarf irregular galaxies NGC 1569 and NGC 1705 would fill in the $`CI`$ vs. $`\chi `$diagram. Based on the 48 brightest central star clusters of NGC 1569 as compiled in Hunter et al. (2000) and adopting a distance of 2.5 Mpc and a galaxy absolute magnitude of $`M_V=17.99`$ mag, we estimate a mere $`\chi 0.10`$ for NGC 1569. Similarly, for the super-star cluster dominated amorphous galaxy NGC 1705, the absolute magnitude for the 7 brightest clusters is about $`M_V=14.1`$ according to the data in O’Connell et al. (1994), whereas the galaxy has a magnitude of $`M_V=16.13`$ at a distance of 5 Mpc, implying only $`\chi 0.15`$. Thus independent of the exact concentration indices for the brightest clusters, these two small but representative galaxies with central starbursts would not occupy the empty part of the $`CI`$ vs. $`\chi `$ diagram. This means that the empty region in this figure is not a selection effect, but may be related to our adopted procedures in determining the corresponding indices.

While the concentration index is a measure for lump spreading, the cluster or correlation dimension provides information on the scaling behaviour for lump-to-lump distances. We found the lump cluster dimensions — corrected for the effect of radial abundances according to the annulus-integrated exponential distribution — to lie between 1.3 and 2.0 and to gently correlate with extrapolated central surface brightness and absolute magnitude of the host galaxy. At the same time the cluster dimension is weakly anticorrelated with the lumpiness index.

Cluster dimension (or porosity) as introduced in this paper may be intimately linked to the sizes of the largest, kiloparsec-sized lump compounds (Elmegreen et al. 1996) or to the sizes of star-forming, collapsed expanding shells (e.g., Walter 1999). Elmegreen et al. (1996) found the sizes of the largest compounds within spiral and irregular galaxies to approximately scale with the square root of the galaxy luminosity, or, if normalized by the galaxy semi-major axis $`R_{25}`$, small galaxies to have slightly larger relative compound diameters than larger galaxies. This was hypothesized to result from gravitational instabilities with the Jeans length or the mean virial density varying with galaxy luminosity. Walter (1999) suggests the holes in dwarf irregulars to be larger than those in late-type spirals because small galaxies have lower masses and correspondingly lower gravitational potentials and lower ambient ISM gas densities, favoring H I shells to grow larger. Alternatively, we are temptatively interpreting the cluster dimension of a galaxy in terms of the volume filling factor of empty regions in a fractal medium, i.e. in terms of porosity (defined analogous to Elmegreen 1997), and find the following statistical trends: (i) fainter galaxies tend to be more porous; (ii) more porous galaxies also have a lumpier morphology with lower central lump concentrations; (iii) the more porous the galaxy, the lower the star formation rate per kpc2 (equation 4). While these trends are not unexpected, we provide an objective and quantitative statistical treatment of these.

Porosity, or self-similarity, as observed with the bright-lump distribution within dwarf irregular galaxies reflects the self-regulated evolution of the interstellar medium, with stellar feedback and self-gravitation being the main mechanisms. It is thus not to be confused with the still self-similar pattern of dispersed stellar aggregates that initially formed from the fractal interstellar gas, obeying the canonical value of $`D`$=1.3 for turbulence-driven star formation (Elmegreen & Elmegreen 2001). Our sub-galactic areas are showing $`D`$$`\stackrel{_>}{_{}}`$1.7, i.e. much higher fractal dimensions. We suspect that in dwarf irregular galaxies either the dispersive redistribution of stars is indeed much more effective than in spiral galaxies (Elmegreen & Hunter 2000), and/or that feed-back regulation is responsible for the partially randomized position patterns (e.g., due to the intersection of giant shells).

###### Acknowledgements.

B.R.P. thanks Helmut Jerjen for introducing him to IRAF and for pointing out the HIPASS data release interface. Valuable recommendations by the referee, J. Gallagher, helped to improve the paper. Financial support by the Swiss National Science Foundation is gratefully acknowledged.

## Appendix A The SSPSF model

The implementation of the stochastic self-propagating star formation (SSPSF) disk model is a variant of the prescriptions found in the reviews of Schulman & Seiden (1986) and, in more detail, Seiden & Schulman (1990). Major modifications are an exponentiated initial disk structure, a transition from a linearly increasing to a flat rotation curve, and the inclusion of spontaneous star formation. In particular, our model consists of 80 corotating rings, each with 6R cells, R being the ring number or radius. Thus we have a total of 18960 cells. Initially, for each ring the number of occupied cells, $`N(r)`$, has a probability proportional to a Gamma distribution $`Rexp(R/R_d)`$, with the scale length taken to be $`R_d=16`$. On average the galaxies of our sample have a scale length of about 0.7 kpc, thus the linear size of each cell corresponds to about 44 pc. The polar angles for the $`N(r)`$ cells in a ring are randomly chosen. At the start there are a total of 300 occupied cells. The life time of an occupied cell is 10 time steps, corresponding to about 10 Myr. The first time step following the activation of a cell, an empty neighbouring cell has a probability of 0.21 to become activated too. This implements the idea that the stellar wind of massive stars created in a cluster travels with a wind velocity of about 40 km s-1 for about 1 Myr forming an increasingly dense shell that eventually fragments or hits other overdense regions, thus giving chance to the formation of new star-forming sites. At each time step, an additional 20 new cells are spontaneously activated; this sustains the number-density profile being exponential. Typically, an equilibrium occupation of around 1400 cells is reached after a few dozen time steps (providing a filling factor around 0.07), 10 percent of which having been just activated, and with the number density distribution remaining rather exponential out to about four scale lengths; further out there is a rapid drop or truncation of star-forming regions.
Either the rings rotate rigidly, with circular velocity being proportional to the ring radius, or differential rotation may be imposed by additionally demanding a constant circular velocity beyond a turnover radius $`R_t=2R_d`$. For the simulations that included shear a flat rotation curve velocity of 500 km s-1 was enforced, which is an unrealistic factor of $``$10 faster than observed for a typical dwarf irregular. However, this was only to clearly demonstrate the effect of strong shear within the model. As long as the circular velocity is much higher than the radial propagation velocity, shear seems to increase the star formation rate. For each simulated galaxy the number (and number density) distribution after 500 time steps was stored for use in the study of Section 4.4. The lump patterns and their corresponding distributions for a typical simulated galaxy can be seen in Fig. 9. Note that we simulate only the occurence of new and the presence of young stellar clusters, but otherwise assume a prevailing underlying population of older stars.


format: text

text:
# Untitled Document

Realization of the Stasheff polytope

Jean-Louis Loday

Abstract We propose a simple formula for the coordinates of the vertices of the Stasheff polytope (associahedron) and we compare it to the permutohedron.

Introduction.

The Stasheff polytope $`𝒦^n`$, also called associahedron, appeared in the sixties in the work of Jim Stasheff \[St1\] on the recognition of loop spaces. It is a convex polytope of dimension $`n`$ with one vertex for each planar binary tree with $`n+1`$ leaves. There are various realizations of $`𝒦^n`$ as a polytope in the literature (cf. \[Lee, GKZ, T, St2, D, CFZ\]). Here we propose a simple one which has the following advantages, on top of being simple:

– it respects the symmetry,

– it fits with the classical realization of the permutohedron $`𝒫^n`$,

– the faces have simple equations.

To any planar binary tree we associate a point in the euclidean space by describing its coordinates (which are going to be positive integers) in terms of the structure of the tree. Explicitly the $`i`$th coordinate is the product of the number of leaves on the left and on the right side of the $`i`$th vertex. The main idea is to start with the permutohedron and to think of it as the truncation of the standard simplex by some hyperplanes. Truncating only by the admissible hyperplanes gives the Stasheff polytope. From the explicit equations of the facets of the permutohedron we compute the coordinates of the intersections of the admissible hyperplanes and find the result mentioned above.

Convention. In the euclidean space $`𝐑^n`$ the coordinates of a point are denoted $`x_1,\mathrm{},x_n`$. We denote by $`H`$ the affine hyperplane whose equation is: $`_{i=1}^{i=n}x_i=\frac{1}{2}n(n+1)`$. We adopt the notation $`S(n)=\frac{1}{2}n(n+1)`$.

1. A simple realization of the Stasheff polytope

The Stasheff polytope $`𝒦^n`$ of dimension $`n`$ (alias associahedron) is a finite cell complex whose $`k`$-cells are in bijection with the planar trees having $`nk+1`$ internal vertices and $`n+2`$ leaves (so it is sometimes denoted $`K_{n+2})`$, cf. \[St1\].

Let $`Y_n`$ be the set of planar binary trees with $`n+1`$ leaves:

$$Y_0=\{|\},Y_1=\{\text{ }\text{Γ}\text{Γ}\},Y_2=\{\text{ }\text{Γ}\text{Γ}\text{ },\text{ }\text{Γ}\text{Γ}\text{ }\},$$

$$Y_3=\{\text{ }\text{Γ}\text{Γ}\text{ }\text{ },\text{ }\text{Γ}\text{Γ}\text{ }\text{ },\text{ }\text{Γ}\text{Γ}\text{ }\text{ },\text{ }\text{Γ}\text{Γ}\text{ }\text{ },\text{ }\text{Γ}\text{Γ}\text{ }\text{ }\}.$$

The integer $`n`$ is called the degree of $`tY_n`$. We label the leaves of $`t`$ from left to right by $`0,1,\mathrm{}`$. Then we label the internal vertices by $`1,2,\mathrm{}`$. The $`i`$th vertex is the one which falls in between the leaves $`i1`$ and $`i`$. We denote by $`a_i`$, resp. $`b_i`$, the number of leaves on the left side, resp. right side, of the $`i`$th vertex. The product $`a_ib_i`$ is called the weight of the $`i`$th vertex. To the tree $`t`$ in $`Y_n`$ we associate the point $`M(t)𝐑^n`$ whose $`i`$th coordinate is the weight of the $`i`$th vertex:

$$M(t)=(a_1b_1,\mathrm{},a_ib_i,\mathrm{},a_nb_n)𝐑^n.$$

For instance: $`M(\text{ }\text{Γ}\text{Γ})=(1),M(\text{ }\text{Γ}\text{Γ}\text{ })=(1,2),M(\text{ }\text{Γ}\text{Γ}\text{ })=(2,1),`$ $`M(\text{ }\text{Γ}\text{Γ}\text{ }\text{ })=(1,2,3),M(\text{ }\text{Γ}\text{Γ}\text{ }\text{ })=(1,4,1)`$.

Observe that the weight of a vertex depends only on the subtree that it determines.

We will show in the next section that all the points $`M(t)𝐑^n`$ for $`tY_n`$ lie in the affine hyperplane $`H`$. The main point of this paper is the following result.

1.1 Theorem. The convex hull of the points $`M(t)𝐑^n`$, for $`t`$ a planar binary tree with $`n+1`$ leaves, is a realization of the Stasheff polytope $`𝒦^{n1}`$ (alias associahedron) of dimension $`n1`$.

The proof will be given in the next section.

Let us recall the definition of the permutohedron (alias zylchgon). For any permutation $`\sigma `$ in the symmetric group $`S_n`$ acting on the set $`\{1,\mathrm{},n\}`$ let $`M(\sigma )𝐑^n`$ be the point with coordinates $`M(\sigma )=(\sigma (1),\mathrm{},\sigma (n))`$. By definition the permutohedron $`𝒫^{n1}`$ is the convex hull of the $`n!`$ points $`M(\sigma )`$. Observe that the sum of the $`n`$ coordinates of $`M(\sigma )`$ is $`S(n)`$, hence all the points $`M(\sigma )`$ lie in the affine hyperplane $`H`$.

Under interpreting a permutation as a planar binary tree with levels (cf. for instance \[LR\]), and then forgetting the levels, one gets a well-defined map

$$\psi :S_nY_n.$$

For instance $`\psi (\mathrm{1\; 2\; 3})=\text{ }\text{Γ}\text{Γ}\text{ }\text{ },\psi (\mathrm{1\; 3\; 2})=\psi (\mathrm{2\; 3\; 1})=\text{ }\text{Γ}\text{Γ}\text{ }\text{ }`$.

1.2 Proposition. The Stasheff polytope $`𝒦^{n1}`$ as defined above contains the permutohedron $`𝒫^{n1}`$ and, for $`\sigma S_n`$ and $`tY_n`$, the following are equivalent:

(a) $`M(\sigma )=M(t)`$,

(b) $`\psi {}_{}{}^{1}(t)=\{\sigma \}`$,

(c) $`\psi (\sigma )=t`$ and for all $`i`$ either $`a_i=1`$ or $`b_i=1`$,

(d) $`\psi (\sigma )=t`$ and the permutation $`\sigma `$ has the following property: either $`\sigma (1)=n`$ or $`\sigma (n)=n`$ and the remaining permutation $`\sigma ^{}S_{n1}`$, obtained by deleting $`n`$, satisfies the same property (ad libitum).

The proof will be given in the next section. Observe that, as a consequence, there are $`2^{n1}`$ points which are both vertices of $`𝒦^{n1}`$ and of $`𝒫^{n1}`$.

Example. For $`n=3`$, the common vertices are the points corresponding to the permutations $`(\mathrm{1\; 2\; 3}),(\mathrm{2\; 1\; 3}),(\mathrm{3\; 1\; 2}),(\mathrm{3\; 2\; 1})`$. For $`n=4`$ we get $`(\mathrm{1\; 2\; 3\; 4}),(\mathrm{2\; 1\; 3\; 4}),(\mathrm{3\; 1\; 2\; 4}),(\mathrm{3\; 2\; 1\; 4}),(\mathrm{4\; 1\; 2\; 3}),(\mathrm{4\; 2\; 1\; 3}),(\mathrm{4\; 3\; 1\; 2}),(\mathrm{4\; 3\; 2\; 1})`$.

2. Equation for the facets of the permutohedron and of the Stasheff polytope

The permutohedron can be obtained by truncating the standard simplex along some hyperplanes, one per each cell of $`\mathrm{\Delta }^{n1}`$ (except the big cell). Truncating only along “admissible” ones gives the Stasheff polytope (cf. \[St2\]). We give the explicit equations of these hyperplanes. As a consequence we get the results announced in the first section.

2.1 Shuffles and hyperplanes. The intersection of the hyperplane $`H`$ with the quadrant $`\{(x_1,\mathrm{},x_n)x_i0\text{ for all }i\}`$ is (homothetic to) the standard simplex $`\mathrm{\Delta }^{n1}`$. We still call this intersection the standard simplex.

The $`(k1)`$-cells of $`\mathrm{\Delta }^{n1}`$, for $`k=1,\mathrm{}n1`$, are indexed by the $`(k,nk)`$-shuffles of $`(1,\mathrm{},n)`$, i.e. the partitions $`\omega =(\omega _1\mathrm{}\omega _k|\omega _{k+1}\mathrm{}\omega _n)`$ of $`\{1,\mathrm{},n\}`$ into 2 nonempty subsets. Two partitions $`\omega `$ and $`\omega ^{}`$ are the same if they differ only by the order of the integers in each subset. It is sometimes necessary to take a representative, in which case we will assume that $`\omega _1<\mathrm{}<\omega _k`$ and $`\omega _{k+1}<\mathrm{}<\omega _n`$. We denote by $`\overline{\omega }`$ the dual cell, i.e $`\overline{\omega }=(\omega _{k+1}\mathrm{}\omega _n|\omega _1\mathrm{}\omega _k)`$.

We associate to the shuffle $`\omega =(\omega _1\mathrm{}\omega _k|\omega _{k+1}\mathrm{}\omega _n)`$ the polynomial

$$\begin{array}{c}\text{ }p_\omega (x_1,\mathrm{},x_n):=\text{ }\hfill \\ \text{ }(nk)(x_{\omega _1}+\mathrm{}+x_{\omega _k})k(x_{\omega _{k+1}}+\mathrm{}+x_{\omega _n})+\frac{1}{2}nk(nk),\text{ }\hfill \end{array}$$

and the hyperplane $`_\omega `$ defined by $`p_\omega (x_1,\mathrm{},x_n)=0`$. Observe that $`_\omega `$ and $`_{\overline{\omega }}`$ are parallel.

2.2 Recall on the permutohedron. For any $`\sigma S_n`$ the point $`M(\sigma )`$ lies in the affine hyperplane $`H`$. The $`k`$-cells of the permutohedron $`𝒫^{n1}`$ can be indexed by the partitions of $`\{1,\mathrm{},n\}`$ into $`nk`$ subsets. In particular the facet indexed by the shuffle $`\omega `$ lies in the hyperplane $`_\omega `$. The $`0`$-cells, that is the vertices $`M(\sigma )`$, are indexed by the partitions $`\omega (\sigma )`$ with $`n`$ subsets. The relationship with the permutations is given by

$$\omega (\sigma )=\sigma {}_{}{}^{1}.$$

The vertex $`M(\sigma )=(x_1,\mathrm{},x_n)`$ lies in the hyperplane $`_\omega `$ if and only if the partition $`\omega (\sigma )`$ is a refinement of $`\omega `$. Indeed, if it is so, then $`\{x_{\omega _1},\mathrm{},x_{\omega _k}\}=\{1,\mathrm{},k\}`$ and $`x_{\omega _1}+\mathrm{}+x_{\omega _k}=S(k)`$. It also implies $`x_{\omega _{k+1}}+\mathrm{}+x_{\omega _n}=S(n)S(k)`$ and therefore $`p_\omega (M)=0`$. Observe that if $`\omega (\sigma )`$ is not a refinement of $`\omega `$, then $`p_\omega (M)>0`$.

In conclusion, the permutohedron $`𝒫^{n1}`$ is the truncation of the standard simplex lying in $`H`$ by the hyperplanes $`_\omega `$ for all shuffles $`\omega `$.

Example: $`n=3`$.

ΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJ$`𝒫^2`$012$`_{0,12}`$$`_{12,0}`$$`_{2,01}`$$`_{01,2}`$$`_{1,02}`$$`_{02,1}`$$`123`$$`213`$$`312`$$`321`$$`132`$$`231`$
$$\begin{array}{c}\text{ }M(1|2|3)=(1,2,3),M(2|1|3)=(2,1,3),M(2|3|1)=(3,1,2),\text{ }\hfill \\ \text{ }M(3|2|1)=(3,2,1),M(3|1|2)=(2,3,1),M(1|3|2)=(1,3,2).\text{ }\hfill \end{array}$$

2.3 Planar trees and admissible shuffles. We denote by $`T_n`$ the set of planar trees with $`n+1`$ leaves, $`n0`$ (and one root) such that the valence of each internal vertex is at least 2. Here are the first of them:

$$T_0=\{|\},T_1=\{\text{ }\text{Γ}\text{Γ}\},T_2=\{\text{ }\text{Γ}\text{Γ}\text{ },\text{ }\text{Γ}\text{Γ}\text{ };\text{ }\text{Γ}\text{Γ}\}$$

$$T_3=\{\text{ }\text{Γ}\text{Γ}\text{ }\text{ },\text{ }\text{Γ}\text{Γ}\text{ }\text{ },\text{ }\text{Γ}\text{Γ}\text{ }\text{ },\text{ }\text{Γ}\text{Γ}\text{ }\text{ },\text{ }\text{Γ}\text{Γ}\text{ }\text{ };\text{ }\text{Γ}\text{Γ}\text{ },\text{ }\text{Γ}\text{Γ}\text{ }\text{ },\text{ }\text{Γ}\text{Γ}\text{ },\text{ }\text{Γ}\text{Γ}\text{ },\text{ }\text{Γ}\text{Γ}\text{ };\text{ }\text{Γ}\text{Γ}\text{ }\text{ }\}.$$

The integer $`n`$ is called the degree of $`tT_n`$. The set $`T_n`$ is the disjoint union of the sets $`T_{n,k}`$ made of the planar trees which have $`nk+1`$ internal vertices. For instance $`T_{n,1}=Y_n`$ since it is made of the planar binary trees. On the other extreme the set $`T_{n,n}`$ has only one element, which is the planar tree with one vertex. It is sometimes called a corolla. So we have

$$T_n=T_{n,1}\mathrm{}T_{n,n}.$$

A tree $`t`$ is called a refinement of the tree $`t^{}`$ if $`t^{}`$ can be obtained from $`t`$ by contracting to a point some of the internal edges. So any tree is a refinement of the corolla. Any tree in $`T_{n,n1}`$ is of the form

$$y(r,k)=\text{b}\text{b}\text{b}\text{b}\text{b}\text{b}\text{b}\text{b}\text{b}\text{b}\text{b}\text{b}\text{b}\text{b}\text{b}\text{b}\text{b}\text{b}\text{b}\text{b}\text{ }\text{b}\text{A}\text{A}\text{A}\text{A}\text{A}\text{}\text{}\text{}\text{}\text{}\text{}\text{}\text{}\text{}\text{}\text{}\text{}\text{}\text{}\text{}\text{}\text{}\text{}\text{}\text{}\text{}\text{}\text{}\text{Δ}\text{Δ}\text{Δ}\text{Δ}\text{Δ}\text{Γ}\text{Γ}\text{Γ}\text{Γ}\text{@}\text{@}\text{@}\text{ }\text{@}\mathrm{}\mathrm{}\mathrm{}\text{0}r1rr+kr+k+1n$$

Observe that, once $`n`$ is fixed, it is completely determined by $`r`$ and $`k`$, whence the notation $`y(r,k)`$. We associate to it the shuffle $`\omega (y(r,k))=(r+1r+2\mathrm{}r+k|\mathrm{})`$.

A shuffle $`\omega =(\omega _1\mathrm{}\omega _k|\omega _{k+1}\mathrm{}\omega _n)`$ such that $`\omega _1<\mathrm{}<\omega _k`$ and $`\omega _{k+1}<\mathrm{}<\omega _n`$ is called admissible if the first part is a sequence of consecutive integers, i.e. if $`\omega `$ is of the form $`(r+1r+2\mathrm{}r+k|\mathrm{})`$. Observe that there is a bijection between the admissible shuffles and the planar tree with 2 internal vertices. We denote by $`\omega (t)`$ the partition associated to $`t`$.

2.4 Recall on the Stasheff polytope. It is shown in \[St2, Appendix\] that the Stasheff polytope can be obtained from the standard simplex by truncating along the hyperplanes corresponding to the admissible shuffles. We will show that the points $`M(t)`$ defined in section 1 are indeed the vertices of the polytope in $`H`$ defined by the equations $`p_\omega (M)0`$ for $`\omega `$ an admissible shuffle.

2.5 Lemma. For any tree $`tY_n`$ the coordinates of the point $`M(t)=(x_1,\mathrm{},x_n)𝐑^n`$ satisfy the relation $`_{i=1}^{i=n}x_i=\frac{1}{2}n(n+1)`$. Hence one has $`M(t)H`$.

Proof. Any planar binary tree $`t`$ in $`Y_n,n1,`$ is the grafting of its left part $`t^l`$ and its right part $`t^r`$ (cf. \[LR\]), so $`t=t^lt^r`$. For instance $`\text{ }\text{Γ}\text{Γ}=||`$ . It follows from the definition of $`M(t)`$ that

$$M(t)=(M(t^l),pq,M(t^r))$$

where $`p`$ is the number of leaves of $`t^l`$ and $`q`$ is the number of leaves of $`t^r`$ (we initialize with $`M(|)=\mathrm{}`$). For $`M=(x_1,\mathrm{},x_n)𝐑^n`$, let $`\varphi (M):=x_1+\mathrm{}+x_n`$. We have $`\varphi (M(\text{ }\text{Γ}\text{Γ}))=1`$ since $`M(\text{ }\text{Γ}\text{Γ})=(1)`$. Suppose, by induction, that, $`\varphi (M(t))=\frac{1}{2}k(k+1)`$ for any $`tY_k`$, $`k<n`$. Then, for $`tY_n`$, we get $`\varphi (M(t))=\varphi (M(t^l))+pq+\varphi (M(t^r))`$. By induction $`\varphi (M(t^l))=\frac{1}{2}(p1)p`$ and $`\varphi (M(t^r))=\frac{1}{2}(q1)q`$. Hence we get

$$\begin{array}{cc}\hfill \varphi (M(t))& =\frac{1}{2}(p1)p+pq+\frac{1}{2}(q1)q\hfill \\ & =\frac{1}{2}(p^2+2pq+q^2pq)\hfill \\ & =\frac{1}{2}(n+1)n\hfill \end{array}$$

since $`n+1=p+q`$. Hence we have proved that $`M(t)`$ belongs to the affine hyperplane $`H`$ of $`𝐑^n`$.

2.6 Proposition. Let $`\omega `$ be an admissible shuffle. For any tree $`tY_n`$ the point $`M(t)`$ lies in $`_\omega `$ if and only if the partition $`\omega (t)`$ is a refinement of $`\omega `$. If not, then $`p_\omega (M(t))>0`$.

Proof. Let $`y(r,k)`$ be the tree corresponding to $`\omega `$. When $`\omega (t)`$ is a refinement of $`\omega `$, $`t`$ is a planar binary tree such that by contracting some internal edges we can obtain the tree $`y(r,k)`$ with one internal edge. Let $`(x_1,\mathrm{},x_n)`$ be the coordinates of $`M(t)`$. From the structure of $`t`$ it follows that the subtree which contains the leaves number $`r`$ to $`r+k`$ is a tree of degree $`k`$ (its root becomes the only internal edge of $`y(r,k)`$). Hence we get $`x_{r+1}+x_{r+2}+\mathrm{}+x_{r+k}=S(k)`$. Since $`_{i=1}^{i=n}x_i=S(n)`$, we get $`_{i=1}^{i=r}x_i+_{i=r+k+1}^{i=n}x_i=S(n)S(k)`$.

We already know that $`M(t)H`$ by Lemma 2.5. The conclusion $`M(t)H_\omega `$ follows from the following computation:

$$\begin{array}{cc}\hfill p_\omega (M)& =(nk)S(k)k(S(n)S(k))+\frac{1}{2}nk(nk)\hfill \\ & =nS(k)kS(n)+\frac{1}{2}nk(nk)\hfill \\ & =\frac{1}{2}nk(k+1n1+nk)\hfill \\ & =0.\hfill \end{array}$$

If $`\omega (t)`$ is not a refinement of $`\omega `$, then one of the values of $`x_{r+1}+x_{r+2}+\mathrm{}+x_{r+k}`$ is at least $`1\times (k+1)=k+1`$ and the sum of the others is at least $`S(k1)`$. Hence $`_{i=r+1}^{i=r+k}x_iS(k1)+k+1>S(k)`$. Since $`_{i=1}^{i=n}x_i=S(n)`$, we get $`p_\omega (M(t))>0`$.

Proof of Theorem 1.1. Since the Stasheff polytope is the truncation of the standard simplex by the hyperplanes corresponding to the admissible shuffles, the vertex corresponding to the tree $`t`$ is the intersection of the hyperplanes $`H,_{\omega _1},\mathrm{},_{\omega _{n1}}`$, where $`\omega _1,\mathrm{},\omega _{n1}`$ are the admissible shuffles corresponding to the trees with 2 vertices which admit $`t`$ as a refinement. In order to show that the convex hull of the points $`M(t)`$ is a realization of the Stasheff polytope, it is sufficient to show that

$$H_{\omega _1}\mathrm{}_{\omega _{n1}}=\{M(t)\}.$$

Since we know that this intersection is a point, it is sufficient to prove that $`M(t)`$ lies in each hyperplane. For $`H`$ this is Lemma 2.5. For $`_{\omega _i}`$ this is Proposition 2.6 and we are done.

Example: $`n=3`$.

ΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩΩJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJ$`𝒦^2`$012$`_{0,12}`$$`_{12,0}`$$`_{2,01}`$$`_{01,2}`$$`_{1,02}`$$`123`$$`213`$$`312`$$`321`$$`141`$
$$\begin{array}{c}\text{ }M(\text{ }\text{Γ}\text{Γ}\text{ }\text{ })=(1,2,3),M(\text{ }\text{Γ}\text{Γ}\text{ }\text{ })=(2,1,3),M(\text{ }\text{Γ}\text{Γ}\text{ }\text{ })=(3,1,2),\text{ }\hfill \\ \text{ }M(\text{ }\text{Γ}\text{Γ}\text{ }\text{ })=(3,2,1),M(\text{ }\text{Γ}\text{Γ}\text{ }\text{ })=(1,4,1).\text{ }\hfill \end{array}$$

Proof of Proposition 1.2. Recall that the surjective map $`\psi :S_nY_n`$ is defined by using the interpretation of the permutations as planar binary trees with levels, cf. \[L-R\]. In a tree with levels each internal vertex has a level (ranging from 1 to $`n`$), and there is only one vertex per level. The permutation is obtained by taking $`\sigma (i)=`$ the level of the $`i`$th vertex. For instance

@@@ΓΓΓΓ ΓΓ… 1… 2… 3 @@@ΓΓΓΓ@ @ … 1… 2… 3
(a) $``$ (b) Since all the points $`M(\sigma )`$ are distinct, the equality $`M(\sigma )=M(t)`$ implies that, for a fixed $`t`$, there is only one $`\sigma `$ such that $`\psi (\sigma )=t`$.

(b) $``$ (c) The equality $`\psi (\sigma )=t`$ is clear from the assumption. If some internal vertex of $`t`$ has several leaves on both sides, then there are several ways of lifting it as a leveled tree.

(c) $``$ (d) The root vertex has either $`a_i=1`$ or $`b_i=1`$. In the first case, it means that $`i=1`$ and the permutation is of the form $`(n\mathrm{})`$. In the second case it means that $`i=n`$ and the permutation is of the form $`(\mathrm{}n)`$. And so on.

(d) $``$ (a) Let $`\sigma `$ be a permutation as described in condition (d). Then the $`i`$th vertex of the associated tree has one leaf on one side and has $`\sigma (i)`$ ($`=`$ the degree of the subtree it generates) leaves on the other side. Hence the weight of the $`i`$th vertex is $`1\times \sigma (i)=\sigma (i)`$. It follows that $`M(\sigma )=M(t)`$.

2.7 The cube. There is a family of cubes $`𝒞^n`$ which fits nicely with the families of Stasheff polytopes and permutohedrons. It is defined as follows.

The convex polytope $`𝒞^{n1}`$ is defined in $`H`$ by the equations $`p_\omega (M)0`$ for $`\omega =(\mathrm{1\; 2}\mathrm{}i|i+1\mathrm{}n)`$ and $`\omega =(i+1\mathrm{}n|\mathrm{1\; 2}\mathrm{}i)`$, $`i`$ ranging from 0 to $`n1`$. So the facets of $`𝒞^{n1}`$ are in the hyperplanes

$$_{1,2\mathrm{}n},_{12,3\mathrm{}n},\mathrm{},_{1\mathrm{}n1,n},$$

and

$$_{2\mathrm{}n,1},_{3\mathrm{}n,12},\mathrm{},_{n,1\mathrm{}n1}.$$

Let us introduce the set $`Q_n:=\{0,1\}^{n1}`$ and the map $`\varphi :Y_nQ_n`$ given by $`\varphi (t)=(ϵ_1,\mathrm{},ϵ_{n1})`$ where $`ϵ_i=0`$ (resp. $`ϵ_i=1`$) if the $`i`$th leaf of $`t`$ is pointing to the left (resp. to the right) (cf. \[LR\]). We code the vertices of the cube by the elements of $`Q_n`$. With the definition given above for $`𝒞^{n1}`$, the coordinates of the vertex $`M(ϵ)=(x_1,\mathrm{},x_n)`$ for $`ϵ=(ϵ_1,\mathrm{},ϵ_{n1})Q_n`$ are

$$x_i=iϵ_{i1}(ni+1)(i1)+ϵ_i(ni)(i),\text{for }i=1,\mathrm{},n.$$

Example: $`n=3`$.

ΩΩΩΩΩΩΩΩΩΩΩJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJ$`𝒞^2`$012$`_{0,12}`$$`_{12,0}`$$`_{2,01}`$$`_{01,2}`$$`123`$$`303`$$`321`$$`141`$
One can check that $`𝒞^{n1}`$ contains the Stasheff polytope $`𝒦^{n1}`$ and hence the permutohedron $`𝒫^{n1}`$. The only common vertices of $`𝒞^{n1}`$ and $`𝒫^{n1}`$ are the two points $`(1,2,\mathrm{},n)`$ and $`(n,n1,\mathrm{},1)`$. The polytopes $`𝒞^n`$ and $`𝒦^n`$ have $`n`$ vertices in common. They are characterized by the following equivalent conditions, where $`tY_n`$ and $`ϵQ_n`$ :

(a) $`M(t)=M(ϵ)`$,

(b) $`\varphi {}_{}{}^{1}(ϵ)=\{t\}`$,

(c) $`\varphi (t)=ϵ`$ and $`ϵ`$ is of the form $`(1,\mathrm{},1,0,\mathrm{},0)`$,

(d) $`\varphi (t)=ϵ`$ and $`t`$ is of the form:

@@@@@@ @ΓΓΓΓΓΓΓΓ  ΓΓΓΓ@@@ @$`\mathrm{}`$$`\mathrm{}`$
We remark that these common vertices are on the shortest path (for the Tamari order, see below) in $`𝒦^n`$ from the minimal vertex $`(1,2,\mathrm{},n)`$ to the maximal vertex $`(n,n1,\mathrm{},1)`$.

2.8 Relationship with the poset structure. The three sets $`S_n`$, $`Y_n`$ and $`Q_n`$ can be equipped with a poset structure such that the maps $`\psi `$ and $`\varphi `$ are maps of posets, cf. \[LR\]. On $`S_n`$ it is called the weak Bruhat order, on $`Y_n`$ it is called the Tamari order, and on $`Q_n`$ it is the lexicographic order. These orders are induced by the following covering relations.

Let $`s_i`$ be the permutation which exchanges $`i`$ and $`i+1`$. Then $`\{s_1,\mathrm{},s_{n1}\}`$ is a set of generators of $`S_n`$. For two permutations $`\sigma `$ and $`\sigma ^{}`$, $`\sigma <\sigma ^{}`$ is said to be a covering relation for the weak Bruhat order if $`\sigma ^{}=s_i\sigma `$ for some $`i`$ and the length of $`\sigma ^{}`$ is greater than the length of $`\sigma `$ (recall that the length of $`\sigma `$ is the minimal number of generators necessary to write $`\sigma `$ in terms of the $`s_i`$’s). So, for $`S_3`$ the poset structure is:

$$\begin{array}{ccccc}& & 1& & \\ & & & & \\ & & & & \\ s_1& & & & s_2\\ & & & & \\ & & & & \\ & & & & \\ s_2s_1& & & & s_1s_2\\ & & & & \\ & & & & \\ & & s_1s_2s_1=s_2s_1s_2& & \end{array}$$

For two planar binary trees $`t`$ and $`t^{}`$, $`t<t^{}`$ is said to be a covering relation for the Tamari order if $`t^{}`$ can be obtained from $`t`$ by changing locally the pattern  ΓΓ  to the pattern  ΓΓ . So for $`Y_3`$ the poset structure is:

$$\begin{array}{ccccc}& & \text{ }\text{Γ}\text{Γ}\text{ }\text{ }& & \\ & & & & \\ \text{ }\text{Γ}\text{Γ}\text{ }\text{ }& & & & \\ & & & & \\ & & & & \text{ }\text{Γ}\text{Γ}\text{ }\text{ }\\ & & & & \\ \text{ }\text{Γ}\text{Γ}\text{ }\text{ }& & & & \\ & & & & \\ & & \text{ }\text{Γ}\text{Γ}\text{ }\text{ }& & \end{array}$$

For $`Q_n`$ the lexicographic order is induced by the following covering relation: $`ϵ<ϵ^{}`$ if and only if the values of $`ϵ`$ and $`ϵ^{}`$ are the same except at one place, let say the $`i`$th one, for which $`ϵ_i=0`$ and $`ϵ_i^{}=1`$. So for $`Q_3`$ the poset structure is:

$$\begin{array}{cccc}& & (0,0)& \\ & & & \\ & & & & \\ (1,0)& & & & (0,1)\\ & & & & \\ & & & \\ & & (1,1)& \end{array}$$

2.9 Proposition. The realization of the polytopes $`𝒫^{n1}`$, $`𝒦^{n1}`$ and $`𝒞^{n1}`$ described above are such that all the edges are precisely the covering relations of the posets.

The projection $`\pi `$ of the vertices on the oriented axis $`NS`$ where $`N=(1,2,\mathrm{},n)`$ and $`S=(n,n1,\mathrm{},1)`$ respects the order.

2.10 Length of the edges. It is immediate to verify that the length of the edges in the permutohedron case is $`\sqrt{2}`$ and in the case of the cube $`(ni)i\sqrt{2}`$ for $`i=1,\mathrm{}n1`$. In the case of the Stasheff polytope it is also an integral multiple of $`\sqrt{2}`$. Indeed if the covering relation from $`t`$ to $`t^{}`$ moves the $`i`$th vertex of $`t`$ to the $`j`$th vertex of $`t^{}`$, then the corresponding edge is of length $`a_ib_j\sqrt{2}`$. So the maximum length of an edge in $`𝒦^n`$ is $`m(m+1)\sqrt{2}`$ if $`n=2m`$ and $`m^2\sqrt{2}`$ if $`n=2m1`$.

2.11 Barycenter. F. Chapoton observed that the barycenter $`B`$ of the vertices of $`𝒦^{n1}`$ is $`(\frac{n+1}{2},\mathrm{},\frac{n+1}{2})`$. So the permutohedron, the Stasheff polytope and the “cube” have the same barycenter. As a consequence, for any vertex $`M`$ of the Stasheff polytope one has

$$\stackrel{}{BM}=\underset{i}{}\stackrel{}{BP_i}$$

where the points $`P_i`$ are the vertices of the permutohedron corresponding to the permutations whose image by $`\psi `$ is the tree corresponding to $`M`$ (cf. Proposition 1.2).

Similarly, if $`N`$ is a vertex of the “cube”, then

$$\stackrel{}{BN}=\underset{j}{}\stackrel{}{BM_j}$$

where the points $`M_j`$ are the vertices of the Stasheff polytope related to $`N`$ by $`\varphi `$ (cf. 2.7).

A projection of the Stasheff polytope $`𝒦^3`$ with the coordinates of its vertices in $`𝐑^4`$.

References

\[CFZ\] Chapoton, F.; Fomin, S.; Zelevinsky, A. Polytopal realizations of generalized associahedra. Bulletin Canadien de Mathématiques (to appear) \[ArXiv: math.CO/0202004\]

\[D\] Devadoss, S. L. Tessellations of moduli spaces and the mosaic operad. Homotopy invariant algebraic structures (Baltimore, MD, 1998), 91–114, Contemp. Math., 239, Amer. Math. Soc., Providence, RI, 1999.

\[GKZ\] Gelfand, I. M.; Kapranov, M. M.; Zelevinsky, A. V. Discriminants, resultants, and multidimensional determinants. Mathematics: Theory and Applications. Birkhäuser Boston, Inc., Boston, MA, 1994. x+523 pp.

\[Lee\] Lee, C. W. The associahedron and triangulations of the $`n`$-gon. European J. Combin. 10 (1989), no. 6, 551–560.

\[LR\] Loday, J.-L., and Ronco M., Order structure on the algebra of permutations and of planar binary trees, J. Algebraic Combinatorics, 15(3) (2002), 253–270.

\[St1\] Stasheff, J. D. Homotopy associativity of $`H`$-spaces. I, II. Trans. Amer. Math. Soc. 108 (1963), 275-292; ibid. 293–312.

\[St2\] Stasheff, J. D. From operads to “physically” inspired theories. Operads: Proceedings of Renaissance Conferences (Hartford, CT/Luminy, 1995), 53–81, Contemp. Math., 202, Amer. Math. Soc., Providence, RI, 1997.

\[T\] Tonks, A. Relating the associahedron and the permutohedron. Operads: Proceedings of Renaissance Conferences (Hartford, CT/Luminy, 1995), 33–36, Contemp. Math., 202, Amer. Math. Soc., Providence, RI, 1997.

Institut de Recherche Mathématique Avancée,

CNRS et Université Louis Pasteur

7 rue R. Descartes,

67084 Strasbourg Cedex, France

Courriel : loday@math.u-strasbg.fr

9 December 2002