Algebraic Techniques In Combinatorics

Algebra plays an important role in combinatorics. In enumerative combinatorics, we need the theory of group [10,29], the theory of ring [7,27], the theory of algebra [30] and so on. In graph theory, we have the algebraic graph theory [8] which involving spectrum, chromatic polynomial and so on. In design theory and coding theory, we need finite geometry and Hadamard matrices [19,20,24]. There are much more examples in various branches of combinatorics. In this thesis, we discuss two combinatorial problems by algebraic techniques.In part I, we consider the problems about restricted sums of congruence classes.The original problem was proposed by Erdos and Heilbronn (cf. [14] and [18]) in 1964. They conjectured that for each nonempty subset A of Z_p there are at least min{p,2|A| — 3} residue classes mod p that can be written as the sum of two distinct elements of A. This had been open for thirty years until Dias da Silva and Hamidoune [12] proved the result for n-fold sums in 1994, with the help of the representation theory of symmetric groups. In 1995 and 1996, N. Alon, Nathanson and I.Z. Ruzsa [5,6] invented a polynomial method to attack similar problems. By this method, the estimating of the lower bound of the number of restricted sums becomes the calculating of one coefficient of a special polynomial. The keys of the method are the proper choosing of the polynomial and the calculating of the special coefficient. The polynomial chosen in [6] can only deal with the case that all the cardinalities of the sets are distinct. Hence, they could not deal with the n-fold sums case directly.Noting the above draw back, we generalize the polynomial method and chose a new polynomial. Since the coefficient of the new polynomial is too complicate to calculate directly, we introduce a linear operator and study the algebraic properties of it. Based on those properties and Dyson's conjecture [13], we get the coefficient, and hence, the lower bound of the number of restricted sums. The new estimation covers the result of Dias da Silva and Hamidoune. More important, it gives the best lower bound of the number of sums with more than one restrictions. There are also some interesting results obtained as corollaries.In part II, we consider the recurrence formula of double hypergeometric terms.Hypergeometric terms have wide applications in mathematics and physics [15,16,32]. There are many famous identities involving those functions, such as Gauss's identity [2] and Dixon's identity [36]. There are also many beautiful proofs for them. While, it is more amazing that a lot of them can be proved automatically. Since 1990, Zeilberger and Wilf developed a series of elegant methods to prove automatically the identities involving (q-) hypergeometric terms [37-40,42]. The basic idea is to find the recurrence formula of the function on each side of the identity and to prove that they are equivalent. Thus, the identity is proved by checking the initial values. Clearly, a basic hypothesis of this method is that the functions should be determined by finite initial values, which are calledholonomic functions. The accurate definition is given by the language of rings [9,42], which is very abstract and is hard to verify. While, Zeilberger and Wilf [39] showed that proper hypergeometric terms are holonomic and conjectured that the inverse assertion also holds.By generalizing the Gosper's algorithm, we introduce the representation of rational functions and hence the standard representation of double hypergeometric terms. Using the two basic recurrence formulae that double hypergeometric terms satisfy, we get the general form of such representation. Based on it, we derive that there exists a Mree recurrence formula for a double hypergeometric term if and only if it is proper. Consequently, holonomic double hypergeometric terms are all proper, which modifies the identities that can be proved automatically.