2-Binary trees: Bijections and related issues

A 2-binary tree is a binary rooted tree whose root is colored black and the other vertices are either black or white. We present several bijections concerning different types of 2-binary trees as well as other combinatorial structures such as ternary trees, non-crossing trees, Schröder paths, Motzkin paths and Dyck paths. We also obtain a number of enumeration results with respect to certain statistics.     

The normalized matching property from the generalized Macaulay theorem

IfA is a family ofk-element subsets of a finite setM having elements of several different types (i.e., amultiset) and A is the set of all (k–1)-element subsets ofM obtainable by removing a single element ofM from a single member ofA, then, according to the well known normalized matching condition, the density ofA among thek-element subsets ofM never exceeds the density of A among the (k–1)-element subsets ofM. We show that this useful fact can be regarded as yet another corollary of the generalized Macaulay theorem.     

The equivalence of certain equidistant binary codes and symmetric bibds

We study equidistant codes of length 4k + 1 having (constant) weight 2k, and (constant) distance 2k between codewords. The maximum number of codewords is 4k; this can be attained if and only ifk = (u ² +u)/2 (for some integeru) and there exists a ((2u ² + 2u + 1,u ², (u ² −u)/2) — SBIBD. Also, one can construct such a code, with 4k − 1 codewords, from a (4k − 1, 2k − 1,k − 1) — SBIBD. Supported, in part by NSERC grants U0217 (D. R. Stinson), A3558 (G. H. J. van Rees).     

On the existence of difference sets in groups of order 96

The correspondence between a (96,20,4) symmetric design having regular automorphism group and a difference set with the same parameters has been used to obtain difference sets in groups of order 96. Starting from eight such symmetric designs constructed by the tactical decomposition method, 55 inequivalent (96,20,4) difference sets are distinguished. Thereby the existence of difference sets in 22 nonabelian groups of order 96 is proved.     

Bounds on the convex label number of trees

A convex labelling of a tree is an assignment of distinct non-negative integer labels to vertices such that wheneverx, y andz are the labels of vertices on a path of length 2 theny≦(x+z)/2. In addition if the tree is rooted, a convex labelling must assign 0 to the root. The convex label number of a treeT is the smallest integerm such thatT has a convex labelling with no label greater thanm. We prove that every rooted tree (and hence every tree) withn vertices has convex label number less than 4n. We also exhibitn-vertex trees with convex label number 4n/3+o(n), andn-vertex rooted trees with convex label number 2n +o(n). The research by M. B. and A. W. was partly supported by NSF grant MCS—8311422.     

Construction of nested balanced block designs, rectangular designs andq-ary codes

Construction of nested balanced incomplete block (BIB) designs, nested balanced ternary designs and rectangular designs from given nested BIB designs and resolvable BIB designs are described. New constructions ofq-ary codes from nested BIB designs and balanced bipartite weighing designs are also given.     

Pattern Avoidance in Multiset Permutations: Bijective Proof

It is well-known that the number of permutations of n letters that avoid a pattern τ of 3 letters is independent of τ. In this note we provide bijective proof that the same result holds for permutations of a multiset. Received August 16, 2006     

The convex hull of antichains in posets

Extending a result of Kleitman et al. [7] it is shown that the vertices on the convex hull off-vectors of all antichains of a poset come from antichains which are the unions of full orbits of the automorphism group.     

The minimum independence number for designs

Fort=2,3 andk2t–1 we prove the existence oft–(n,k,) designs with independence numberC _,k n ^{(k–t)/(k–1)} (ln n) ^1/(k–1) . This is, up to the constant factor, the best possible.Some other related results are considered.Supported by NSF Grant DMS-9011850     

Card shuffling and a transformation on S n

Summary We consider two card shuffling schemes. The first, which has appeared in the literature previously ([G], [RB], [T]), is as follows: start with a deck ofn cards, and pick a random tuplet { 1, 2, , n} ⁿ ; interchange cards 1 andt ₁, then interchange cards 2 andt ₂, etc. The second scheme, which can be viewed as a transformation on the symmetric groupS _n , is given by the restriction of the former shuffling scheme to tuplest which form a permutation of {1, 2,,n}.We determine the bias of each of these shuffling schemes with respect to the sets of transpositions and derangements, and the expected number of fixed points of a permutation generated by each of these shuffling schemes. For the latter scheme we prove combinatorially that the permutation which arises with the highest probability is the identity. The same question is open for the former scheme. We refute a candidate answer suggested by numerical evidence [RB].This work was carried out in part while R.S. was visiting the Institute for Mathematics and its Applications and was partly supported through NSF Grant CCR-8707539.     

On the maximum number of fixed points in automorphisms of prime order of 2-(v,k,1) designs

In this paper, we study 2-(v, k, 1) designs with automorphisms of prime orderp, having the maximum possible number of fixed points. We prove an upper bound on the number of fixed points, and we study the structure of designs in which this bound is met with equality (such a design is called ap-MFP(v, k)). Several characterizations and asymptotic existence results forp-MFP(v, k) are obtained. For (p, k)=(3,3), (5,5), (2,3) and (3,4), necessary and sufficient conditions onv are obtained for the existence of ap-MFP(v, k). Further, for 3≤k≤5 and for any primep≡1 modk(k−1), we establish necessary and sufficient conditions onv for the existence of ap-MFP(v, k).     

2-(<Emphasis Type="Italic">v,k</Emphasis>,1) Designs and PSL (3,<Emphasis Type="Italic">q</Emphasis>) where <Emphasis Type="Italic">q</Emphasis> is ODD

Let G be a block-primitive automorphism group of a 2-(v,k,1) design. If G is isomorphic to PSL (3,q) where q is odd, then G is also point-primitive. Supported by the National Natural Science Foundation of China (10171089).     

Pooling, lattice square, and union jack designs

Simplified pooling designs employ rows, columns, and principal diagonals from square and rectangular plates. The requirement that every two samples be tested together in exactly one pool leads to a novel combinatorial configuration: The union jack design. Existence of union jack designs is settled affirmatively whenever the ordern is a prime andn3 (mod 4).     

Symbolic Moment Calculus I: Foundations and Permutation Pattern Statistics

The old workhorse called linearity of expectation, by which it is often very easy to compute the expectation (alias first moment) of interesting combinatorial quantities, can also be used to compute higher moments, as well as correlations, but then things get very soon too complicated for mere humans. The computer, used as a symbol-cruncher, can go much further (alas, only by a few orders of magnitude). In this article, a methodology for using Computer Algebra Systems to automatically derive higher moments of interesting combinatorial random variables is described, and applied to Pattern Statistics of permutations. This would be hopefully followed by sequels applied to other combinatorial objects like graph-colorings, Boolean functions, and Random Walks. In addition to the intrinsic interest that the actual results might have, it is also hoped that this work will serve as as an illustrative example for conducting reliable mathematical experiments that lead to completely rigorous results, by an Overlapping Stages approach.     

Non-Trivial t-Intersection in the Function Lattice

The function lattice, or generalized Boolean algebra, is the set of ℓ-tuples with the ith coordinate an integer between 0 and a bound n_i. Two ℓ-tuples t-intersect if they have at least t common nonzero coordinates. We prove a Hilton–Milner type theorem for systems of t-intersecting ℓ-tuples.Received September 29, 2004     

Van der waerden and ramsey type games

Let us consider the following 2-player game, calledvan der Waerden game. The players alternately pick previously unpicked integers of the interval {1, 2, ...,N}. The first player wins if he has selected all members of ann-term arithmetic progression. LetW*(n) be the least integerN so that the first player has a winning strategy. By theRamsey game on k-tuples we shall mean a 2-player game where the players alternately pick previously unpicked elements of the completek-uniform hypergraph ofN verticesK _N ^k , and the first player wins if he has selected allk-tuples of ann-set. LetR _k*(n) be the least integerN so that the first player has a winning strategy. We prove (W* (n))¹/n → 2,R ₂*(n)<(2+ε) ⁿ andR _k ^* n<2 ^nk / ^k! fork ≧3.     

Weighted Non-Trivial Multiply Intersecting Families

Let n and r be positive integers. Suppose that a family satisfies F₁∩···∩F_r ≠∅ for all F₁, . . .,F_r ∈ and . We prove that there exists ε=ε(r) >0 such that holds for 1/2≤w≤1/2+ε if r≥13.     

The Doyen-Wilson theorem for kite systems

Necessary and sufficient conditions are given to embed a kite system of order n into a kite system of order m.