Matrices related to the Bell polynomials

In this paper, we study the matrices related to the partial exponential Bell polynomials and those related to the Bell polynomials with respect to Ω. As a result, the factorizations of these matrices are obtained, which give unified approaches to the factorizations of many lower triangular matrices. Moreover, some combinatorial identities are also derived from the corresponding matrix representations.     

Relations between the Clausen and Kazhdan-Lusztig representations of the symmetric group

We use Kazhdan-Lusztig polynomials and subspaces of the polynomial ring C[x_1,1,…,x_n,n] to give a new construction of the Kazhdan-Lusztig representations of S_n. This construction produces exactly the same modules as those which Clausen constructed using a different basis in [M. Clausen, Multivariate polynomials, standard tableaux, and representations of symmetric groups, J. Symbolic Comput. (11), 5-6 (1991) 483-522. Invariant-theoretic algorithms in geometry (Minneapolis, MN, 1987)], and does not employ the Kazhdan-Lusztig preorders. We show that the two resulting matrix representations are related by a unitriangular transition matrix. This provides a C[x_1,1,…,x_n,n]-analog of results due to Garsia and McLarnan, and McDonough and Pallikaros, who related the Kazhdan-Lusztig representations to Young’s natural representations.     

Group divisible designs with block size four and two groups

We give some constructions of new infinite families of group divisible designs, GDD(n,2,4;λ₁,λ₂), including one which uses the existence of Bhaskar Rao designs. We show the necessary conditions are sufficient for 3?n?8. For n=10 there is one missing critical design. If λ₁>λ₂, then the necessary conditions are sufficient for . For each of n=10,15,16,17,18,19, and 20 we indicate a small minimal set of critical designs which, if they exist, would allow construction of all possible designs for that n. The indices of each of these designs are also among those critical indices for every n in the same congruence class mod 12.     

On Bessel integrals for reducible degenerate principal series representations

We discuss generalized Bessel integrals with nondegenerate characters, which are assigned to irreducible submodules of a reducible degenerate principal series representation of Sp(n,R). Then we give sufficient conditions for their vanishings which are based on the signatures of the nondegenerate characters. This consequently suggests a reasonable correspondence between open GLn(R)-orbits in the set of real symmetric matrices of size n and irreducible submodules of the reducible principal series representations.     

Some new results on subset sums

Let n be a large integer and A be a subset of [n]={1,…,n}. The set SA is the collection of the subset sums of A. In this note, we discuss new results (and proofs) on few well-known problems concerning SA. In particular, we improve an estimate of Alon and Erd?s concerning monochromatic representations.     

Constructing Ramsey graphs from Boolean function representations

Explicit construction of Ramsey graphs or graphs with no large clique or independent set, has remained a challenging open problem for a long time. While Erdös’ probabilistic argument shows the existence of graphs on 2n vertices with no clique or independent set of size 2 ⁿ , the best explicit constructions achieve a far weaker bound. There is a connection between Ramsey graph constructions and polynomial representations of Boolean functions due to Grolmusz; a low degree representation for the OR function can be used to explicitly construct Ramsey graphs [17,18]. We generalize the above relation by proposing a new framework. We propose a new definition of OR representations: a pair of polynomials represent the OR function if the union of their zero sets contains all points in {0, 1} ⁿ except the origin. We give a simple construction of a Ramsey graph using such polynomials. Furthermore, we show that all the known algebraic constructions, ones to due to Frankl-Wilson [12], Grolmusz [18] and Alon [2] are captured by this framework; they can all be derived from various OR representations of degree O(√n) based on symmetric polynomials. Thus the barrier to better Ramsey constructions through such algebraic methods appears to be the construction of lower degree representations. Using new algebraic techniques, we show that better bounds cannot be obtained using symmetric polynomials.     

Homology representations arising from the half cube, II

In a previous work, we defined a family of subcomplexes of the n-dimensional half cube by removing the interiors of all half cube shaped faces of dimension at least k, and we proved that the reduced homology of such a subcomplex is concentrated in degree k−1. This homology module supports a natural action of the Coxeter group W(Dn) of type D. In this paper, we explicitly determine the characters (over C) of these homology representations, which turn out to be multiplicity free. Regarded as representations of the symmetric group Sn by restriction, the homology representations turn out to be direct sums of certain representations induced from parabolic subgroups. The latter representations of Sn agree (over C) with the representations of Sn on the (k−2)-nd homology of the complement of the k-equal real hyperplane arrangement.     

A note on equal unions in families of sets

A family of sets has the equal union property if and only if there exist two nonempty disjoint subfamilies having the same union. We prove that any n nonempty subsets of an n-element set have the equal union property if the sum of their cardinalities exceeds n(n+1)/2. This bound is tight. Among families in which the sum of the cardinalities equals n(n+1)/2, we characterize those having the equal union property.     

A bijection of the set of 3-regular partitions

A bijection of the set of 3-regular partitions of an integer n is constructed. It is shown that this map has order 2 and that the 3-cores of a partition and its image have diagrams which are mutual transposes. It is conjectured that this is the same bijection as the one induced, using the labeling of Farahat, Müller, and Peel, from the action of the alternating character upon the 3-modular irreducible representations of the symmetric group of degree n.     

Critical Sets of Full <Emphasis Type="Italic">n</Emphasis>-Latin Squares

The full n-Latin square is the \(n\times n\) array with symbols \(1,2,\dots ,n\) in each cell. In a way that is analogous to critical sets of full designs, a critical set of the full n-Latin square can be used to find a defining set for any Latin square of order n. In this paper we study the size of the smallest critical set for a full n-Latin square, showing this to be somewhere between \((n^3-2n^2+2n)/2\) and \((n-1)^3+1\). In the case that each cell is either full or empty, we show the size of a critical set in the full n-Latin square is always equal to \(n^3-2n^2-n\).     

The codimension of singular matrix pairs

The singular pairs of n × n matrices [those satisfying det(A? λB)  0] form a closed set of codimension n + 1 inside the space of all matrix pairs. The same holds for singular symmetric pairs. For Hermitian pairs, the singular ones form a closed set of codimension n+ 1 orn + 2 according as n is odd or even. The irreducible components of these closed sets are determined by various basic singular summands.     

Local representations of braid groups

We study the local linear representations of the braid group B ₃ and the homogeneous local representations of B _n for n ≥ 2. We investigate the connection of these representations with the Burau representation. The linear representations of B _n are constructed from the Wada representation of B _n in the automorphism group of a free group.     

Locally bounded coverings and factorial properties of graphs

For a graph property X, let X_n be the number of graphs with vertex set {1,…,n} having property X, also known as the speed of X. A property X is called factorial if X is hereditary (i.e. closed under taking induced subgraphs) and n^c₁n≤X_n≤n^c₂n for some constants c₁ and c₂. Hereditary properties with speed slower than factorial are surprisingly well structured. The situation with factorial properties is more complicated and less explored. Only the properties with speeds up to the Bell number are well studied and well behaved. To better understand the behavior of factorial properties with faster speeds we introduce a structural tool called locally bounded coverings and show that a variety of graph properties can be described by means of this tool.     

On local newforms for unramified U(2, 1)

Let G be the unramified unitary group in three variables defined over a p-adic field F with p ≠ 2. In this paper, we investigate local newforms for irreducible admissible representations of G. We introduce a family of open compact subgroups {K _n } _n≥0 of G to define the local newforms for representations of G as the K _n -fixed vectors. We prove the existence of local newforms for generic representations and the multiplicity one property of the local newforms for admissible representations.     

Identities for partial Bell polynomials derived from identities for weighted integer compositions

We discuss closed-form formulas for the (n, k)th partial Bell polynomials derived in Cvijovi? (Appl Math Lett 24:1544–1547, 2011). We show that partial Bell polynomials are special cases of weighted integer compositions, and demonstrate how the identities for partial Bell polynomials easily follow from more general identities for weighted integer compositions. We also provide short and elegant probabilistic proofs of the latter, in terms of sums of discrete integer-valued random variables. Finally, we outline further identities for the partial Bell polynomials.     

Combinatorics on partial word correlations

Partial words are strings over a finite alphabet that may contain a number of “do not know” symbols. In this paper, we consider the period and weak period sets of partial words of length n over a finite alphabet, and study the combinatorics of specific representations of them, called correlations, which are binary and ternary vectors of length n indicating the periods and weak periods. We characterize precisely which vectors represent the period and weak period sets of partial words and prove that all valid correlations may be taken over the binary alphabet. We show that the sets of all such vectors of a given length form distributive lattices under suitably defined partial orderings. We show that there is a well-defined minimal set of generators for any binary correlation of length n and demonstrate that these generating sets are the primitive subsets of {1,2,…,n−1}. We also investigate the number of partial word correlations of length n. Finally, we compute the population size, that is, the number of partial words sharing a given correlation, and obtain recurrences to compute it. Our results generalize those of Guibas, Odlyzko, Rivals and Rahmann.     

Generalized Riordan arrays

In this paper, we generalize the concept of Riordan array. A generalized Riordan array with respect to c_n is an infinite, lower triangular array determined by the pair (g(t),f(t)) and has the generic element d_n,k=[tⁿ/c_n]g(t)(f(t))^k/c_k, where c_n is a fixed sequence of non-zero constants with c₀=1.We demonstrate that the generalized Riordan arrays have similar properties to those of the classical Riordan arrays. Based on the definition, the iteration matrices related to the Bell polynomials are special cases of the generalized Riordan arrays and the set of iteration matrices is a subgroup of the Riordan group. We also study the relationships between the generalized Riordan arrays and the Sheffer sequences and show that the Riordan group and the group of Sheffer sequences are isomorphic. From the Sheffer sequences, many special Riordan arrays are obtained. Additionally, we investigate the recurrence relations satisfied by the elements of the Riordan arrays. Based on one of the recurrences, some matrix factorizations satisfied by the Riordan arrays are presented. Finally, we give two applications of the Riordan arrays, including the inverse relations problem and the connection constants problem.     

Degenerate group of type A: Representations and flag varieties

We consider the degeneration of a simple Lie group which is a semidirect product of its Borel subgroup and a normal Abelian unipotent subgroup. We introduce a class of highest weight representations of the degenerate group of type A, generalizing the construction of PBW-graded representations of the classical group (PBW is an abbreviation for “Poincaré-Birkhoff-Witt”). Following the classical construction of flag varieties, we consider the closures of orbits of the Abelian unipotent subgroup in projectivizations of the representations. We show that the degenerate flag varieties F _n ^a and their desingularizations R _n can be obtained via this construction. We prove that the coordinate ring of R _n is isomorphic as a vector space to the direct sum of the duals of the highest weight representations of the degenerate group. At the end we state several conjectures on the structure of the highest weight representations of the degenerate group of type A.     

The existence of regular self-complementary 3-uniform hypergraphs

A k-uniform hypergraph with vertex set V and edge set E is called t-subset-regular if every t-element subset of V lies in the same number of elements of E. In this paper we show that a 1-subset-regular self-complementary 3-uniform hypergraph with n vertices exists if and only if n≥5 and n is congruent to 1 or 2 modulo 4.     

Asymptotic expansions for the distribution of the crossing number of a strip by a Markov-modulated random walk

We obtain complete asymptotic expansions for the distribution of the crossing number of a strip in n steps by sample paths of a random walk defined on a finite Markov chain. We assume that the Cramér condition holds for the distribution of jumps and the width of the strip grows with n. The method consists in finding factorization representations of the moment generating functions of the distributions under study, isolating the main terms in the asymptotics of the representations, and inverting those main terms by the modified saddle-point method.