Damien Pitman
email: damien.pitman@cortland.edu

Random 2-SAT Solution Components and a Fitness Landscape

Keywords: 2-SAT, random graphs, components, clusters, fitness landscape, incompatibilitiies

We describe a limiting distribution for the number of connected components in the subgraph of the discrete cube induced by the satisfying assignments to a random 2-SAT formula. We show that, for the probability range where formulas are likely to be satisfied, the random number of components converges weakly (in the number of variables) to a distribution determined by a Poisson random variable. The number of satisfying assignments or solutions is known to grow exponentially in the number of variables. Thus, our result implies that exponentially many solutions are organized into a stochastically bounded number of components. We also describe an application to biological evolution; in particular, to a type of fitness landscape where satisfying assignments represent viable genotypes and connectivity of genotypes is limited by single site mutations. The biological result is that, with probability approaching 1, each viable genotype is connected by single site mutations to an exponential number of other viable genotypes while the number of viable clusters is finite.

Introduction

We are interested in the connective properties of a random subgraph of the discrete cube Q n . This random subgraph Q F is induced on those vertices that correspond to literal assignments that satisfy a 2-CNF formula F = F p that is randomly determined by letting each clause be included in F with probability p. Let N n be the number of connected components in Q F .

Theorem 1 Let F , Q F and N n be randomly determined as above. If p = c/2n and c < 1 is constant, then N n converges weakly to N = 2 Ψ where Ψ is a Poisson random variable with mean

λ = - 1 2 (ln (1 -c) + c) .
In particular, the probability that there is a unique cluster converges to e -λ = (1 -c)e c .

Our interest in the component structure is motived by the theory of fitness landscapes. The notion of fitness landscapes was introduced by a theoretical evolutionary biologist, Sewall Wright in [START_REF] Wright | The roles of mutation, inbreeding, crossbreeding and selection in evolution[END_REF] (see also [START_REF] Kauffman | The origins of order[END_REF][START_REF] Gavrilets | Fitness Landscapes and the Origin of Species[END_REF]). The study of fitness landscapes has proved extremely useful both in biology and well outside of it. In the standard interpretation, a fitness landscape is a relationship between a set of genes (or a set of quantitative characters) and a measure of fitness (e.g. viability, fertility, or mating success). In Wright's original formulation the set of genes (or quantitative characters) is the property of an individual. However, the notion of fitness landscapes can be generalized to the level of a mating pair, or even a population of individuals [START_REF] Gavrilets | Fitness Landscapes and the Origin of Species[END_REF]. For further information one can look at the book Fitness Landscapes and the Origin of Species [START_REF] Gavrilets | Fitness Landscapes and the Origin of Species[END_REF] or the paper [START_REF] Gravner | Percolation on fitness landscapes: Effects of correlation, phenotype, and incompatibilities[END_REF], which is a sort of biological sister to our discussion here.

It turns out that k-SAT is also of interest to physicists working in statistical mechanics and it is somewhat surprising that the component structure for random 2-SAT has not been examined previously because the component structure for 3-SAT has been explored. Replica symmetry breaking is a method from statistical mechanics that is not strictly rigorous, but has been used to find two phase transitions in 3-SAT [START_REF] Biroli | A variational description of the ground state structure in random satisfiability problems[END_REF]. In one phase, all satisfying assignments form a single component in the n-cube. In the next, the number of components is exponential in n. In the final phase, there are no satisfying assignments. Since our result shows that the number of components is stochastically bounded for 2-SAT, it seems that the structures are quite different for 2-SAT and 3-SAT.

We organize the remainder as follows. In Section 2 we introduce notation and provide the necessary background and results in both 2-SAT and fitness landscapes. We also describe the connection between the two topics. Section 3 pertains to the number of clusters and contains the proof of our result.

Background

Fitness Landscapes

The particular model of fitness landscapes that we consider here begins with an idealized collection of all genotypes that are haploid and diallelic at n loci. A haploid organism is one for which there is only one copy of each chromosome. Alleles are the potential versions of a gene at a specified locus. In our model, for any specified n loci, there exists a list L of all the unordered pairs of strictly distinct alleles that are incompatible. Each genotype for these n loci is viable if none of its allele pairs is incompatible and inviable otherwise. Each list L is an instance of a fitness landscape on the given genotype space.

We are primarily interested in two questions relating to a given list L: how many viable genotypes are there and how well connected are they through single locus mutations? With regards to connectivity, we say that two genotypes are in the same cluster if and only if they are connected by a path of single locus mutations through viable genotypes. Thus, each cluster of viable genotypes corresponds to a collection of genotypes which can each evolve into any other genotype in the cluster without passing through an inviable genotype and without altering two or more alleles simultaneously. Since there are n loci and two alleles at each locus, our genotype space is in bijection with the set of binary strings of length n or the vertices of the discrete cube Q n . In addition, since the only allowed mutations are single locus mutations (which are equivalent to bit flips) we can represent these mutations by edges in Q n . The viable genotypes and mutations between them form an induced subgraph of Q n and the clusters are the connected components.

2-SAT

We begin with n Boolean variables ξ 1 , . . . , ξ n . For each 1 ≤ i ≤ n, the two truth values of ξ i are referred to as the positive literal and the negative literal of ξ i . We will be using a non-standard notation to refer to these literals. We let 0 be the negative literal and 1 be the positive literal and then put the index in the subscript, i.e., for 1 ≤ i ≤ n 0 i is the negative literal of ξ i 1 i is the positive literal of ξ i

The negation of any literal x is denoted x. Thus, 0 i = 1 i and 1 i = 0 i . Literals of distinct variables are said to be strictly distinct. An assignment of n strictly distinct literals to n Boolean variables is referred to as a truth assignment to the n variables. A 2-clause c = x ∨ y is the disjunction of two literals x and y. Generally these literals need not be distinct, but here we assume x and y are strictly distinct. Thus, there are

2 2 n 2 = 2n(n -1)
possible 2-clauses. Suppose we have some number m ≥ 0 of 2-clauses c 1 , . . . , c m . Then

F = c 1 ∧ . . . ∧ c m
is a 2-SAT formula. Again, we assume that the clauses are distinct. If there is some literal assignment to the n variables for which the formula F is TRUE, then it is said to be satisfied or SAT. Determining if a formula is satisfiable is known as the 2-SAT problem. The 2-SAT problem is the simplest of the k-SAT problems. For any k ≥ 2, a k-SAT formula is the conjunction of m disjunctions where the number of literals per disjunction is k. The k-SAT problem, like the 2-SAT problem, is to determine whether or not a given formula is satisfiable. Of course, one can consider other types of satisfiability problems as well. Satisfiability problems in general have been important in theoretical computer science since 1971, when Cook established that they are NP-complete [START_REF] Cook | The complexity of theorem-proving procedures[END_REF]. The most studied type of satisfaction problem is k-SAT because most other models were proven to generate easy-to-satisy formulas. The 2-SAT problem, unlike k-SAT problems for k > 2, is not NP-complete. In fact, solutions can be found in linear time [START_REF] Aspvall | A linear-time algorithm for testing the truth of certain quantified Boolean formulas[END_REF].

2-SAT as a Fitness Landscape

Let each Boolean variable ξ i be associated with a genetic locus i and let the literals 0 i and 1 i represent the two alleles at that locus. Also, let us write that xy is an incompatibility if the alleles x and y are incompatible. Then, notice that if a formula F contains the clause x ∨ y then no satisfying assignment to n variables contains both x and y. Mapping each clause x ∨ y to the corresponding incompatibility xy leads to a bijection between the set of 2-SAT formulas and the set of lists of incompatibilities. It follows that if L is a list of incompatibilities and F is the 2-SAT formula with the corresponding clauses, then a genotype with no allele pairs on L is associated with a literal assignment that satisfies the formula F and vice versa. Consequently, we can let F refer to either the formula or the list of incompatibilities without distinction and we can think of the biological questions in terms of 2-SAT or the other way around.

Random 2-SAT and Results

Determining the probability that a randomly chosen formula F is satisfiable is a random 2-SAT problem. Throughout this paper, F is chosen by letting each possible clause be included independently with probability p = c 2n .

where c > 0. In general, c may depend on n, but all results stated here hold only for constant c. The reason p is written as c/2n is that there is a phase transition from satisfiable to unsatisfiable where the expected number of clauses is asymptotically equivalent to the number of literals 2n.

Theorem 2 Let > 0 be constant and F be a formula chosen randomly as described above. Then the following statements hold with probability approaching 1 as n tends to infinity.

• If c ≥ 1 + then F is not satisfiable. • If c ≤ 1 -then F is satisfiable.
This is the fundamental result for random 2-SAT and was proved independently by three different groups around 1992 [START_REF] Chvátal | Mick gets some (the odds are on his side)[END_REF][START_REF] De | On random 2-SAT[END_REF][START_REF] Goerdt | A threshold for unsatisfiability[END_REF]. The model examined in these papers is actually slightly different, but is asymptotically equivalent to ours in that both exhibit the same phase transition at equivalent critical values. This equivalence and the best current results are described in [START_REF] Bollobás | The scaling window of the 2-SAT transition[END_REF], where > 0 is allowed to vary with n and the size of the finite scaling window is described. We are also interested in the number of satisfying assignments in the SAT phase. The following result is proved in [START_REF] Gravner | Percolation on fitness landscapes: Effects of correlation, phenotype, and incompatibilities[END_REF].

Theorem 3 The number of satisfying assignments to a satisfiable 2-SAT formula is at least exp((e -2c + ce -4c ) log 2 -δ)n) where c < 1 and δ > 0 are constants.

And now for the context of random 2-SAT. Random satisfiability problems became popular as a way to study the hardness of "typical" formulas. A particularly interesting fact about random k-SAT problems is that all random k-SAT problems undergo a phase transition similar to the transition for 2-SAT. More on this can be found in [START_REF] Achlioptas | The threshold for random k-SAT is 2 k log 2 -O(k)[END_REF], which is a nice paper on both the latest research on k-SAT and some general satisfiability context.

Digraphs

The Standard Digraph for 2-SAT

Every 2-SAT formula F can be associated to a directed graph D F as defined by Aspvall et al [START_REF] Aspvall | A linear-time algorithm for testing the truth of certain quantified Boolean formulas[END_REF]. The proofs of Theorem 2 and the remainder of our discussion here are based on this digraph.

• The vertex set of D F is the set of literals {0 1 , . . . , 0 n , 1 1 , . . . , 1 n }.

• For each clause x ∨ y in F the directed edges x → y and y → x are included in D F .

To clarify this definition, consider the clause x ∨ y: a literal assignment including x must include y to be satisfying and an assignment with literal y must have x. Thus, the two edges in the definition correspond to the two implications naturally associated with the clause x ∨ y: x ⇒ y and y ⇒ x.

If there is a directed path from x to y in D F it is denoted by x y. Notice that this path is in D F if and only if the path y

x is also in D F . Also, like the edges of D F , these paths do correspond to logical implications corresponding to the satisfiability of F . The set of literals and edges that can be reached from x is referred to as the out-graph D + F (x) and the literal set of D + F is denoted

L + (x) = L + F (x) = {y : x y}.
These are the literals that must be present in any satisfying assignment with literal x. Of course, an assignment may have all the literals in L + (x) and yet still not be satisfying due to an unrelated clause. On the other hand, those literals that require x to be present in any satisfying assignment are denoted

L -(x) = L - F (x) = {y : y x}.
and the corresponding graph is called the in-graph of x and denoted D -(x).

We say that two vertices x and y in a digraph are weakly connected if there is an undirected path from x to y in the digraph, i.e., x and y are weakly connected in the digraph if they are connected in the undirected (multi)graph that is formed by replacing directed edges with undirected edges. The components of this undirected graph formed from D F are called the weak components of D F . Notice that x and y may be in the same weak component without having a directed path from x to y or from y to x.

Suppose that y ∈ L + F (x) ∩ L - F (x), so x y and y x. In this case x and y are said to be strongly connected. Consider the set of literals

C F (x) = {y : x y x}
that are strongly connected to x. The subgraph of D F induced by these literals is a strongly connected component. We will refer to both the strongly connected component and its set of literals as the strong component of x. We follow the convention that x x for every vertex x ∈ D F so that every vertex is a member of a strong component and C F (x) is well defined for every literal and the set of all 2n literals can be partitioned into strong components of D F . When a strong component consists of a single literal we will say that the strong component is trivial. Otherwise the strong component is considered to be nontrivial. The set of all strong components can be partially ordered. Let

C F (x) ≤ C F (y) if x y,
which also implies that x y for any

x ∈ L - F (x) ⊇ C F (x) and y ∈ L + F (y) ⊇ C F (y).
For any set of literals M , we define

M = {y : y ∈ M }. When M ∩ M = ∅, we say that M and M are complementary. Notice that if y ∈ C F (x), then y ∈ C F (x) so C F (x) = C F (x)
for every literal x. We also see that

C F (x) ∩ C F (x) = ∅ ⇐⇒ C F (x) = C F (x).
If there is a literal x such that C F (x) = C F (x), then there are literals y, z / ∈ {x, x} (not necessarily distinct) such that x y x z x and we say that x (and each y ∈ C F (x)) is on a contradictory cycle in D F . Notice that this cycle need not be simple (have the same number of literals as edges). Since the literal x depends upon its complement x to be satisfying and vice versa, neither literal can be assigned to the corresponding variable and there are no satisfying assignments. On the other hand, it can be shown that if there are no contradictory cycles, then there is at least one satisfying assignment (see [START_REF] Bollobás | The scaling window of the 2-SAT transition[END_REF] for example). This is perhaps the most fundamental result in the study of 2-SAT. Theorem 4 A formula F is satisfiable if and only if there is no contradictory cycle in D F .

The Digraph of the Partial Ordering of Strong Components O F

Since a formula F is satisfiable exactly when there is no literal x such that C F (x) = C F (x), we see that having a satisfiable formula is equivalent to having every strong component of the digraph being a member of a complementary pair {C F (x), C F (x)}. It follows that, given any satisfiable formula F and any strong component C of D F , a necessary (but not sufficient) condition for an assignment to be satisfying is that it must have either have all the literals of C or else all of the literals of C. This means that, while there are 2 |C| potentially satisfying (partial) assignments to the variables of C, we know that there are actually only two possible combinations of the literals on these variables that might correspond to satisfying assignments. To indicate the assignment of all literals in C (or C) we will simply state that we have assigned C (or C). Now suppose that there are s complementary strong component pairs determined by a satisfiable formula F , and {C 1 , C 1 } . . . {C s , C s } is a listing of these. Then every satisfying assignment must satisfy

(C 1 ∨ C 1 ) ∧ . . . ∧ (C s ∨ C s ). (1)
It follows that there are no more than 2 s assignments that satisfy F . In this manner, it makes sense to think of complementary strong components as a tool for reducing the dimension of the solution space.

Continuing in this vein, we find it helpful to consider the directed graph corresponding to the partial order on the strong components of D F , which we will denote by O F . The vertex set of O F is the set of strong components of D F and there are edges X → Y in O F exactly when X and Y are strong components of D F such that there exist literals x in X and y in Y such that x → y is an edge of D F . Thus the edges of O F correspond to implications that are represented in D F . Moreover, the implications corresponding to O F in conjunction with the statement (1) form a statement that is logically equivalent to F . In much of Section 3 we will effectively ignore the internal structure of the strong components that determines (1) and focus our attention on the ordering of the strong components represented in O F .

We will relax our language a bit and write that a collection of strong components C = {C 1 , . . . , C i } is a partial assignment to indicate that all the literals in ∪ i C i have been assigned. Similarly, we will use L + (C) to refer to L + (∪ i C i ), and so on. Given two partial assignments C and D, we notice that C ∪ D is a partial assignment without contradiction if and only if

L + (C) ∪ L + (D) is strictly distinct. A related result is Lemma 5 If X is a collection of strong components such that L + (X ) = X
and Y is any collection of strong components that is strictly distinct from X , then L + (Y) ∩ X = ∅. Thus, under the given premises, X ∪ Y can be assigned without contradiction if and only if L + (Y) is strictly distinct.

Proof: If this were not the case, then there are strong components X ∈ X and Y ∈ Y such that Y ≤ X, which is equivalent to X ≤ Y . Since X = L + (X ) this means that Y ∈ X ; which means that X and Y were not strictly distinct.

2 This result allows us to make the assignment X for any collection of strong components that satisfies X = L + (X ) and then consider partial assignments to the remaining variables without consideration of the variables of X . Clearly, we are interested in the structure of the partial order O F . A chain is a totally ordered subset of a partially ordered set, which means that any two elements in the chain are comparable in order. An antichain is a subset A of a partially ordered set such that any two elements in A are incomparable. A maximal (anti)chain is an (anti)chain that is not a proper subset of any other (anti)chain. A maximum (anti)chain is an (anti)chain that has cardinality at least as large as every other (anti)chain. The height of a partial order is the cardinality of a maximum chain. The width of a partial order is the cardinality of a maximum antichain. We will use the term complementary antichains to refer to a pair {A, A} where A is a strictly distinct collection of strong components where each element in A is incomparable to every other element in A ∪ A. We will refer to the cardinality of a maximum complementary antichain as the complementary width of O F .

Lemma 6 Suppose F is satisfiable. If {A, A} is a pair of complementary antichains in O F where A = {C 1 , . . . , C l }, and X = {X 1 , . . . , X l } is any partial assignment where X i ∈ {C i , C i } for 1 ≤ i ≤ l, then there exists a satisfying assignment containing X .

Proof: Notice that L + (X ) is strictly distinct. Indeed, if not, then there is a component Z such that there exist X i and X j from X such that X i ≤ Z and X j ≤ Z. And so we have Z ≤ X i , which gives us X j ≤ X i . Since this contradicts the complementary nature of A, the outgraph is strictly distinct and we can select all the literals of L + (X ) for a partial assignment A that is without contradictions. Notice that A = L + (A) = L + (X ), so A = L -(A). Thus, once we have selected A, we can not choose a strong component Y from L -(A) (because we have already chosen the complements). This means that the choice between any strong component pair {Y, Y } beyond A can be made independent of A. Thus, we can simply invoke the satisfiability of F to be sure that there exists some satisfying assignment containing A which of course contains X . 2

Corollary 7 Suppose F is satisfiable. If k is the complementary width of O F , then there are at least 2 k assignments that satisfy F .

Proof: Let A be a maximum complementary antichain. We observe that there are 2 k distinct partial assignments X as described in Lemma 6 that correspond to A. Thus, Lemma 6 ensures the existence of 2 k distinct assignments that satisfy F . 2

The Number of Components

The purpose of our discussion here is ultimately to study the number of connected components of Q F . Besides our innate mathematical interest in structure, we are also interested in connected components of Q F for biological reasons. Recall that in our biological model, literals correspond to alleles, so complementary strong components represent alternate strategies for survival. If we anthropomorphize evolution, then we can think of the evolution of an organism as a sequence of choices between these alternate strategies. We imagine the set of satisfying assignments as the collection of all possible viable strategies for survival. We are interested in the topology of Q F as opposed to a more dense graph because allowing for edges only between assignments that differ on a single variable corresponds with allowing evolutionary pathways through single allele mutations only. If one considers our primary result, Theorem 1 in light of Theorem 3, we see that exponentially many solutions are organized into a stochastically bounded number of components. In the biological model, this means that each viable genotype is connected by single site mutations to an exponential number of other viable genotypes; whereas the number of these clusters, which are not connected to each other is very likely to be small. We begin our study in Section 3.1 by considering the structure of Q F for a fixed formula F . We will see that this structure is somewhat difficult to describe when a formula F gives rise to a complicated partial order O F . In Section 3.2 we consider the random picture and prove Theorem 1. The proof of this result is based on the fact that in a random setting where satisfiability is asymptotically almost sure, the partial order O F is asymptotically almost surely an antichain.

The Deterministic Setting

Consider two satisfying assignments U and V in Q F that differ by only one strong component pair {C, C}. We take the perspective that moving from U to V is achieved by changing the literals of C in U to the literals of its complement C in V. We will use the notation V = U C to denote this evolution. In other words, U C = (U -C) ∪ C. In general, two satisfying assignments U and V may differ by several strong component pairs. We will write X = U -V to denote the collection of strong components in U whose complements are in V. We will also write V = U X to indicate that V is the assignment that results from starting with U and changing X to X . Lemma 8 If U and V are any two F satisfying assignments, then there exist satisfying assignments U 0 , U 1 , U 2 , . . . , U l such that U 0 = U, U l = V and U i+1 = U i C i for 0 ≤ i < l where C 1 , . . . , C l is some ordering of the strong components of U -V.

Proof: We begin by making the following definitions:

C = U -V P = the graph of the partial order of C ∪ C B = {C ∈ C | L - P (C) = ∅}.
Notice that B is defined so that for any X ⊆ B, we have L + P (X ) = X . Thus, if Y = U -X , then Lemma 5 applies and U X is satisfying for any X ⊆ B. Thus, given any ordering of the components in C, we can generate a sequence of satisfying assignments from U to U B following this order. To be concrete, let C 1 , C 2 , . . . , C l be the components in B in the order induced by the original order of the literals, i.e., C 1 has the least literal among all literals in B and C 2 has the least literal among all literals in B -C 1 and so on. Then, each of U 0 , U 1 , U 2 , . . . , U m is a satisfying assignment, where

U 0 = U, U m = U B and U i+1 = U i C i for 0 ≤ i < m.
We can complete our proof via induction on the depth of P . Our base case is that P has depth one. In this case, B = C and U m = V, so we are done. If the depth of P is k, then the depth of the partial order on C -B is k -1, so we can apply the inductive hypothesis to U m and V and concatenate the satisfying assignments found there to the satisfying assignments U 0 , U 1 , U 2 , . . . , U m and we have our proof.

2

Corollary 9 Suppose F is a satisfiable 2-formula and that U and V are any two distinct satisfying assignments in Q F . Then U and V are connected in Q F if and only if U -V consists entirely of trivial strong components.

Proof: We use the notation from the proof of Lemma 8. In the case that U -V consists entirely of trivial strong components, the sequence

U 0 , U 1 , U 2 , . . . , U m is a path in Q n . Since Q F is induced from Q n , it follows that this path connects U to V in Q F .
For the converse, suppose that there is a nontrivial strong component C ∈ U -V. Consider the subcubes of Q n formed by fixing the literals corresponding to C and C respectively, but varying over both literals on all other variables. Since the pair is nontrivial, any assignment in one subcube differs from any assignment in the other subcube for at least two variables. Moreover, there are no satisfying assignments outside these subcubes because every satisfying assignment has to have all the literals of C or else all the literals of C. Since U and V are in different subcubes they are not connected in Q F .

2

It is important to realize that Lemma 8 and Corollary 9 apply only under the assumption that U and V are both satisfying assignments. It is certainly possible that U is a satisfying assignment, while the assignment V is unsatisfying even though U and V differ by only one strong component pair. A few example formulas and the corresponding graphs are provided in Figure 1. In the figure, we refer to incompatibilities as opposed to disjunctions, so we remind the reader that an incompatibility xy is equivalent to the disjunction x ∨ y. Incompatibilities are useful when studying the structure of Q F because we simply remove the subcubes of Q n that are specified by the list of incompatibilities.

From Corollary 9 we see that to study the component structure of Q F one must understand the partial order on the nontrivial strong components. In particular, if there are no nontrivial strong components in D F on which two assignments differ, then the components are not in distinct components of Q F . From Corollary 7, we see that we will have satisfying assignments with every combination of strong components from a maximum complementary antichain and its complement. But this tells us nothing about the component structure of Q F . If we want to count the number of components in Q F , then we need to identify satisfying assignments in distinct components of Q F . To accomplish this, we will look at complementary antichains of nontrivial strong components. We will use the term nontrivial complementary width to refer to the greatest cardinality among the complementary antichains consisting entirely of nontrivial strong components of D F . We will use the term nontrivial height to refer to the greatest number of nontrivial strong components within a single chain of D F . The term nontrivial complementary height will mean the greatest number of nontrivial strong components in a maximal chain that is complementary. Notice that we first make a list of all maximal chains and then consider only those that are complementary to find one with a maximum number of nontrivial strong components.

Theorem 10 Suppose that F is a satisfiable formula with nontrivial width j. Also, let k be the number of complementary pairs of nontrivial strong components determined by F and let N be the number of connected components in

Q F . Then 2 j ≤ N ≤ 2 k . Furthermore 1. If the nontrivial height of O F is one, then N = 2 k . 2. If the nontrivial height of O F is greater than one, then 2 j ≤ N < 2 k . 1 1 1 2 1 3 1 4 0 1 0 2 0 3 0 4 F 1 1 1 1 2 1 3 1 4 0 1 0 2 0 3 0 4 F 2 1 1 1 2 1 3 1 4 0 1 0 2 0 3 0 4 F 3
Fig. 1: A sequence of digraphs and the corresponding subgraphs of Q n for n = 4. Dimensions of Q n are ordered left/right, down/up, front/back, in/out. The subcubes of nonsatisfying assignments are shaded. For F1 = {0112, 0213}, DF 1 has no cycles and QF 1 is connected. A complementary pair {{01, 02, 03}, {11, 12, 13}} that is not order related arises in F2 = F1 ∪ 1102 and QF 2 is disconnected. In F3 = F2 ∪ 0102, the complementary pair from F2 becomes order related and we see that one of the two components from QF 2 is lost in QF 3 .

3. If there are complementary weak components containing chains of nontrivial height greater than one, then 2 j < N < 2 k .

Proof: The weak upper bound follows directly from Corollary 9. The weak lower bound follows directly from Corollaries 7 and 9. Result 1 follows from the fact that j = k if there are no order relations between nontrivial strong components. On the other hand, if there are nontrivial strong components C 1 and C 2 such that C 1 < C 2 , then j < k. For the remainder of the proof, we suppose that this is the case. Since C 1 < C 2 there is no satisfying assignment with C 1 and C 2 , so N < 2 k . Thus, the strict upper bound in 2 and 3 holds. Notice that this allows for C 2 = C 1 ; in which case there is no satisfying assignment with C 1 . All that remains is to show that the strict lower bound holds in the case that C 1 and C 2 are strictly distinct and C 1 and C 2 are not related to C 1 or C 2 .

We consider Lemma 5 and use the notation there for X . We notice that L + (C 1 ) is strictly distinct, so if we set X = L + (C 1 ), then we see that there will be a satisfying assignment with C 1 and C 2 . Similarly, if we set X = L + (C 2 ) ∪ L + (C 1 ) we find another satisfying assignment. The same can also be said for X = L + (C 2 ). Thus, we have satisfying assignments with each of C 1 C 2 , C 1 C 2 , and C 1 C 2 , but not with C 1 C 2 . We clearly have that these three possible combinations fall strictly between two and four. We also notice that any satisfying assignment must have one of these three combinations. It follows that 2 j < N < 2 k . 2

The Random Setting

In this subsection, we prove the primary result of this paper, Theorem 1. Throughout, F and consequently D F , are randomly determined as described in Section 1. When a strong component is comprised of exactly i ≥ 2 edges and i literals, we will refer to the strong component as a simple cycle of order i, or more succinctly, as an i-cycle. The proof of Theorem 1 follows easily from Theorem 10 and the following lemmas.

Lemma 11 With probability 1 -O(n -1 ), every nontrivial strong components is a simple cycle.

Lemma 12

With probability 1 -O(n -1 ), the set of all nontrivial strong components is an antichain.

Lemma 13

The distribution on complementary simple cycle pairs converges to a Poisson distribution with parameter λ = -(ln(1 -c) + c)/2.

Proof: (of Theorem 1 under the assumption of Lemmas 11, 12 and 13.) If Lemmas 11 and 12 are true, then it follows from Theorem 10 that we are a.a.s. that the number of components in Q F is 2 Xn where X n is the random number of complementary simple cycle pairs. If Lemma 13 is true then X n converges weakly to a Poisson random variable Ψ with parameter λ = -(ln(1 -c) + c)/2. Together, these imply that the number of connected components in Q F converges weakly to 2 Ψ , and that the probability that there is a unique cluster converges to e

-λ = (1 -c)e c . 2
All that remains is to show that Lemmas 11, 12 and 13 are true. Before beginning these proofs, we will attempt to provide some context for the results in this section. From a combinatorial perspective (or even simply from a descriptive perspective), Theorem 10 is quite unsatisfactory. We would like to know what happens when the nontrivial height of P is not one. A cursory examination of various partial orders on nontrivial strong components of D F leads to the conclusion that categorizing all the possible scenarios would be quite involved and is certainly beyond our scope here. The good news is that Lemmas 11 and 12 show that from a probabilistic perspective, none of these complexities are important because, as the number of variables becomes large, we are asymptotically almost sure that the nontrivial height will be one.

This should come as no surprise to someone well versed in random graph theory because of the similarity between D F and a standard directed random graph on 2n vertices where each edge appears with probability p. One can also relate D F to a standard undirected random graph G p where p = 2p -p 2 as was done in [START_REF] Bollobás | The scaling window of the 2-SAT transition[END_REF]. It is well known [START_REF] Bollobás | Random graphs[END_REF][START_REF] Barbour | Poisson Approximation[END_REF][START_REF] Palasti | On the threshold distribution function of cycles in a directed random graph[END_REF] that for p = O(n -1 ), the number of simple cycle pairs of any fixed length in directed or undirected random graphs converges weakly to a Poisson distribution. What we must show is that the total number of simple cycle pairs of all lengths converges weakly to the Poisson distribution with parameter λ = -(ln(1 -c) + c)/2 when p = c/2n and c < 1. While this result doesn't seem to be published for the 2-SAT digraph, it has been shown [START_REF] Takács | On the limit distribution of the number of cycles in a random graph[END_REF][START_REF] Arratia | Poisson approximation and the chen-stein method[END_REF] that in the standard random graph, G p * where p * = c/n, the total number of simple cycles converges weakly to a Poisson distribution with parameter -1 2 (ln(1 -c) + c + c 2 /2). The proof we provide for D F closely resembles the proof in Section 4.3 of [START_REF] Arratia | Poisson approximation and the chen-stein method[END_REF].

We now establish our notation and make some preliminary observations. Let Γ i,n be the set of (unordered) complementary i-cycle pairs on the 2n literals and define

Γ n = i=2 Γ i,n . Then, for each α ∈ Γ n let I α = 1 if α ∈ D F 0 else and p α = E(I α ).
We remind that reader that for any literals y 1 , y 2 , . . . , y i we can make the following statement about cycles in D F :

y 1 → y 2 → . . . → y i → y 1 ⇐⇒ y 1 ← y 2 ← . . . ← y i ← y 1 .
Since every α ∈ Γ i,n is a complementary pair of directed cycles on strictly distinct literals, p α = p i for all α ∈ Γ i,n . We next define

X i,n = α∈Γi,n I α and µ i,n = E (X i,n ) .
Again, by the complementary nature of D F , we get

µ i,n = α∈Γi,n p α = α∈Γi,n p i = (n) i i 2 i-1 p i = (n) i n i c i 2i .
Notice that for any fixed i, (n

) i /n i = (1 -1/n)(1 -2/n) . . . (1 -(i -1)/n).
Thus, µ i,n monotonically increases with n and converges to c i /2i. Next, we define

X n = n i=2 X i,n and λ n = E (X n ) .
Notice that X n is the random variable that counts the total number of simple cycle pairs in D F . Thus, λ n is the expected total number of simple cycle pairs in D F . If c < 1, then

λ n = n i=2 µ i,n < ∞ i=2 c i 2i = - 1 2 (ln (1 -c) + c) .
This immediately implies that if c < 1 and ω = ω(n) → ∞, then

P n i=ω X i,n > 0 ≤ E n i=ω X i,n -→ n 0. (2)
Thus, the probability that the length of the longest cycle will diverge with n converges to 0. Nevertheless, our proof technique will require that we control cycles of unbounded length. We discuss the reason for this after completing this proof. For now, we define for any

2 ≤ m ≤ n T m,n = m i=2 X i,n and λ m,n = E(T m,n ).
We also introduce the notation Ψ m,n for the Poisson random variable with mean λ m,n . Now that we have established some notation we proceed with the proofs.

Proof: (of Lemma 11.) We observe that any strong component of order i ≥ 3 that is not a simple cycle contains at least a simple cycle α and a path β with first and last literals in α. Suppose α ∈ Γ i,n and β is a path with j > 0 edges and both endpoints in α. Then the expected number of such ordered pairs (α, β) in D F is bounded above by

n i 2 i-1 (i -1)! n -i j -1 2 j-1 (j -1)!i 2 p i+j < i(2n) i+j-1 p i+j = ic i+j 2n .
Since c < 1, the sum over 1 ≤ j ≤ n -i and then over 2 ≤ i ≤ n is O(n -1 ). We have actually counted at least two ordered pairs for each of the potential nonsimple components because exactly one of the paths of α with endpoints in common with β will form a cycle with β, which will be counted as some cycle α with the other path as β . Thus, for any D F , the number of nonsimple strong components is not more than one half of the number of ordered pairs considered here. Thus, the expected number of ordered pairs we have estimated is at least twice the expected number of nonsimple strong components, which is greater than the probability that there exists a nonsimple strong component.

Proof: (of Lemma 12.) Notice that if there are strong components A and C such that A ≤ C, then there are directed cycles α ⊆ A and γ ⊆ C such that α and γ are connected by a directed path β. Similar to the proof of Lemma 12, it is sufficient to show that the expected number of such ordered triples (α, β, γ) is O(n -1 ). To identify (α, β, γ) we select α and mark a literal of α that is common to β; and then select the remaining literals of β in order, the last of which is the first literal of γ; and then select the remaining literals of γ in order. Assuming that α is an i-cycle, β is a path with j > 0 edges, and γ is a k-cycle, we have must choose i+j +k -1 literals in order. Thus, there are no more than (2n) i+j+k-1 < (2n) i+j+k-1 such triples. Notice that there are necessarily i + j + k edges in the subgraph corresponding to (α, β, γ). Thus, c i+j+k-1 p is an upper bound for the expected number of such configurations. Since c < 1 we can sum over i, j, and k to get the desired result.

Proof: (of Lemma 13) We will prove the weak convergence of X n to Ψ by demonstrating that for any subset A of the positive integers we can make |P (X n ∈ A) -P (Ψ ∈ A)| arbitrarily small by taking n to Since this sum is O(n -2 ) for any m ≤ n, we can address the second sum. If I α and I β are not independent, then they share some edge and the event that I α = 1 increases the probability that I β = 1, so E(I α I β ) > p α p β and we need only show convergence of

α∈Γ m n ,β∈Γ 0 α E(I α I β ). (6)
Let α ∈ Γ i,n and let β be such that the edges of β that are shared with those of α are found on j disjoint paths in each member of the pair and such that there are k literals on each member of β which are not on the paths common to both α and β. Then, the probability that any such fixed pair (α, β) is present in D F is p i+j+k . Notice that there are j more edges than literals in such an (α, β) configuration. This is what causes the expectation in question to converge to 0. Now for the details.

We will count the number of such pairs by first fixing α, and then examining the number of possible shared paths. Notice that by choosing 2j literals in one member of α we fix the endpoints for one of two possible collections of j shared paths. Thus, the number of ways to choose j paths from an i-cycle is 2 i 2j where 1 ≤ j ≤ i/2 . This fixes j pairs of complementary paths from the members of α that will be shared with β, but it does not determine which of the complementary paths will be chosen for a given member of β. There are 2 j binary sequences that are in one-to-one correspondence with the possible assignments of j paths to the first member of β. Thus there are 2 j+1 i 2j ways to select the j paths from α that will be shared with one of the members of β.

Next we consider the k additional literals in each member of β. There are no more than n-2j variables that do not correspond to the shared paths. Moreover, β is a complementary pair of simple cycles, which must have strictly distinct literals in each member of the pair. Thus, there are at most n-2j k 2 k possible ways to choose the remaining literals for one of the members of β.

Together, the literals and paths make for j +k objects to be ordered on a cycle, and there are (j +k -1)! ways to do this. Notice that we did not make use of the restriction that two paths are not allowed to be consecutive in this ordering if there is only one edge between them on α. Thus we are overestimating once again. The choices above, along with the (n) i 2 i-1 /i choices for α provide an upper bound for the total number of ordered pairs (α, β). There is just one last bit of counting to mention. We have double counted everything. That is, when we started selecting the k additional literals for one of the members of β, it matters which of the members these k literals go with; but we could get the same structure by selecting the complementary k literals and the complementary member of α. Thus, all together we have i + j + k -1 total factors of 2, which we will group together with the powers of p.

The computations on the following page are mostly self explanatory, but we mention that to obtain (12) and ( 13) we begin with the Robbins-Feller Stirling approximation and then simplify a bit to get j! < 2πj j e If we look at expression [START_REF] Palasti | On the threshold distribution function of cycles in a directed random graph[END_REF] we see that given any positive constant c < 1 we can choose m = m(n) so that for large enough n, we have m/n sufficiently small to satifty

c 1 + cm 2e(1 -c)n < 1.
Once this inequality is satisfied, the sum over i in the last line above will be bounded above by a constant, and it follows that the expectation for this m = m(n) will be O(n -1 ), which proves Lemma 14 . 2

As was previously stated, Lemma 13 follows from Lemma 14 and this is all that remained to prove Theorem 1.

2

Corollary 16 If 0 < c < c max , where c max ≈ 0.6375 is the solution to

c 1 + c 2e(1 -c) = 1,
then the rate of convergence of X n to Ψ n,n is O(n -1 ).

Proof: If c < c max , then the proof of Lemma 13 applies with m = n and we have a rate of convergence of O(n -1 ) for X n to Ψ n,n . 2

Discussion

The proof provided here of Lemma 13 relies on the use of truncated random variables and also fails to provide a bound on the distance between X n and Ψ n,n for a significant range of c values. If the proof of Lemma 14 could be improved to provide some rate of convergence f (n) that holds for m = n and all c < 1, then there would be no need for truncated random variables and the overall rate of convergence would be no slower than f (n). However, it may be difficult to find such a proof because there is reason to believe that the Chen-Stein method can not be applied to this problem. In [START_REF] Arratia | Poisson approximation and the chen-stein method[END_REF], they provide numerical evidence (pg. 413) that α∈Γn,β∈Γα E(I α I β ) diverges with m = n for sufficiently large values of c. If this is true, then for these values of c, the second moment of X n diverges with n and the Chen-Stein method will not be able to provide a rate of convergence for X n to Ψ n,n .

j e 1 /(12j) < 4 j j e j .

 1j Then we use j ≤ i/2 ≤ m to get

Acknowledgements

The author would like to thank Janko Gravner for suggesting this model and for his advisement in general. The author would also like to thank Jaikumar Radhakrishnan for suggesting the use of antichains. This work was in part supported by the National Science Foundation grant DMS-0204376.

(5)

Thus, to prove the weak convergence of X n to Ψ it is enough to show that we can choose n and m (which may depend on n) to make (3), ( 4) and ( 5) arbitrarily small. We first consider [START_REF] Biroli | A variational description of the ground state structure in random satisfiability problems[END_REF]. From (2), we see that when m diverges with n, λ m,n will become arbitrarily close to λ. Thus, we have the weak convergence of Ψ m,n to Ψ and (5) must vanish for any m that diverges with n.

We now focus on [START_REF] Aspvall | A linear-time algorithm for testing the truth of certain quantified Boolean formulas[END_REF]. Notice that (3) is bounded above by P (X n = T m,n ), which is in turn bounded above by the expected number of events that distinguish X n from T m,n . Notice that by (2) the probability that there are any i-cycles for i > m vanishes as m diverges. Notice also that by Lemma 11 we have for any m, that the probability that there is a strong component that is not a simple cycle is O(n -1 ). Lastly, by Lemma 12 the probability that there are two nontrivial strong components that are ordered is O(n -1 ) for any m. Thus, the probability that X n = T m,n vanishes as n and m diverge.

The supremum over all A of ( 4) is half the total variation between the law of T m,n and Ψ m,n . Thus, the bound for (4) and the proof of Lemma 13 is complete provided that the following lemma is true.

Lemma 14 There exists an m = m(n) that is unbounded such that the total variation between the law of T m,n and Poisson random variable with mean λ m,n is O(n -1 ).

Proof: There is a family of methods called the Stein-Chen or Chen-Stein method for bounding the total variation between two distributions. A thorough treatment of these methods can be found in [START_REF] Barbour | Poisson Approximation[END_REF]. Of particular interest here is Corollary 2.C.5, on pg. 26. of [START_REF] Barbour | Poisson Approximation[END_REF], which we restate using our current notation and the following definition. Let

Lemma 15 Suppose that for each α ∈ Γ m n , Γ m n can be partitioned into Γ 0 α , Γ i α such that I α and I β are independent for all β ∈ Γ i α . Then the total variation between the laws of T m,n and Ψ m,n is not more than

For any α, there certainly is a set Γ 0 α of all complementary cycle pairs that are distinct from α and yet not independent of α. Moreover, since λ m,n is bounded below, our proof will be complete when we can find an unbounded m = m(n) for which the sums are both O(n -1 ).

Consider the first sum


Nicholas A Loehr
email: nloehr@vt.edu.

Elizabeth Niese
email: eniese@vt.edu.

Recursions and divisibility properties for combinatorial Macdonald polynomials

Keywords: Macdonald polynomials, Garsia-Haiman modules, Hilbert series, bijections, recursions, q-analogues

For each integer partition µ, let Fµ(q, t) be the coefficient of x1 • • • xn in the modified Macdonald polynomial Hµ. The polynomial Fµ(q, t) can be regarded as the Hilbert series of a certain doubly-graded Sn-module Mµ, or as a q, t-analogue of n! based on permutation statistics invµ and maj µ that generalize the classical inversion and major index statistics. This paper uses the combinatorial definition of Fµ to prove some recursions characterizing these polynomials, and other related ones, when µ is a two-column shape. Our result provides a complement to recent work of Garsia and Haglund, who proved a different recursion for two-column shapes by representation-theoretical methods. For all µ, we show that Fµ(q, t) is divisible by certain q-factorials and t-factorials depending on µ. We use our recursion and related tools to explain some of these factors bijectively. Finally, we present fermionic formulas that express F (2 n ) (q, t) as a sum of q, t-analogues of n!2 n indexed by perfect matchings.

Introduction

The Macdonald polynomials P µ [START_REF] Macdonald | A new class of symmetric functions[END_REF] play a prominent role in algebraic combinatorics and the theory of symmetric functions. The polynomials P µ , as µ ranges over all integer partitions of n, form a basis for the vector space of symmetric polynomials of degree n with coefficients in the field Q(q, t). By specializing the parameters q and t in various ways, one can obtain many classical symmetric function bases from the Macdonald basis. For instance, P µ | t=1 is the monomial symmetric polynomial m µ ; P µ | q=1 is the elementary symmetric polynomial e µ ; P µ | q=t is the Schur symmetric polynomial s µ ; and P µ | q=0 is a Hall-Littlewood polynomial [START_REF] Macdonald | Symmetric functions and Hall polynomials[END_REF].

Garsia, Haglund, and Haiman (among others) studied modified versions of Macdonald polynomials, denoted H µ , that have remarkable connections to representation theory and combinatorics [START_REF] Garsia | A graded representation model for Macdonald's polynomials[END_REF][START_REF] Haglund | A combinatorial model for the Macdonald polynomials[END_REF][START_REF] Haglund | A combinatorial formula for Macdonald polynomials[END_REF]. To compute the modified polynomials H µ from the original polynomials P µ , one first multiplies each P µ by a certain scalar in Q(q, t) to obtain the integral forms J µ , then applies a suitable plethystic transform to obtain H µ , and finally sets H µ = t n(µ) H µ | t→1/t . See [START_REF] Garsia | A random q, t-hook walk and a sum of Pieri coefficients[END_REF][START_REF] Haglund | Combinatorial theory of Macdonald polynomials I: Proof of Haglund's formula[END_REF] for more details. One can also give a direct characterization of H µ in terms of triangularity and normalization axioms [START_REF] Haglund | A combinatorial formula for Macdonald polynomials[END_REF][START_REF] Haglund | Combinatorial theory of Macdonald polynomials I: Proof of Haglund's formula[END_REF], or one can define H µ to be the eigenfunctions of the linear operator ∆ 1 [START_REF] Garsia | A remarkable q, t-Catalan sequence and q-Lagrange inversion[END_REF].

In [START_REF] Garsia | A graded representation model for Macdonald's polynomials[END_REF], Garsia and Haiman defined doubly-graded S n -modules M µ and conjectured that the Frobenius series for these modules were none other than the modified Macdonald polynomials H µ . This conjecture was ultimately proved by Haiman using deep results from commutative algebra and algebraic geometry [START_REF] Haiman | Hilbert schemes, polygraphs, and the Macdonald positivity conjecture[END_REF][START_REF] Haiman | Notes on Macdonald polynomials and the geometry of Hilbert schemes. Symmetric Functions[END_REF]. Let F µ ∈ Q(q, t) be the coefficient of x 1 x 2 • • • x n in H µ ; equivalently, F µ = H µ , h (1 n ) . It follows from Haiman's result that F µ is the Hilbert series of the doubly-graded module M µ ; i.e., F µ (q, t) = i≥0 j≥0

dim(M (i,j) µ )q i t j , where M (i,j) µ denotes the bihomogeneous component of M µ of bidegree (i, j). In a groundbreaking paper [START_REF] Haglund | A combinatorial model for the Macdonald polynomials[END_REF], Haglund conjectured a combinatorial formula for F µ of the form

F µ = w∈Sn q invµ(w) t maj µ (w) , (1)
where inv µ , maj µ : S n → N are suitable permutation statistics parametrized by µ. This formula leads directly to a combinatorial prescription for the expansion of H µ into fundamental quasisymmetric polynomials. These formulas, which are described in more detail in §2 below, were proved by Haglund, Haiman, and Loehr [START_REF] Haglund | A combinatorial formula for Macdonald polynomials[END_REF][START_REF] Haglund | Combinatorial theory of Macdonald polynomials I: Proof of Haglund's formula[END_REF]. Haglund's formula opened the way to new explorations of the combinatorial properties of Macdonald polynomials and the associated Hilbert series F µ . A problem of ongoing interest involves the search for recursions characterizing the polynomials F µ , as µ ranges over all integer partitions. One such recursion follows from a version of the Pieri rules for Macdonald polynomials [START_REF] Macdonald | Symmetric functions and Hall polynomials[END_REF]. This recursion has the form F µ (q, t) = ν→µ c µ,ν (q, t) F ν (q, t), F (0) (q, t) = 1,

where we sum over all partitions ν that can be obtained from µ by removing a single corner box, and c µ,ν (q, t) ∈ Q(q, t) is a complicated quotient of two polynomials built from the arm and leg numbers of the cells in µ and ν [START_REF] Garsia | A random q, t-hook walk and a sum of Pieri coefficients[END_REF]. While this recursion is very striking, the presence of rational coefficients makes it difficult to use in combinatorial settings. For instance, there is presently no known combinatorial proof of this recursion based on (1), nor can one easily deduce the polynomiality of F µ from (2). In a very recent paper [GHar], Garsia and Haglund found a new recursion valid for polynomials F µ indexed by shapes µ with two columns. They proved this recursion using a multitude of clever representation-theoretical manipulations. In related work, M. Yoo used (1) to derive a combinatorial formula for polynomials F µ indexed by partitions µ of hook shape [START_REF] Yoo | Combinatorial formula for the Hilbert series of bigraded S n -modules[END_REF]. Some results for two-row shapes and rectangles appear in J. Bandlow's doctoral dissertation [START_REF] Bandlow | Combinatorics of Macdonald polynomials and extensions[END_REF].

The Garsia-Haglund recursion builds up a given shape µ from smaller shapes ν obtained by removing one of the inner corners of µ. In this paper, we shall present different recursions characterizing the polynomials F µ (where µ has two columns) that are based on removing the bottom row of µ. Our recursions are stated in Theorem 6.10 and Theorem 6.16 below. We will give a fully combinatorial proof of our recursions using bijections and combinatorial operations on permutations weighted by the statistics inv µ and maj µ . For our approach, it is more convenient to use F µ (q, t) = t n(µ) F µ (q, 1/t); this entails replacing maj µ by a related statistic comaj µ , which is defined in §2.

For

n ∈ N, let [n] t = 1 + t + t 2 + • • • + t n-1 and [n]! t = n i=1 [i] t . It is straightforward to deduce from Haglund's combinatorial formula (1) that F (1 n ) (q, t) = F (1 n ) (q, t) = [n]! t and F (n) (q, t) = F (n) (q, t) = [n]! q .
One consequence of our recursion is a combinatorial explanation of the fact that F (2 m ) (q, t) is divisible by [m]! t . We will prove the following more general divisibility property in §4.

Theorem 1.1 Let µ = (1 n1 2 n2 • • • k n k ) be an integer partition with µ = (1 m1 2 m2 • • • p mp ). (a) F µ (q, t) and F µ (q, t) are divisible by [m 1 ]! q [m 2 ]! q • • • [m p ]! q . (b) F µ (q, t) and F µ (q, t) are divisible by [n 1 ]! t [n 2 ]! t • • • [n k ]! t .
As we will see, (a) follows bijectively from a certain combinatorial move on permutations. Then (b) follows algebraically from (a) using the known symmetry property H µ (X; q, t) = H µ (X; t, q) of Macdonald polynomials [START_REF] Macdonald | Symmetric functions and Hall polynomials[END_REF]. One of our motivations for developing the recursions below is to obtain a greater understanding of why (b) holds at the combinatorial level. Proving (b) bijectively for general µ appears to be a difficult problem. We hope that the special cases considered here will yield some clues to the even more challenging problem of giving a bijective proof of the general symmetry property

F µ (q, t) = F µ (t, q).
2 Combinatorial Formula for F µ This section reviews Haglund's combinatorial formula for F µ (q, t) and defines a related polynomial F µ (q, t).

Definition 2.1 A partition of a positive integer n is a sequence µ = (µ 1 , µ 2 , . . . , µ k ) with µ 1 + µ 2 + • • • + µ k = n and µ 1 ≥ µ 2 ≥ • • • ≥ µ k > 0,
for some k. Let Par(n) be the set of all partitions of n. Definition 2.2 A standard filling T of shape µ ∈ Par(n) is a placement of the integers 1, 2, . . . , n in the Ferrers diagram of µ with each integer used exactly once. A filling can be identified with a permutation w ∈ S n by reading the rows of the diagram from left to right, beginning with the shortest row. The column words of a filling are obtained by reading the columns from top to bottom.

Example 2.3 For µ = (5, 3, 1), an example of a standard filling is:

T = 4 3 1 6 2 8 5 9 7
. This filling is identified with the permutation w = 431628597 ∈ S 9 . The column words for this filling are 432, 18, 65, 9, and 7.

In order to define the statistics inv µ (T ) and comaj µ (T ), we first recall some classical permutation statistics defined for w ∈ S n .

Definition 2.4 Fix w = w 1 w 2 • • • w n ∈ S n . An inversion of w is a pair i < j such that w i > w j . Note that i and j do not need to be consecutive. Let inv(w) be the number of inversions of w. A descent of w is an index i < n with w i > w i+1 . The descent set of w is Des(w) = {i : w i > w i+1 }. The major index of w is maj(w) = i∈Des(w) i. Similarly, define the ascent set Asc(w) = {i : w i < w i+1 } and the co-major index comaj(w) = i∈Asc(w) i. Definition 2.10 For all partitions µ, let F µ be the set of all standard fillings of the shape µ.

Haglund's combinatorial formula [START_REF] Haglund | A combinatorial model for the Macdonald polynomials[END_REF] for F µ (q, t) is

F µ (q, t) = T ∈Fµ q invµ(T ) t maj µ (T ) .
Definition 2.11 For T ∈ F µ , define comaj µ (T ) = n(µ) -maj µ (T ). Note that comaj µ (T ) can also be written as the sum of the co-major indices of the column words of T .

In the following, we will use the specialization

F µ (q, t) = t n(µ) F µ (q, 1/t) = T ∈Fµ q invµ(T ) t comaj µ (T ) . F µ (q, t) is the coefficient of x 1 x 2 • • • x n in the (unmodified) Macdonald polynomial H µ (x 1 , x 2 , . . . , x n ; q, t).

The Inversion Flip Operation

This section describes a combinatorial operation on fillings called the inversion flip that will allow us to partially sort the bottom row of a filling T ∈ F µ . A similar operation on fillings that may have repeated symbols was studied by Bandlow [Ban07, Section 5.5].

Definition 3.1 Suppose µ ∈ Par(n) and i ∈ N + satisfy µ i = µ i+1 . Define the inversion flip move s i : F µ → F µ as follows:

• Given T ∈ F µ , let a (resp. b) be the entry of T at the bottom of column i (resp. i + 1).

• Switch entries a and b in the bottom row as shown here:

c d a b → c d b a .
• If a, c, d and b, c, d are either both inversion triples or both not inversion triples, the move is complete. Otherwise, apply s i recursively to the filling T of (µ 2 , µ 3 , . . .) obtained by ignoring the bottom row of T .

Lemma 3.2 Given µ ∈ Par(n) and i, j ∈ N + with µ i = µ i+1 and µ j = µ j+1 , (a) s 2 i = s i • s i = id Fµ ; (b) s i • s j = s j • s i when |i -j| ≥ 2.
Proof: Both properties follow directly from the definition of s i . 2

Remark 3.3 The s i 's do not satisfy the braid relations in general; i.e., when µ i = µ i+1 = µ i+2 , we may have

s i • s i+1 • s i = s i+1 • s i • s i+1 .
This can be seen in Figure 1.

1 3 5 2 6 4 s2 -→ 1 5 3 2 4 6 s1 -→ 1 5 3 4 2 6 s2 -→ 1 5 3 4 6 2 1 3 5 2 6 4 s1 -→ 3 1 5 6 2 4 s2 -→ 3 1 5 6 4 2 s1 -→ 3 1 5 4 6 2 Fig. 1: si • si+1 • si = si+1 • si • si+1 in general.
Proposition 3.4 Given µ ∈ Par(n) and i ∈ N + with µ i = µ i+1 , let T ∈ F µ have entries a and b in the bottom row of columns i and i + 1, respectively. Then:

(a) comaj µ (s i (T )) = comaj µ (T ); (b) maj µ (s i (T )) = maj µ (T ); (c) inv µ (s i (T )) = inv µ (T ) + 1 if a < b; -1 if b < a.
Proof: (cf. [Ban07, Section 5.5]) Since every column contributes independently to comaj µ and maj µ , to prove (a) and (b) it is sufficient to consider a filling T of shape µ = (2 n ) and i = 1. By 3.2(a) we may also assume that the bottom row of T is increasing. We must show that comaj µ (s 1 (T )) = comaj µ (T ), which automatically yields maj µ (s 1 (T )) = maj µ (T ). This result is true when n = 1.

When n = 2, we can write

T = c d a b . If s 1 (T ) = d c b a , column words are preserved, so comaj µ (s 1 (T )) = comaj µ (T ) and maj µ (s 1 (T )) = maj µ (T ).
It is also possible that

s 1 (T ) = c d b a .
In this case, if a, c, d formed an inversion triple in T , then b, c, d forms an inversion triple in

s 1 (T ). If a < b < d < c, d < c < a < b, or c < a < b < d,
then the location and number of the ascents are preserved, so comaj µ (s 1 (T )) = comaj µ (T ). If a < d < c < b, the number of ascents is preserved, but the column in which the ascent is located changes. However, since the columns are of equal height,

comaj µ (s 1 (T )) = comaj µ (T ). Similarly, if a, c, d is not an inversion triple in T , then b, c, d is not an inversion triple in s 1 (T ). If a < b < c < d, c < d < a < b, or d < a < b < c
, the location and number of ascents are preserved. If a < c < d < b, the number of ascents are preserved, but the column in which the ascent is located changes. As before, since the columns are of equal height, comaj µ (s 1 (T )) = comaj µ (T ). By induction, this result holds for any number of rows.

To show that inv µ (s i (T )) = inv µ (T ) + 1, we must show that the inversion flip does not affect the total number of inversion triples, excluding the triple a, b, ∞. By the definition of the inversion flip, it is sufficient to consider triples positioned as shown:

c d a b • • • z
since all other triples in T will be preserved. Once again, there are two possibilities. First, if

s i (T ) = d c b a • • • z ,
the inversion triples themselves are preserved. On the other hand, if

s i (T ) = c d b a • • • z ,
to show that the total number of inversion triples is preserved requires a tedious case analysis. We present several cases here and leave the remainder to the reader. First, suppose z < a < b < c < d. Then none of z < a < c, z < b < c, z < a < d, and z < b < d are inversion triples. Next, if a < z < b < c < d, then a < z < c is an inversion triple in T , and z < b < c is not an inversion triple in s i (T ). On the other hand, z < b < d is not an inversion triple in T , but a < z < d is an inversion triple in s i (T ). Thus, the total number of inversion triples is preserved. The remaining cases are similar. 2

4 Divisibility Properties for F µ

We now prove Theorem 1.

1. Given µ = (1 n1 2 n2 • • • k n k ) with µ = (1 m1 2 m2 • • • p mp ), we must prove that F µ (q, t) and F µ (q, t) are divisible by (a) [m 1 ]! q [m 2 ]! q • • • [m p ]! q and (b) [n 1 ]! t [n 2 ]! t • • • [n k ]! t .
First we prove (a) bijectively by using the inversion flip. We begin by considering a filling T of shape µ = (m n ). For 1 ≤ i ≤ m, let k i be the ith smallest entry in the bottom row of T , and let c 1 , c 2 , . . . , c m be the cells in the bottom row of µ.

If k m is in cell c i , applying s m-1 • s m-2 • • • • • s i will move k m to cell c m .
Continue likewise to move each k i into cell c i in decreasing order. The sequence of inversion flips used to sort the k i 's gives rise to a permutation w ∈ S m , by replacing each s j in the sequence by the basic transposition (j, j + 1). Let T be the filling that results from sorting T in this way. By 3.4(c), inv µ (T ) = inv µ (T ) + inv(w) and comaj µ (T ) = comaj µ (T ). Hence,

F µ (q, t) = T ∈Fµ q invµ(T ) t comaj µ (T ) = T ∈Fµ with increasing row 1 w∈Sm q invµ(T )+inv(w) t comaj µ (T ) = w∈Sm q inv(w)
T ∈Fµ with increasing row 1 q invµ(T ) t comaj µ (T ) = [m]! q T ∈Fµ with increasing row 1 q invµ(T ) t comaj µ (T ) . This result can be extended to µ ∈ Par(n) with µ = (1 m1 2 m2 • • • p mp ) by applying the above argument to each set of m i columns of equal height. Thus

F µ (q, t) is divisible by [m 1 ]! q • • • [m p ]! q . It follows that F µ (q, t) = t n(µ) F µ (q, 1/t)
is divisible by the same factors. We remark that the divisibility property 1.1(a) for rectangles is also a consequence of [START_REF] Bandlow | Combinatorics of Macdonald polynomials and extensions[END_REF], Corollary 3 in Section 5.5.

Part (b) of 1.1 follows algebraically from (a) and the fact that

F µ (q, t) = F µ (t, q).
Example 4.1 For µ = (5, 5, 2, 2), consider the filling T = 4 2 9 12 13 8 5 1 14 11 3 10 6 7

.

Then s 1 (s 4 (s 3 (T ))) = s 4 (s 3 (s 1 (T ))), and

s 1 (s 4 (s 3 (T ))) =
4 2 9 12 8 13 5 1 14 3 11 6 7 10

.

Considering the first two columns, the transposition associated with s 1 is (1, 2), so the permutation generated by the inversion flip is 12 ∈ S 2 . Considering the last three columns, the transpositions associated with s 3 and s 4 are (3, 4) and (4, 5), respectively. This gives us the permutation 534 of {3, 4, 5}.

The Cyclic Shift Operation

We wish to obtain a combinatorial explanation for part (b) of Theorem 1.1, at least in the case where µ is a two-column rectangle. For this, we must first define another bijection on standard fillings. (c) inv µ (cyc(T )) = inv µ (T ).

Proof: This can be seen by considering what happens to the cell c containing n in a filling.

n cyc --→ 1
The ascent between n and the cell above (if any) is shifted downward by a unit, while the descent between n and the cell below are shifted up one unit. All other ascents and descents are unaffected. All triples in T which do not involve n are preserved. Triples in T which include n have the form a < b < n. The corresponding triple in T will be 1 < a + 1 < b + 1. Thus, the status of the triple will be preserved. The assumption that n is not in the bottom row is needed to ensure that no triple involving n also involves an ∞ below the bottom row. Therefore,

s 1 • cyc = cyc •s 1 . 2 Proposition 5.6 Let T ∈ F (2 n ) for some n ≥ 1 where 2n is in the bottom row of T . Let S = s 1 (cyc(T )). Then comaj (2 n ) (S) = comaj (2 n ) (T ) -(n -1) and inv (2 n ) (S) = inv (2 n ) (T ).
Proof: First notice that when 2n is in the bottom row of T ,

inv (2 n ) (cyc(T )) = inv (2 n ) (T ) + 1 if 2n is in column 2; -1 if 2n is in column 1. Since the entry 2n in T becomes 1 in cyc(T ), comaj (2 n ) (cyc(T )) = comaj (2 n ) (T ) -(n -1)
because the ascent which occurs in T between 2n and the entry above it is lost. It follows from 3.4 that

inv (2 n ) (S) = inv (2 n ) (s 1 (cyc(T ))) = inv (2 n ) (T ) and comaj (2 n ) (S) = comaj (2 n ) (s 1 (cyc(T ))) = comaj (2 n ) (T ) -(n -1) .

Recursions for Two-Column Shapes

In this section, we consider what happens when we fix the bottom row of the fillings of (2 n ) to be 1 a . This will lead to a recursion characterizing the polynomials F (2 n ) (q, t).

Definition 6.1 For n ≥ 1 and 2 ≤ a ≤ 2n, set

F (2 n ),a = {T ∈ F (2 n ) : T has bottom row 1 a }. Define R (2 n ),a = R (2 n ),a (q, t) = T ∈F (2 n ),a q inv (2 n ) (T ) t comaj (2 n ) (T ) .

Augmentation

Definition 6.2 For n ≥ 1, T ∈ F (2 n ) and 2 ≤ a ≤ 2n + 2, we define the a-augmentation of T to be the filling A a (T ) ∈ F (2 n+1 ),a which is obtained by first relabeling the entries of T as follows: c ∈ T is replaced by c + 1 if c < a -1 and by c + 2 if c ≥ a -1; and then placing the relabeled filling over the new bottom row 1 a . .

We consider next what A a does to inv µ and comaj µ and how it interacts with cyc and s 1 . Here and below, for any statement P , we write χ(P ) = 1 if P is true and χ(P ) = 0 if P is false. Proposition 6.4 For all n ≥ 2, all a with 2 ≤ a ≤ 2n, and all T ∈ F (2 n-1 ) with bottom row x z ,

(a) comaj (2 n ) (A a (T )) = comaj (2 n-1 ) (T ) + (n -1)χ(z < a -1); (b) inv (2 n ) (A a (T )) = inv (2 n-1 ) (T ).
Proof: Let T ∈ F (2 n-1 ) have bottom row x z , and let 2 ≤ a ≤ 2n. The bottom two rows of A a (T ) look like:

x z 1 a

where x is x + 1 if x < a -1 or x + 2 if x ≥ a -1, and z is z + 1 if z < a -1 or z + 2 if z ≥ a -1. Now inv (2 n ) (A a (T )) = inv (2 n-1 ) (T )
since the two entries in the bottom row of A a (T ) do not form an inversion triple, and 1, x , z form an inversion triple in A a (T ) iff ∞, x, z form an inversion triple in T . The ascents in the top n -1 rows of A a (T ) are the same as the ascents in T . There cannot be an ascent between the two lowest cells in column 1 of A a (T ) since the lowest cell in this column contains 1. If a is greater than the entry directly above it in A a (T ), that entry is z + 1, giving a new ascent, so

comaj (2 n ) (A a (T )) = comaj (2 n-1 ) (T ) + n -1.
If a is less than the entry directly above it in A a (T ), that entry must be z + 2, and thus comaj (2 n ) (A a (T )) = comaj (2 n-1 ) (T ). 2 Definition 6.5 For all n ≥ 2 and all a with 2 ≤ a ≤ 2n, define cyc :

F (2 n ),a → F (2 n ),a by cyc = A a • cyc •A -1 a . Similarly, define s 1 : F (2 n ),a → F (2 n ),a by s 1 = A a • s 1 • A -1 a . Proposition 6.6 For all n, a, b, j, T with n ≥ 2, 2 ≤ a ≤ 2n, 2 ≤ b ≤ 2n -2, 0 ≤ j ≤ 2n -2 -b, and T ∈ F (2 n-1 ),b : (a) comaj (2 n ) (cyc j (A a (T ))) = comaj (2 n-1 ) (T ) + j + (n -1)χ(j < a -b -1); (b) inv (2 n ) (cyc j (A a (T ))) = inv (2 n-1 ) (T ); (c) comaj (2 n ) (cyc j (s 1 (A a (T )))) = comaj (2 n-1 ) (T ) + j + (n -1)χ(j < a -2); (d) inv (2 n ) (cyc j (s 1 (A a (T )))) = inv (2 n-1 ) (T ) + 1. Proof: Let T ∈ F (2 n-1
),b . Then, by 5.3 and 6.4,

comaj (2 n ) (cyc j (A a (T ))) = comaj (2 n ) (A a (cyc j (T )) = comaj (2 n-1 ) (cyc j (T )) + (n -1)χ(b + j < a -1) = comaj (2 n-1 ) (T ) + j + (n -1)χ(j < a -b -1).
By 5.3 and 6.4, inv (2 n ) (cyc j (A a (T ))) = inv (2 n-1 ) (T ).

Similarly, using 5.5, 6.4, and 5.3, we find that

comaj (2 n ) (cyc j (s 1 (A a (T )))) = comaj (2 n ) (A a (cyc j (s 1 (T )))) = comaj (2 n ) (A a (s 1 (cyc j (T )))) = comaj (2 n-1 ) (cyc j (T )) + (n -1)χ(1 + j < a -1) = comaj (2 n-1 ) (T ) + j + (n -1)χ(j < a -2).
By 6.4, 5.3, and 3.4,

inv (2 n ) (cyc j (s 1 (A a (T )))) = inv (2 n-1 ) (T ) + 1. 2 Proposition 6.7 For all n ≥ 1 and 2 ≤ a ≤ 2n, R (2 n ),2n-a+2 = t n-a+1 R (2 n ),a .
Proof: It suffices to prove the result for 2 ≤ a ≤ n. Note that s 1 • cyc 2n-a+1 is a bijection from F (2 n ),a onto F (2 n ),2n-a+2 . For T ∈ F (2 n ),a , 5.3 and 5.6 give

comaj (2 n ) (s 1 (cyc 2n-a+1 (T ))) = comaj (2 n ) (T ) + 2n -a -(n -1) = comaj (2 n ) (T ) + n -a + 1; inv (2 n ) (s 1 (cyc 2n-a+1 (T ))) = inv (2 n ) (T ). 2

Recursions for Two-Column Rectangles

We can compute R (2 n ),a for 2 ≤ a ≤ n + 1 by the recursion below. A nicer version of this recursion appears in 6.10 below.

Proposition 6.8 For all n ≥ 2 and 2 ≤ a ≤ n + 1,

R (2 n ),a =[n -1] t n-1 b=2 (t (a-b-1) + + t n-b + qt a-2 + qt n-1-(b+1-a) + )R (2 n-1 ),b + (1 + qt a-2 )R (2 n-1 ),n
where R (2),2 = 1 and x + = max{x, 0}.

Proof: To prove the theorem bijectively, we will decompose

F (2 n ),a into a collection of disjoint sets X 2 , . . . , X n , Y 2 , . . . , Y n , such that the generating function for X b is [n -1] t (t (a-b-1) + + t n-b )R (2 n-1 ),b when 2 ≤ b < n, and [n -1] t R (2 n-1 ),n when b = n. Similarly, the generating function for Y b is [n -1] t (qt a-2 + qt n-1-(b+1-a) + )R (2 n-1 ),b when 2 ≤ b < n, and [n -1] t qt a-2 R (2 n-1 ),n when b = n. For 2 ≤ b ≤ n, define X b = {T ∈ F (2 n ),a : for some U ∈ F (2 n-1 ),b , T = cyc i (A a (U )) where 0 ≤ i ≤ 2n -2 -b or T = cyc j (s 1 (A a (U ))) for 2n -1 -b ≤ j ≤ 2n -3}
and

Y b = {T ∈ F (2 n ),a : for some U ∈ F (2 n-1 ),b , T = cyc i (s 1 (A a (U ))) where 0 ≤ i ≤ 2n -2 -b or T = cyc j (A a (U )) for 2n -1 -b ≤ j ≤ 2n -3}.
Using 3.2, 5.2, and 5.5, one sees that each T ∈ F (2 n ),a can be written as cyc j (s 1 (A a (U ))) for exactly one choice of j ∈ {0, 1, . . . , 2n -3}, ∈ {0, 1}, b ∈ {2, . . . , n}, and U ∈ F (2 n-1 ),b . To find j, , b, and U , delete the bottom row of T , renumber the remaining entries to be {1, 2, . . . , 2n -2}, cyclically shift down until 1 appears in the new bottom row, and then apply s 1 if needed to get 1 in the lower-left corner. For example, if n = 5 and a = 4, the filling

T = 9 3 6 10 2 7 5 8 1 4
can be written as cyc 2 (A 4 (U )) where

U = 5 8 2 6 7 3 1 4 . It follows that F (2 n ),a
is the disjoint union of the sets X b and Y b just defined. By 5.6 and 6.6, inv

(2 n ) (cyc i (A a (U ))) = inv (2 n ) (cyc j (s 1 (A a (U )))) = inv (2 n-1 ) (U ) for all 0 ≤ i ≤ 2n -2 -b and all 2n -1 -b ≤ j ≤ 2n -3. Similarly, inv (2 n ) (cyc i (s 1 (A a (U )))) = inv (2 n ) (cyc j (A a (U ))) = inv (2 n-1 ) (U ) + 1
for all i, j in the indicated ranges. Before continuing the proof, we give an example that illustrates the main ideas in the calculations that follow. Notice that q inv (2 3 ) (U ) t comaj (2 3 ) (U ) = q 2 t 1 . In Figure 2, the fillings in bold are elements of X 3 derived from U , while the rest are elements of Y 3 derived from U . The generating functions for these elements in X 3 and Y 3 are [3] t (1 + t)q 2 t 1 and [3] t (qt 2 + qt 3 )q 2 t 1 , respectively.

Returning to the proof, we first consider the case where 2 ≤ b < n and a ≤ b+1.

Let U ∈ F (2 n-1 ),b . By 6.6, comaj (2 n ) (cyc i (A a (U ))) = comaj (2 n-1 ) (U )+i for 0 ≤ i ≤ 2n-2-b. For 2n-1-b ≤ i ≤ 2n-3, comaj (2 n ) (cyc i (s 1 (A a (U )))) = comaj (2 n-1 ) (U ) + i -(n -1)
by 6.6 and 5.6, since 2n -b > a.

3 3 3 8 8 8 7 7 7 6 6 6 2 2 2 5 5 5 1 1 1 4 4 4 cyc --→ 5 5 5 2 2 2 8 8 8 7 7 7 3 3 3 6 6 6 1 1 1 4 4 4 cyc --→ 6 6 6 3 3 3 2 2 2 8 8 8 5 5 5 7 7 7 1 1 1 4 4 4 cyc --→ 7 7 7 5 5 5 3 3 3 2 2 2 6 6 6 8 8 8 1 1 1 4 4 4 cyc --→ 8 6 5 3 7 2 1 4 cyc --→ 2 7 6 5 8 3 1 4 q 2 t q 2 t 2 q 2 t 3 q 2 t 4 q 3 t 5

q 3 t 6 s 1 s 1 s 1 s 1 s 1 s 1 3 8 7 6 5 2 1 4 cyc --→ 5 2 8 7 6 3 1 4 cyc --→ 6 3 2 8 7 5 1 4 cyc --→ 7 5 3 2 8 6 1 4 cyc --→
8 8 8 6 6 6 5 5 5 3 3 3 2 2 2 7 7 7 1 1 1 4 4 4 cyc --→ 2 2 2 7 7 7 6 6 6 5 5 5 3 3 3 8 8 8 1 1 1 4 4 4 q 3 t 4 q 3 t 5 q 3 t 3 q 3 t 4 q 2 t 2 q 2 t 3 We now compute 2n-3

i=0 t comaj (2 n ) (cyc i (Aa(U ))
) by splitting the sum into the ranges

0 ≤ i ≤ n -2, n -1 ≤ i ≤ 2n -2 -b, and 2n -1 -b ≤ i ≤ 2n -3. For i in the first range, we compute n-2 i=0 t comaj (2 n ) (cyc i (Aa(U ))) = [n -1] t t comaj (2 n-1 ) (U ) = [n -1] t t (a-b-1) + t comaj (2 n-1 ) (U ) .
For the remaining values of i, we obtain

2n-2-b i=n-1 t comaj (2 n ) (cyc i (Aa(U ))) + 2n-3 i=2n-1-b t comaj (2 n ) (cyc i (s1(Aa(U )))) = t comaj (2 n-1 ) (U ) 2n-2-b i=n-1 t i + 2n-3 i=2n-1-b t i-(n-1) = t comaj (2 n-1 ) (U ) 2n-2-b i=n-1 t i + n-2 i=n-b t i = [n -1] t t n-b+comaj (2 n-1 ) (U ) .
Thus, the generating function for

X b is [n -1] t (t (a-b-1) + + t n-b )R (2 n-1 ),b
. Similarly, we can use 6.6 and 5.6 to obtain:

comaj (2 n ) (cyc i (s1(Aa(U )))) = comaj (2 n-1 ) (U ) + i + n -1 if 0 ≤ i < a -2; comaj (2 n ) (cyc i (s1(Aa(U )))) = comaj (2 n-1 ) (U ) + i if a -2 ≤ i ≤ 2n -2 -b; comaj (2 n ) (cyc i (Aa(U ))) = comaj (2 n-1 ) (U ) + i if 2n -1 -b ≤ i < a -2 + (2n -1 -b); comaj (2 n ) (cyc i (Aa(U ))) = comaj (2 n-1 ) (U ) + i -(n -1) if a -2 + (2n -1 -b) ≤ i ≤ 2n -3. Then 2n-3 i=0 t comaj (2 n ) (cyc i (s1(Aa(U )))) = a-3 i=0 t comaj (2 n-1 ) (U )+i+n-1 + n-2 i=a-2 t comaj (2 n-1 ) (U )+i + 2n-2-b i=n-1 t comaj (2 n-1 ) (U )+i + a+2n-b-4 i=2n-b-1 t comaj (2 n-1 ) (U )+i + 2n-3 i=a+2n-b-3 t comaj (2 n-1 ) (U )+i-(n-1) = a+n-4 i=a-2 t i + a+2n-b-4 i=n-1 t i + n-2 i=a+n-b-2 t i t comaj (2 n-1 ) (U ) = [n -1] t (t a-2 + t n-1-(b+1-a) )t comaj (2 n-1 ) (U ) .
So the generating function for Y b in this case is

[n -1] t q(t a-2 + t n-1-(b+1-a) + )R (2 n-1 ),b .
Next we look at what happens when b + 1 < a, 2 ≤ b < n, and 2 ≤ a ≤ n + 1. Let U ∈ F (2 n-1 ),b . Then, by 6.6 and 5.6,

comaj (2 n ) (cyc i (A a (U ))) = comaj (2 n-1 ) (U ) + i + n -1 if 0 ≤ i < a -b -1; comaj (2 n ) (cyc i (A a (U ))) = comaj (2 n-1 ) (U ) + i if a -b -1 ≤ i ≤ 2n -b -2; comaj (2 n ) (cyc i (s 1 (A a (U )))) = comaj (2 n-1 ) (U ) + i -(n -1) if 2n -b -1 ≤ i ≤ 2n -3. Then 2n-3 i=0 t comaj (2 n ) (cyc i (Aa(U ))) = a-b-2 i=0 t comaj (2 n-1 ) (U )+i+n-1 + n-2 i=a-b-1 t comaj (2 n-1 ) (U )+i + 2n-b-2 i=n-1 t comaj (2 n-1 ) (U )+i + 2n-3 i=2n-b-1 t comaj (2 n-1 ) (U )+i-(n-1) = n+a-b-3 i=n-1 t i + n-2 i=a-b-1 t i + 2n-b-2 i=n-1 t i + n-2 i=n-b t i t comaj (2 n-1 ) (U ) = [n -1] t (t (a-b-1) + t n-b )t comaj (2 n-1 ) (U ) .
Thus, the generating function for X b in this case is

[n -1] t (t (a-b-1) + + t n-b )R (2 n-1 ),b .
Similarly, for Y b , we have

comaj (2 n ) (cyc i (s 1 (A a (U )))) = comaj (2 n-1 ) (U ) + i + n -1 if 0 ≤ i < a -2; comaj (2 n ) (cyc i (s 1 (A a (U )))) = comaj (2 n-1 ) (U ) + i if a -2 ≤ i ≤ 2n -2 -b; comaj (2 n ) (cyc i (A a (U ))) = comaj (2 n-1 ) (U ) + i if 2n -1 -b ≤ i ≤ 2n -3. Then 2n-3 i=0 t comaj (2 n ) (cyc i (s1(Aa(U )))) = a-3 i=0 t comaj (2 n-1 ) (U )+i+n-1 + n-2 i=a-2 t comaj (2 n-1 ) (U )+i + 2n-2-b i=n-1 t comaj (2 n-1 ) (U )+i + 2n-3 i=2n-1-b t comaj (2 n-1 ) (U )+i = [n -1] t (t a-2 + t n-1 )t comaj (2 n-1 ) (U ) .
So the generating function for Y b in this case is [n -1] t q(t a-2 + t n-1 )R (2 n-1 ),b . Combining all of the above gives us that, for 2 ≤ b < n, the generating function for

X b is [n -1] t (t (a-b-1) + + t n-b )R (2 n-1 ),b and the generating function for Y b is [n -1] t q(t a-2 + t n-1-(b+1-a) + )R (2 n-1 ),b . When b = n and U ∈ F (2 n-1 ),n , A a (U ), cyc(A a (U )), . . . , cyc n-2 (A a (U )) ∈ X n and s 1 (A a (U )), cyc(s 1 (A a (U ))), . . . , cyc n-2 (s 1 (A a (U ))) ∈ Y n . Since a -n -1 ≤ 0, comaj (2 n ) (cyc i (A a (U ))) = comaj (2 n-1 ) (U ) + i, so the generating function for X n is [n -1] t R (2 n-1
),n . To obtain the generating function for Y n , we note that

comaj (2 n ) (cyc i (s 1 (A a (U )))) = comaj (2 n-1 ) (U ) + i + n -1 if 0 ≤ i < a -2 comaj (2 n ) (cyc i (s 1 (A a (U )))) = comaj (2 n-1 ) (U ) + i if a -2 ≤ i ≤ n -2.
Then, as above, the generating function for

Y n is [n -1] t (qt a-2 )R (2 n-1 ),n . 2
We can use 6.7 to obtain the following more streamlined version of the recursion for two-column rectangles.

Theorem 6.10 For all n ≥ 2 and 2 ≤ a ≤ 2n,

R (2 n ),a = [n -1] t 2n-2 b=2 t (a-b-1) + + qt n-1-(b+1-a) + R (2 n-1 ),b ,
where R (2),2 = 1 and x + = max(x, 0).

Proof: First, we use 6.7 to rewrite the recursion from 6.8 for 2 ≤ a ≤ n + 1. We see that R (2 n ),a equals

[n -1] t n-1 b=2 (t (a-b-1) + + t n-b + qt a-2 + qt n-1-(b+1-a) + )R (2 n-1 ),b + (1 + qt a-2 )R (2 n-1 ),n = [n -1] t n-1 b=2 (t (a-b-1) + + qt n-1-(b+1-a) + )R (2 n-1 ),b + n-1 b=2 t b-n (t n-b + qt a-2 )R (2 n-1 ),2n-b +(1 + qt a-2 )R (2 n-1 ),n = [n -1] t n b=2 (t (a-b-1) + + qt n-1-(b+1-a) + )R (2 n-1 ),b + n-1 b=2 (1 + qt a+b-n-2 )R (2 n-1 ),2n-b = [n -1] t n b=2 (t (a-b-1) + + qt n-1-(b+1-a) + )R (2 n-1 ),b + 2n-2 b=n+1 (1 + qt n-1-(b+1-a) )R (2 n-1 ),b = [n -1] t 2n-2 b=2 (t (a-b-1) + + qt n-1-(b+1-a) + )R (2 n-1 ),b .
To see that this same recursion works for n + 2 ≤ a ≤ 2n, apply 6.7 again. For

a with n + 2 ≤ a ≤ 2n, note that 2 ≤ 2n -a + 2 ≤ n + 1. Then R (2 n ),a = t a-n-1 R (2 n ),2n-a+2 = t a-n-1 [n -1] t 2n-2 b=2 (t (2n-a+2-b-1) + + qt n-1-(b+1-(2n-a+2)) + )R (2 n-1 ),b = [n -1] t 2n-2 b=2 (t a-n-1+(2n-a+2-b-1) + + qt a-2-(b+a-2n-1) + )R (2 n-1 ),b .
One final application of 6.7, this time to

R (2 n-1 ),b for 2 ≤ b ≤ 2n -2, leads to R (2 n ),a = [n -1] t t n-b 2n-2 b=2 (t a-n-1+(2n-a+1-(2n-b)) + + qt a-2-(2n-b+a-2n-1) + )R (2 n-1 ),b = [n -1] t 2n-2 b=2 (t a-b-1+(b+1-a) + + qt n-b+a-2-(a-b-1) + )R (2 n-1 ),b = [n -1] t 2n-2 b=2 (t (a-b-1) + + qt n-1-(b+1-a) + )R (2 n-1 ),b . 2 Proposition 6.11 For n ≥ 1, F (2 n ) (q, t) = R (2 n+1 ),2 (q, t).
The bottom row of cyc m+2n-x (T ) is x z where x = m + 2n and z = m + 2n -x + z. Then cyc m+2n-x+1 (T ) has bottom row 1 b with b = m + 2n -x + z + 1. The ascent involving x and the entry directly above it in cyc m+2n-x (T ) is lost when cyc is applied, so

comaj (1 m 2 n ) (cyc m+2n-x+1 (T )) = comaj (1 m 2 n ) (cyc m+2n-x (T )) -(m + n -1) and thus comaj (1 m 2 n ) (cyc m+2n-x+1 (T )) = comaj (1 m 2 n ) (T ) + n + 1 -x. By 5.3, inv (1 m 2 n ) (cyc m+2n-x (T )) = inv (1 m 2 n ) (T ).
Since m + 2n is in the bottom row of cyc m+2n-x (T ),

inv (1 m 2 n ) (cyc m+2n-x+1 (T )) = inv (1 m 2 n ) (cyc m+2n-x (T )) -1, so inv (1 m 2 n ) (cyc m+2n-x+1 (T )) = inv (1 m 2 n ) (T ) -1. 2
We can calculate R (1 m 2 n ),a for 2 ≤ a ≤ m + 2n by the recursion below.

Theorem 6.16 For all m ≥ 1, n ≥ 2, and 2 ≤ a ≤ m + 2n,

R (1 m 2 n ),a = m+2n-2 b=2 m+2n-2-b i=0 t i+(n-1)χ(i<a-b-1) R (1 m 2 n-1 ),b +qt b-n+i+(n-1)χ(i<a-2) R (1 m 2 n-1 ),m+2n-b . The initial conditions are R (1 m 2),a = F (1 m ) = [m]! t for m ≥ 1 and 2 ≤ a ≤ m + 1. Proof: Let T ∈ F (1 m 2 n ),a .
Then there exists a unique U ∈ F (1 m 2 n-1 ) such that T = A a (cyc i (U )) and the bottom row of U is either 1 b or b 1 for some b with 2 ≤ b ≤ m + 2n -2 and some i with

0 ≤ i ≤ m + 2n -2 -b.
If the bottom row of U is 1 b , then by 6.14 and 5.3

comaj (1 m 2 n ) (T ) = comaj (1 m 2 n ) (A a (cyc i (U ))) = comaj (1 m 2 n-1 ) (U ) + i + (n -1)χ(i < a -b -1) and inv (1 m 2 n ) (T ) = inv (1 m 2 n-1 ) (U ).
If the bottom row of U is b 1 , then by 6.14 and 5.3,

comaj (1 m 2 n ) (T ) = comaj (1 m 2 n ) (A a (cyc i (U ))) = comaj (1 m 2 n-1 ) (U ) + i + (n -1)χ(i < a -2).
Let U = cyc m+2n-1-b (U ), then, by 6.15,

comaj (1 m 2 n ) (T ) = comaj (1 m 2 n-1 ) (U ) + i + (n -1)χ(i < a -2) = comaj (1 m 2 n-1 ) (U ) + i + b -n + (n -1)χ(i < a -2) and inv (1 m 2 n ) (T ) = inv (1 m 2 n-1 ) (U ) + 1.
Thus the second term in the recursion accounts for fillings T arising from those U having a decreasing bottom row. 2 Remark 6.17 We saw earlier that R (1 m 2 n+1 ),2 (q, t) = F (1 m 2 n ) (q, t) is divisible by [m]! t [n]! t . The recursion above easily yields that every R (1 m 2 n ),a (q, t) is divisible by [m]! t . Computations suggest that these polynomials are also divisible by [n -1]! t , but this fact does not seem to be evident from the form of our recursion. In particular (in contrast to the situation for two equal columns), we have not given a combinatorial explanation of the divisibility of F (1 m 2 n ) (q, t) by [n]! t .

Fermionic Formula

In the case of two-column rectangles, we can use our earlier recursion to deduce some fermionic formulas for F (2 n ) (q, t) and R (2 n+1 ,a) (q, t). For each n ≥ 1, define Iteration of this recursion immediately yields the following fermionic formula for R (2 n+1 ),a .

Theorem 7.1 For all n ≥ 0 and 2 ≤ a 0 ≤ 2n + 2, R (2 n+1 ),a0 = [n]! t (a1,a2,...,an)∈Pn n i=1 (t (ai-1-ai-1) + + qt n+1-i-(ai+1-ai-1) + ).

Now let PM(K 2n

) denote the set of perfect matchings of the complete graph K 2n on 2n vertices. By definition, an element M ∈ PM(K 2n ) is a set partition of {1, 2, . . . , 2n} into n blocks of size 2. There is a bijection f : P n → PM(K 2n ) that can be defined recursively as follows. For n = 1, f ((2)) = {{1, 2}}. Given n > 1 and (a 1 , . . . , a n ) ∈ P n , recursively compute M = f (a 2 , . . . , a n ) ∈ PM(K 2n-2 ). Relabel the perfect matching M to use the vertex set {1, 2, . . . , 2n} ∼ {1, a 1 }, and add the edge {1, a 1 } to obtain the perfect matching M = f (a 1 , . . . , a n ). We can use this bijection to change the indexing set for the summation in 7.1 from P n to PM(K 2n ). We thereby see that R (2 n+1 ),a can be written in the form

R (2 n+1 ),a = [n]! t M ∈PM(K2n) [2 n ] M,a ,
where [2 n ] M,a denotes a q, t-analogue of 2 n that depends on the matching M and the integer a. In particular, we have such an expression for F (2 n ) = R (2 n+1 ),2 . This yields a q, t-analogue of the enumeration formula | PM(K 2n )| = (2n)! n!2 n . It is also natural to incorporate a into the matching M by summing over perfect matchings on 2n + 2 vertices that contain the edge {1, a}. This viewpoint produces a formula of the form We calculate (a 0 , a 1 , a 2 , a 3 ) = f -1 (M ) = (6, 3, 4, 2). Referring to 7.1, we see that [2 3 ] M = (t 2 + qt 3 )(1 + q)(t + qt).

Future Work

The computations in [START_REF] Niese | Combinatorial properties of the Hilbert series of Macdonald polynomials[END_REF] suggest that the recursions considered here may extend to polynomials F µ indexed by partitions µ with more than two columns. In particular, the case of a three-column rectangle appears to be tractable, although the required combinatorial manipulations become substantially more involved compared to two-column rectangles. These extensions of the current work, which are treated in the latter part of [START_REF] Niese | Combinatorial properties of the Hilbert series of Macdonald polynomials[END_REF], will be the subject of future papers.

Example 2. 5 ,

 5 For w = 52341 ∈ S 5 , inv(w) = 7, Des(w) = {1, 4}, maj(w) = 5, Asc(w) = {2, 3}, and comaj(w) = 5. Definition 2.6 For a standard filling T of µ ∈ Par(n), we define a triple to be three cells in T with entries a, b, c, arranged as shown here: a b c where a is directly above c, and b is in the same row as a and to the right of a. If the cells containing a and b are in the lowest row, take c = ∞. This triple is an inversion triple of T iff a < c < b or c < b < a or b < a < c. We define inv µ (T ) = number of inversion triples of T. Definition 2.7 For a standard filling T of µ ∈ Par(n), the µ-major index of T is maj µ (T ) = sum of the major indices of the column words of T. Definition 2.8 For a partition µ = (µ 1 , µ 2 , ..., µ k ) ∈ Par(n), define n(µ) = k i=1 (i -1)µ i . Example 2.9 For the filling T of µ = (3, 3, 2, 1) given by maj µ (T ) = maj(6217) + maj(534) + maj(89) = 3 + 1 + 0 = 4, n(µ) = 10, and inv µ (T ) = 3 since the inversion triples are 4 < 7 < ∞, 1 < 7 < 8, and 3 < 4 < 8.

Definition 5. 1

 1 Given µ ∈ Par(n) and T ∈ F µ , define the cyclic shift of T , denoted cyc(T ), by replacing each entry c in T by (c + 1) mod n. Here we use the convention that a mod n ∈ {1, 2, . . . , n}.Lemma 5.2 For all µ ∈ Par(n), cyc n = cyc • cyc • • • • • cyc = idFµ . Proof: Let T ∈ F µ . Each entry c ∈ T will be replaced by the entry (c + n) mod n = c in cyc n (T ). Thus cyc n (T ) = T . 2 Proposition 5.3 Let µ ∈ Par(n). For T ∈ F µ , where n is not in the bottom row, (a) comaj µ (cyc(T )) = comaj µ (T ) + 1; (b) maj µ (cyc(T )) = maj µ (T ) -1;

Example 5. 4

 4 For µ = (3, 3, 2) and n = 8, : inv µ (T ) = 3; inv µ (cyc(T )) = 3; comaj µ (T ) = 4; comaj µ (cyc(T )) = 5; maj µ (T ) = 3; maj µ (cyc(T )) = 2. Lemma 5.5 Given µ ∈ Par(n) and i ∈ N + with µ i = µ i+1 , s i • cyc = cyc •s i . Proof: Since s i only modifies two adjacent columns in the partition, we are reduced to considering T ∈ F (2 n ) . We argue by induction on n. If 2n is not in the bottom row of T , then, since cyc preserves both the number and location of inversion triples, (s 1 • cyc)(T ) = (cyc •s 1 )(T ) follows by the recursive definition of s 1 and induction. If 2n is in the bottom row of T , we can assume the bottom row is increasing by 3.2 (a). Then a = a + 1, c = c + 1, and d = d + 1. If c < a < d or d < a < c, then s 1 (T ) = of the fillings above the bottom 2 rows agree by induction. Otherwise,

2.

  ExampleThen comaj (2 4 ) (T ) = 5, comaj (2 4 ) (S) = 2, and inv (2 4 ) (T ) = inv (2 4 ) (S) = 2.

Example 6. 3

 3 For a = 3 and T ∈ F (2 3 ) given by

Example 6. 9

 9 For n = 4, a = 4, and b = 3, consider

Fig. 2 :

 2 Fig. 2: The elements of X3 and Y3 generated by U .

P

  n = {2, 3, . . . , 2n} × {2, 3, . . . , 2n -2} × • • • × {2, 3, 4} × {2}.Recall from 6.10 the recursionR (2 n+1 ),a = [n] t 2n b=2 R (2 n ),b (t (a-b-1) + + qt n-(b+1-a) + ), R(2),2 = 1.

R ( 2

 2 n+1 ),a0 = [n]! t M ∈PM(K2n+2): {1,a0}∈M [2 n ] M .Example 7.2 Suppose n = 3, a 0 = 6, andM = {{1, 6}, {2, 4}, {3, 8}, {5, 7}}.

Proof: Note A 2 is a bijection from F (2 n ) onto F (2 n+1 ),2 . By 6.4, for U ∈ F (2 n ) ,

2

Using the recursion 6.10 and induction on n, we see that R (2 n ),a (q, t) is divisible by [n -1]! t for 2 ≤ a ≤ 2n. Then 6.11 shows that F (2 n ) (q, t) is indeed divisible by [n]! t . This gives the promised combinatorial proof of Theorem 1.1(b) in the case of two-column rectangles.

Recursion for Two Unequal Columns

Next we discuss a recursion valid for shapes µ with two unequal columns.

T has bottom row 1 a }, and define

To analyze R (1 m 2 n ),a , we need a definition and proposition analogous to 6.2 and 6.4 for two equal columns. Definition 6.13 For m ≥ 1, n ≥ 0, T ∈ F (1 m 2 n ) and 2 ≤ a ≤ m + 2n + 2, we define the a-augmentation of T to be the filling A a (T ) ∈ F (1 m 2 n+1 ),a which is obtained by first relabeling the entries of T as follows: c ∈ T is replaced by c + 1 if c < a -1 and by c + 2 if c ≥ a -1; and then placing the relabeled filling over the new bottom row 1 a . Proposition 6.14 For all m ≥ 1, n ≥ 1, all a with 2 ≤ a ≤ m + 2n, and all T ∈ F (1 m 2 n-1 ) with bottom row x z ,

Since the columns are not of equal height, the inversion flip is not available to sort. Instead, we use the cyclic shift and careful accounting to obtain an increasing bottom row. Proposition 6.15 Let m ≥ 1, n ≥ 0 and T ∈ F (1 m 2 n ) , where T has bottom row x z for some x > z. Then cyc m+2n-x+1 (T ) will have bottom row 1 b where

Proof: Let T ∈ F (1 m 2 n ) have bottom row x z with x > z. By 5.3,