Schur functions,Good's identity,and hypergeometric series well poised in SU(n)

A simple direct proof is given of a fundamental identity involving Schur functions which contains as special cases the identity responsible for Good's proof of the Dyson conjecture and the summation theorem of Biedenharn and Louck that appears frequently in dealing with the explicit matrix elements which arise in the unitary groups. By using the Weyl character formula, a general identity is obtained which implies our result involving Schur functions when a root system of type A_{n ? 1} is considered. As a further application of our general identity, explicit analogs of Good's identity are given, corresponding to the root systems of types B_n, C_n, and D_n. In addition, methods to obtain q-analogs of all of these results are briefly described.     

A Short Proof of a Theorem of Reid and Parker on Tournaments

In [3], Reid and Parker proved the following interesting theorem: If k≥5 and n ≥ 7.2_k-4, then every tournament T_n of order n contains a TT_k, i.e. a transitive subtournament of order k, improving a well known result of Stearns and disproving a conjecture of Erdös and Moser. The original proof was long and fragmented into many cases. In this paper we give a short and structural proof.     

Variations on a Result of Bressoud

The well-known Rogers-Ramanujan identities have been a rich source of mathematical study over the last fifty years. In particular, Gordon’s generalization in the early 1960s led to additional work by Andrews and Bressoud in subsequent years. Unfortunately, these results lacked a certain amount of uniformity in terms of combinatorial interpretation. In this work, we provide a single combinatorial interpretation of the series sides of these generating function results by using the concept of cluster parities. This unifies the aforementioned results of Andrews and Bressoud and also allows for a strikingly broader family of q-series results to be obtained. We close the paper by proving congruences for a “degenerate case” of Bressoud’s theorem.     

Median orders of tournaments: A tool for the second neighborhood problem and Sumner's conjecture

We give a short constructive proof of a theorem of Fisher: every tournament contains a vertex whose second outneighborhood is as large as its first outneighborhood. Moreover, we exhibit two such vertices provided that the tournament has no dominated vertex. The proof makes use of median orders. A second application of median orders is that every tournament of order 2n − 2 contains every arborescence of order n > 1. This is a particular case of Sumner's conjecture: every tournament of order 2n − 2 contains every oriented tree of order n > 1. Using our method, we prove that every tournament of order (7n − 5)/2 contains every oriented tree of order n. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 244–256, 2000     

Discrete Concavity and Zeros of Polynomials

Murota et al. have recently developed a theory of discrete convex analysis as a framework to solve combinatorial optimization problems using ideas from continuous optimization. This theory concerns M-convex functions on jump systems. We introduce here a family of M-concave functions arising naturally from polynomials (over the field of Puiseux series) with prescribed non-vanishing properties. We also provide a short proof of Speyer's “hive theorem” which he used to give a new proof of Horn's conjecture on eigenvalues of sums of Hermitian matrices. Due to limited space a more coherent treatment and proofs will appear elsewhere.     

Plane partitions IV: A conjecture of Mills—Robbins—Rumsey

In this paper we consider a problem posed by W Mills D Robbins and H Rumsey for a certain plane partition generating functionZ _n (x, m) The special caseZ _n (1,m) is the generating function that arose in the weak Macdonald conjecture Mills—Robbins—Rumsey conjectured thatZ _n (2,m) also possesses a nice finite product representation Their conjecture is proved as Theorem 1 The method of proof resembles that of the evaluation ofZ _n (1,m) given previously Many results for the₃ F ₂ hypergeometric function are required including Whipple's theorem, the Pfaff-Saalschutz summation and contiguous relations In passing we note that our Lemma 2 provides a new and simpler representation ofZ _n (2,m) as a determinant $$Z_n (2,m) = \det \left( {\delta _{ij} + \sum\limits_{t = 0}^1 {\left( {\mathop {m + j + t}\limits_t } \right)} \left( {\mathop {m + t}\limits_{m + t} } \right)} \right)_{0 \leqq ij \leqq n - 1} $$ Conceivably this new representation may provide new interpretations of the combinatorial significance ofZ _n (2,m) In the final analysis, one would like a combinatorial explanation ofZ _n (2,m) that would provide an algorithmic proof of the Mills Robbins—Rumsey conjecture     

On the sign-imbalance of partition shapes

Let the sign of a standard Young tableau be the sign of the permutation you get by reading it row by row from left to right, like a book. A conjecture by Richard Stanley says that the sum of the signs of all SYTs with n squares is 2^⌊n/2⌋. We present a stronger theorem with a purely combinatorial proof using the Robinson-Schensted correspondence and a new concept called chess tableaux.We also prove a sharpening of another conjecture by Stanley concerning weighted sums of squares of sign-imbalances. The proof is built on a remarkably simple relation between the sign of a permutation and the signs of its RS-corresponding tableaux.     

Plane partitions IV: A conjecture of Mills—Robbins—Rumsey

In this paper we consider a problem posed by W Mills D Robbins and H Rumsey for a certain plane partition generating functionZ _n (x, m) The special caseZ _n (1,m) is the generating function that arose in the weak Macdonald conjecture Mills—Robbins—Rumsey conjectured thatZ _n (2,m) also possesses a nice finite product representation Their conjecture is proved as Theorem 1 The method of proof resembles that of the evaluation ofZ _n (1,m) given previously Many results for the₃ F ₂ hypergeometric function are required including Whipple's theorem, the Pfaff-Saalschutz summation and contiguous relations In passing we note that our Lemma 2 provides a new and simpler representation ofZ _n (2,m) as a determinant $$Z_n (2,m) = \det \left( {\delta _{ij} + \sum\limits_{i = 0}^l {\left( {\begin{array}{*{20}c} {m + j + t} \\ t \\ \end{array} } \right)\left( {\begin{array}{*{20}c} {m + i} \\ {m + t} \\ \end{array} } \right)} } \right)_{0 \leqq ij \leqq n - 1} $$ Conceivably this new representation may provide new interpretations of the combinatorial significance ofZ _n (2,m) In the final analysis, one would like a combinatorial explanation ofZ _n (2,m) that would provide an algorithmic proof of the Mills Robbins—Rumsey conjecture     

Representation of ap-harmonic function near a critical point in the plane

A representation theorem is given for ap-harmonic function φ(1<p<∞) in the plane, near a zeroz _o of grad φ. The proof uses “stream functions” and the hodograph transformation. The stream function of ap-harmonic function isp′-harmonic, where \(\frac{1}{p} + \frac{1}{{p'}} = 1\) . In principle, all properties of φ nearz _o can be found from the representation. Some consequences are derived here, e.g. the optimal Hölder continuity of grad φ.     

Generalized Kneser coloring theorems with combinatorial proofs

The Kneser conjecture (1955) was proved by Lovász (1978) using the Borsuk-Ulam theorem; all subsequent proofs, extensions and generalizations also relied on Algebraic Topology results, namely the Borsuk-Ulam theorem and its extensions. Only in 2000, Matoušek provided the first combinatorial proof of the Kneser conjecture. Here we provide a hypergraph coloring theorem, with a combinatorial proof, which has as special cases the Kneser conjecture as well as its extensions and generalization by (hyper)graph coloring theorems of Dol’nikov, Alon-Frankl-Lovász, Sarkaria, and Kriz. We also give a combinatorial proof of Schrijver’s theorem. Oblatum 17-IV-2001 & 12-IX-2001?Published online: 19 November 2001 An erratum to this article is available at .     

Spanning 2-strong tournaments in 3-strong semicomplete digraphs

We prove that every 3-strong semicomplete digraph on at least 5 vertices contains a spanning 2-strong tournament. Our proof is constructive and implies a polynomial algorithm for finding a spanning 2-strong tournament in a given 3-strong semicomplete digraph. We also show that there are infinitely many (2k−2)-strong semicomplete digraphs which contain no spanning k-strong tournament and conjecture that every(2k−1)-strong semicomplete digraph which is not the complete digraph on 2k vertices contains a spanning k-strong tournament.     

r-Qsym is free over Sym

Our main result is a proof of the Florent Hivert conjecture [F. Hivert, Local action of the symmetric group and generalizations of quasi-symmetric functions, in preparation] that the algebras of r-Quasi-Symmetric polynomials in x₁,x₂,…,xn are free modules over the ring of Symmetric polynomials. The proof rests on a theorem that reduces a wide variety of freeness results to the establishment of a single dimension bound. We are thus able to derive the Etingof-Ginzburg [P. Etingof, V. Ginzburg, On m-quasi-invariants of a Coxeter group, Mosc. Math. J. 2 (2002) 555-566] Theorem on m-Quasi-Invariants and our r-Quasi-Symmetric result as special cases of a single general principle. Another byproduct of the present treatment is a remarkably simple new proof of the freeness theorem for 1-Quasi-Symmetric polynomials given in [A.M. Garsia, N. Wallach, Qsym over Sym is free, J. Combin. Theory Ser. A 104 (2) (2003) 217-263].     

A Conjecture on Exceptional Orthogonal Polynomials

Exceptional orthogonal polynomial systems (X-OPSs) arise as eigenfunctions of Sturm–Liouville problems, but without the assumption that an eigenpolynomial of every degree is present. In this sense, they generalize the classical families of Hermite, Laguerre, and Jacobi, and include as a special case the family of CPRS orthogonal polynomials introduced by Cariñena et al. (J. Phys. A 41:085301, 2008). We formulate the following conjecture: every exceptional orthogonal polynomial system is related to a classical system by a Darboux–Crum transformation. We give a proof of this conjecture for codimension 2 exceptional orthogonal polynomials (X₂-OPs). As a by-product of this analysis, we prove a Bochner-type theorem classifying all possible X₂-OPSs. The classification includes all cases known to date plus some new examples of X₂-Laguerre and X₂-Jacobi polynomials.     

On the KŁR conjecture in random graphs

The K?R conjecture of Kohayakawa, ?uczak, and Rödl is a statement that allows one to prove that asymptotically almost surely all subgraphs of the random graph G _n,p , for sufficiently large p:= p(n), satisfy an embedding lemma which complements the sparse regularity lemma of Kohayakawa and Rödl. We prove a variant of this conjecture which is sufficient for most known applications to random graphs. In particular, our result implies a number of recent probabilistic versions, due to Conlon, Gowers, and Schacht, of classical extremal combinatorial theorems. We also discuss several further applications.     

Weak Leopoldt's conjecture for Hecke characters of imaginary quadratic fields

We give a proof of the weak Leopoldt's conjecture à la Perrin-Riou, under some technical condition, for the p-adic realizations of the motive associated to Hecke characters over an imaginary quadratic field K of class number 1, where p is a prime >3 and where the CM elliptic curve associated to the Hecke character has good reduction at the primes above p in K. This proof makes use of the 2-variable Iwasawa main conjecture proved by Rubin. Thus we prove the Jannsen conjecture for the above p-adic realizations for almost all Tate twists.     

Analog of the Riesz theorem and the basis property in L p of a system of root functions of a differential operator: I

An ordinary differential operator of arbitrary order is considered. We find necessary conditions for the Riesz property of systems of normalized root functions, prove an analog of the Riesz theorem, and use it to obtain sufficient conditions for the basis property of a system of root functions of this operator in L _p .     

On a problem of G. Hahn about coloured hamiltonian paths in K2t

We prove a theorem showing that for every integer p (p?2) there is a good minimal coloring of the edges of K_2^p such that every hamiltonian path in K_2^p uses at least one colour twice. This gives a counter-example to a conjecture of Hahn [2].     

On the multigraded Hilbert and Poincaré-Betti series and the Golod property of monomial rings

In this paper we study the multigraded Hilbert and Poincaré-Betti series of A=S/a, where S is the ring of polynomials in n indeterminates divided by the monomial ideal a. There is a conjecture about the multigraded Poincaré-Betti series by Charalambous and Reeves which they proved in the case where the Taylor resolution is minimal. We introduce a conjecture about the minimal A-free resolution of the residue class field and show that this conjecture implies the conjecture of Charalambous and Reeves and, in addition, gives a formula for the Hilbert series. Using Algebraic Discrete Morse theory, we prove that the homology of the Koszul complex of A with respect to x₁,…,x_n is isomorphic to a graded commutative ring of polynomials over certain sets in the Taylor resolution divided by an ideal r of relations. This leads to a proof of our conjecture for some classes of algebras A. We also give an approach for the proof of our conjecture via Algebraic Discrete Morse theory in the general case.The conjecture implies that A is Golod if and only if the product (i.e. the first Massey operation) on the Koszul homology is trivial. Under the assumption of the conjecture we finally prove that a very simple purely combinatorial condition on the minimal monomial generating system of a implies Golodness for A.     

G ∞-Formality Theorem in Terms of Graphs and Associated Chevalley–Eilenberg–Harrison Cohomology #

In 1997, M. Kontsevich proved the L _∞-formality conjecture (which implies the existence of star-products for any Poisson manifold) using graphs. A year later, D. Tamarkin gave another proof of a more general conjecture (for G _∞-structures) using operads and cohomological methods. In this article, we show how Tamarkin's construction can be written using graphs. For that, we introduce a generalization of Kontsevich graphs on which we define a “Chevalley–Eilenberg–Harrison” complex. We show that this complex on graphs is related to the “Chevalley–Eilenberg–Harrison” complex for maps on polyvector fields, which is trivial and give Tamarkin's formality theorem as a consequence. This formality reduces to an L _∞-formality.     

Non-trivialité des points de Heegner

We give here a second proof of Mazur's conjecture on higher Heegner points, using a proven case of the André–Oort conjecture as a substitute for the main ingredient of our first proof [1], a theorem of M. Ratner. To cite this article: C. Cornut, C. R. Acad. Sci. Paris, Ser. I 334 (2002) 1039–1042.