Combinatorial Aspects of Flashcard Games

We study a family of discrete dynamical processes introduced by Novikoff, Kleinberg, and Strogatz that we call flashcard games. We prove a number of results on the evolution of these games, and in particular, we settle a conjecture of NKS on the frequency with which a given card appears. We introduce a number of generalizations and variations that we believe are of interest, and we provide a large number of open questions and problems.     

Combinatorial Aspects of the K-Theory of Grassmannians

In this paper we study Grothendieck polynomials indexed by Grassmannian permutations, which are representatives for the classes corresponding to the structure sheaves of Schubert varieties in the K-theory of Grassmannians. These Grothendieck polynomials are nonhomogeneous symmetric polynomials whose lowest homogeneous component is a Schur polynomial. Our treatment, which is closely related to the theory of Schur functions, gives new information about these polynomials. Our main results are concerned with the transition matrices between Grothendieck polynomials indexed by Grassmannian permutations and Schur polynomials on the one hand and a Pieri formula for these Grothendieck polynomials on the other.     

Some Combinatorial Aspects of Constructing Bipartite-Graph Codes

We propose geometrical methods for constructing square 01-matrices with the same number n of units in every row and column, and such that any two rows of the matrix contain at most one unit in common. These matrices are equivalent to n-regular bipartite graphs without 4-cycles, and therefore can be used for the construction of efficient bipartite-graph codes such that both the classes of its vertices are associated with local constraints. We significantly extend the region of parameters m, n for which there exist an n-regular bipartite graph with 2m vertices and without 4-cycles. In that way we essentially increase the region of lengths and rates of the corresponding bipartite-graph codes. Many new matrices are either circulant or consist of circulant submatrices: this provides code parity-check matrices consisting of circulant submatrices, and hence quasi-cyclic bipartite-graph codes with simple implementation.     

组合数集的毕达哥斯定理

本文得到两个组合数集的毕达哥斯定理的推广。(ⅰ )当n为奇数时∑[(n+ 3 ) / 2 ]t=0n +3-tt2 - ∑[(n+ 1) / 2 ]t=0n +1-tt2 2 +2 ∑[n/ 2 ]t=0n -tt · ∑[(n+ 4 ) / 2 ]t=0n +4-tt2 +4∑[(n+ 2 ) / 2 ]t=0n +2 -tt2= ∑[(n+ 1) /2 ]t=0n+ 1 -tt2 + ∑[(n+ 3) /2 ]t=0n+ 3-tt2 2 。(ⅱ )当n为偶数时∑[(n+ 4 ) / 2 ]t=0n+4-tt2 - ∑[n/ 2 ]t=0n-tt2 2 +2 ∑[(n+ 1) / 2 ]t=0n+1-tt · ∑[(n+ 3 ) / 2 ]t=0n+3-tt2 +4∑[(n+ 2 ) / 2 ]t=0n+2 -tt2= ∑[n/2 ]t=0n -tt2 + ∑[(n+ 4) /2 ]t=0n + 4 -tt2 2 。     

Some Combinatorial Aspects of Reduced Words in Finite Coxeter Groups

We analyze the structure of reduced expressions in the Coxeter groups , and . Several special classes of elements are singled out for their connections with symmetric functions or the theory of -partitions. Membership in these special classes is characterized in a variety of ways, including forbidden patterns, forbidden subwords, and by the form of canonically chosen reduced words.

     

Combinatorial Aspects of Total Weight Orders over Monomials of Fixed Degree

Among all the restrictions of weight orders to the subsets of monomials with a fixed degree, we consider those that yield a total order. Furthermore, we assume that each weight vector consists of an increasing tuple of weights. Every restriction, which is shown to be achieved by some monomial order, is interpreted as a suitable linearization of the poset arising by the intersection of all the weight orders. In the case of three variables, an enumeration is provided. For a higher number of variables, we show a necessary condition for obtaining such restrictions, using deducibility rules applied to homogeneous inequalities. The logarithmic version of this approach is deeply related to classical results of Farkas type, on systems of linear inequalities. Finally, we analyze the linearizations determined by sequences of prime numbers and provide some connections with topics in arithmetic.     

Transitive Factorizations in the Symmetric Group, and Combinatorial Aspects of Singularity Theory

We consider the determination of the number c_k(α) of ordered factorizations of an arbitrary permutation on n symbols, with cycle distribution α, intok -cycles such that the factorizations have minimal length and the group generated by the factors acts transitively on then symbols. The case k =  2 corresponds to the celebrated result of Hurwitz on the number of topologically distinct holomorphic functions on the 2-sphere that preserve a given number of elementary branch point singularities. In this case the monodromy group is the full symmetric group. For k =  3, the monodromy group is the alternating group, and this is another case that, in principle, is of considerable interest. We conjecture an explicit form, for arbitrary k, for the generating series for c_k(α), and prove that it holds for factorizations of permutations with one, two and three cycles (so α is a partition with at most three parts). Our approach is to determine a differential equation for the generating series from a combinatorial analysis of the creation and annihilation of cycles in products under the minimality condition.     

Aspects of Number Theory in Terms of Potential Theory

We develop the Potential Theory on the set N^* of all natural numbers 2 associated with the kernel V (resp. V ^*) given by

Splitting the shadow

We derive formulae for the theta series of the two translates of the even sublattice L₀ of an odd unimodular lattice L that constitute the shadow of L. The proof rests on special evaluations of the Jacobi theta series attached to L and to a certain vector. We produce an analogous theorem for codes. Additionally, we construct non-linear formally self-dual codes and relate them to lattices.     

Splitting the Pasch axiom

On the basis of the theory ^– of Pasch-free 2-dimensional geometry, Pasch's axiom is shown to be equivalent to the conjunction of the following two axioms: In any right triangle the hypotenuse is greater than the leg and If AOB is right, B lies between O and C, and D is the footpoint of the perpendicular from B to AC, then the segment OA is greater than the segment BD. This represents an attempt to split the Pasch axiom with respect to ^–. Only the question whether the second of the above two axioms is really weaker than Pasch's axiom, remains open.     

Splitting intervals

Given an interval we choose a point in the interval and one of the two subintervals thus obtained in a symmetric random manner. The process is repeated ad infinitum. We study the limiting distribution of the midpoint of the interval.     

Combinatorial pseudo-triangulations

We prove that a planar graph is generically rigid in the plane if and only if it can be embedded as a pseudo-triangulation. This generalizes the main result of [Haas et al. Planar minimally rigid graphs and pseudo-triangulations, Comput. Geom. 31(1–2) (2005) 31–61] which treats the minimally generically rigid case.The proof uses the concept of combinatorial pseudo-triangulation, CPT, in the plane and has two main steps: showing that a certain “generalized Laman property” is a necessary and sufficient condition for a CPT to be “stretchable”, and showing that all generically rigid plane graphs admit a CPT assignment with that property.Additionally, we propose the study of CPTs on closed surfaces.     

组合恒等式

本文利用函数１ｆ（ｘ）展开式定理,导出一批新的组合恒等式．