The Number of Edge Colorings with no Monochromatic Cliques

Let F(n,r,k) denote the maximum possible number of distinctedge-colorings of a simple graph on n vertices with r colorswhich contain no monochromatic copy of K_k. It is shown thatfor every fixed k and all n>n₀(k), and , where t_k–1(n)is the maximum possible number of edges of a graph on n verticeswith no K_k (determined by Turán's theorem). The caser=2 settles an old conjecture of Erds and Rothschild, whichwas also independently raised later by Yuster. On the otherhand, for every fixed r>3 and k>2, the function F(n,r,k)is exponentially bigger than . The proofs are based on Szemerédi's regularity lemmatogether with some additional tools in extremal graph theory,and provide one of the rare examples of a precise result provedby applying this lemma.     

Partial Difference Triples

It is known that a strongly regular semi-Cayley graph (with respect to a group G) corresponds to a triple of subsets (C, D, D) of G. Such a triple (C, D, D) is called a partial difference triple. First, we study the case when D D is contained in a proper normal subgroup of G. We basically determine all possible partial difference triples in this case. In fact, when nor 25, all partial difference triples come from a certain family of partial difference triples. Second, we investigate partial difference triples over cyclic group. We find a few nontrivial examples of strongly regular semi-Cayley graphs when |G| is even. This gives a negative answer to a problem raised by de Resmini and Jungnickel. Furthermore, we determine all possible parameters when G is cyclic. Last, as an application of the theory of partial difference triples, we prove some results concerned with strongly regular Cayley graphs.     

The Schur algorithm and coefficient characterizations for generalized Schur functions

In this paper we analyze the existence of a Schur algorithm and obtain coefficient characterizations for the functions in a generalized Schur class. An application to an interpolation problem of Carathéodory type raised by M.G. Krein and H. Langer is indicated.

     

Triples of almost primes

The k-tuple conjecture of Hardy and Little wood predicts that there are infinitely many primes p such that p+2 and p+6 are primes simultaneously.In this paper,we prove that there are infinitely many primes p such that Ω(p+2)≤3 and Ω(p+6)≤6,where Ω(n) denotes the total number of prime divisors of an integer n.We also prove a better conditional result,with the above Ω(p+6)≤6 replaced by Ω(p+6)≤3,under the Elliott-Halberstam conjecture.     

Schur dynamics of the Schur processes

We construct discrete time Markov chains that preserve the class of Schur processes on partitions and signatures.One application is a simple exact sampling algorithm for qvolume-distributed skew plane partitions with an arbitrary back wall. Another application is a construction of Markov chains on infinite Gelfand–Tsetlin schemes that represent deterministic flows on the space of extreme characters of the infinite-dimensional unitary group.     

Localization and Codensity Triples

u: A→H(I), I ε J], and let x: Q→S be the equalizer of ηS and Sη.     

Triples of long root subgroups

Let G = G(Φ, K) be a Chevalley group over a field K of characteristic ≠ 2. In the present paper, we classify the subgroups of G generated by triples of long root subgroups, two of which are opposite, up to conjugacy. For finite fields, this result is contained in papers by B. Cooperstein on the geometry of root subgroups, whereas for SL (n, K) it is proved in a paper by L. Di Martino and the first-named author. All interesting items of our list appear in deep geometric results on abstract root subgroups and quadratic actions by F. Timmesfeld and A. Steinbach, and also by E. Bashkirov. However, for applications to the groups of type E _l, we need a detailed justification of this list, which we could not extract from the published papers. That is why in the present paper, we produce a direct elementary proof based on the reduction to D ₄, where the question is settled by straightforward matrix calculations. Bibliography: 73 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 343, 2007, pp. 54–83.     

Hamiltonian Cycles of Adjacent Triples

A construction is given for ordering triples chosen from an ordered set of elements, so that each triple agrees with each neighbor in two of its members and has third member that is a neighbor of its neighbor's third member. Neighbors here are adjacent in order, and also the first is neighbor to the last among both elements and triples. Joichi and White have given a different construction.     

Equality of Schur and Skew Schur Functions

We determine the precise conditions under which any skew Schur function is equal to a Schur function over both infinitely and finitely many variables. Received May 29, 2004     

The Flagged Double Schur Function

The double Schur function is a natural generalization of the factorial Schur function introduced by Biedenharn and Louck. It also arises as the symmetric double Schubert polynomial corresponding to a class of permutations called Grassmannian permutations introduced by A. Lascoux. We present a lattice path interpretation of the double Schur function based on a flagged determinantal definition, which readily leads to a tableau interpretation similar to the original tableau definition of the factorial Schur function. The main result of this paper is a combinatorial treatment of the flagged double Schur function in terms of the lattice path interpretations of divided difference operators. Finally, we find lattice path representations of formulas for the symplectic and orthogonal characters for sp(2n) and so(2n + 1) based on the tableau representations due to King and El-Shakaway, and Sundaram. Based on the lattice path interpretations, we obtain flagged determinantal formulas for these characters.     

Multiplicity Free Schur, Skew Schur, and Quasisymmetric Schur Functions

In this paper we classify all Schur functions and skew Schur functions that are multiplicity free when expanded in the basis of fundamental quasisymmetric functions, termed F-multiplicity free. Combinatorially, this is equivalent to classifying all skew shapes whose standard Young tableaux have distinct descent sets. We then generalize our setting, and classify all F-multiplicity free quasisymmetric Schur functions with one or two terms in the expansion, or one or two parts in the indexing composition. This identifies composition shapes such that all standard composition tableaux of that shape have distinct descent sets. We conclude by providing such a classification for quasisymmetric Schur function families, giving a classification of Schur functions that are in some sense almost F-multiplicity free.