On a combinatorial property of choice functions of finite sets

We consider choice functions k[X]→X, where X is a finite set and k[X] denotes the set of all k-subsets of X. We define a property of domination for such maps generalizing the classical case k=2 (tournaments) and prove the existence of a dominating element generalizing the existence of a 2-root (king) in the classical case.     

Tree components in random distance graphs of special form

In this work, we consider the problem of distribution of the number of tree components with given number of vertices k(k ?? 2) for a certain series of random distance graphs. Generalizations of the classical Erd?s?CRényi results are obtained in the case of geometric graphs of special form.     

Convex Pencils of Real Quadratic Forms

We study the topology of the set X of the solutions of a system of two quadratic inequalities in the real projective space ?P ⁿ (e.g. X is the intersection of two real quadrics). We give explicit formulas for its Betti numbers and for those of its double cover in the sphere S ⁿ ; we also give similar formulas for level sets of homogeneous quadratic maps to the plane. We discuss some applications of these results, especially in classical convexity theory. We prove the sharp bound b(X)??2n for the total Betti number of X; we show that for odd n this bound is attained only by a singular?X. In the nondegenerate case we also prove the bound on each specific Betti number b _k (X)??2(k+2).     

Theorems of Erdős-Ko-Rado type in geometrical settings

The original Erds-Ko-Rado problem has inspired much research. It started as a study on sets of pairwise intersecting k-subsets in an n-set, then it gave rise to research on sets of pairwise non-trivially intersecting k-dimensional vector spaces in the vector space V (n, q) of dimension n over the finite field of order q, and then research on sets of pairwise non-trivially intersecting generators and planes in finite classical polar spaces. We summarize the main results on the Erds-Ko-Rado problem in these three settings, mention the Erds-Ko-Rado problem in other related settings, and mention open problems for future research.     

On series containing products of Legendre polynomials

Explicit formulas are established for infinite sums of products of three or four Legendre polynomials of nth order with coefficients 2n + 1; the series depends only the arguments of the polynomials and contains no other variables. We show that, for the product of three polynomials, the sum is inverse to the root of the product of four sine functions and, in the case of four polynomials, this expression additionally contains the elliptic integral K(k) as a multiplier. Analogs and particular cases are considered which allow one to compare the relationships proved in this note with results proved in various domains of mathematical physics and classical functional analysis.     

Plünnecke and Kneser type theorems for dimension estimates

Given a division ring K containing the field k in its center and two finite subsets A and B of K*, we give some analogues of Plünnecke and Kneser Theorems for the dimension of the k-linear span of the Minkowski product AB in terms of the dimensions of the k-linear spans of A and B. We also explain how they imply the corresponding more classical theorems for abelian groups. These Plünnecke type estimates are then generalized to the case of associative algebras. We also obtain an analogue in the context of division rings of a theorem by Tao describing the sets of small doubling in a group.     

On formal quantum group laws

There exist natural generalizations of the concept of formal groups laws for noncommutative power series. This is a note on formal quantum group laws and quantum group law chunks. Formal quantum group laws correspond to noncommutative (topological) Hopf algebra structures on free associative power series algebras ká áx₁,...,x_m ? ?k\langle\! \langle x_1,\dots,x_m \rangle\! \rangle , k a field. Some formal quantum group laws occur as completions of noncommutative Hopf algebras (quantum groups). By truncating formal power series, one gets quantum group law chunks. ¶If the characteristic of k is 0, the category of (classical) formal group laws of given dimension m is equivalent to the category of m-dimensional Lie algebras. Given a formal group law or quantum group law (chunk), the corresponding Lie structure constants are determined by the coefficients of its chunk of degree 2. Among other results, a classification of all quantum group law chunks of degree 3 is given. There are many more classes of strictly isomorphic chunks of degree 3 than in the classical case.     

A generalization of Hiraguchi's: Inequality for posets

For a poset X, Dim(X) is the smallest positive integer t for which X is isomorphic to a subposet of the cartesian product of t chains. Hiraguchi proved that if | X | ? 4, then Dim(X) ? [| X |/2]. For each k ? 2, we define Dim_k(X) as the smallest positive integer t for which X is isomorphic to a subposet of the cartesian product of t chains, each of length k. We then prove that if | X | ? 5, Dim₃(X) ? {| X |/2} and if | X | ? 6, then Dim₄(X) ? [| X |/2].     

Prescribing the Jacobian in critical spaces

We consider the Sobolev space $X = W^{s,p} \left( {\mathbb{S}^m ;\mathbb{S}^{k - 1} } \right)$ . We prove the existence of a robust distributional Jacobian Ju for u ∈ X, provided sp ≥ k ? 1; this generalizes a result of Bourgain, Brezis, and the second author [10] dealing with the case m = k. We identify the image of the map X ? u ? Ju in the critical case sp = k ? 1. This extends a result of Alberti, Baldo, and Orlandi [2] for s = 1 and p = k ? 1. We also present a new, analytical, dipole construction method.     

On the separation power and the completion of partial latin squares

Let n and m be natural numbers, n ? m. The separation power of order n and degree m is the largest integer k = k(n, m) such that for every (0, 1)-matrix A of order n with constant linesums equal to m and any set of k 1's in A there exist (disjoint) permutation matrices P₁,…, P_m such that A = P₁ + … + P_m and each of the k 1's lies in a different P_i. Almost immediately we have 1 ? k(n, m) ? m ? 1, yet in all cases where the value of k(n, m) is actually known it equals m ? 1 (except under the somewhat trivial circumstances of k(n, m) = 1). This leads to a conjecture about the separation power, namely that k(n, m) = m ? 1 if $\text{m ? [}\text{n}\text{2}\text{] + 1}$. We obtain the bound $\text{k(n, m) ? m ? [}\text{n}\text{2}\text{] + 2}$, so that this conjecture holds for n ? 7. We then move on to latin squares, describing several equivalent formulations of the concept. After establishing a sufficient condition for the completion of a partial latin square in terms of the separation power, we can show that the Evans conjecture follows from this conjecture about the separation power. Finally the lower bound on k(n, m) allows us to show, after some calculations, that the Evans conjecture is true for orders n ? 11.     

Intersection theorems under dimension constraints

In Ahlswede et al. [Discrete Math. 273(1-3) (2003) 9-21] we posed a series of extremal (set system) problems under dimension constraints. In the present paper, we study one of them: the intersection problem. The geometrical formulation of our problem is as follows. Given integers 0?t, k?n determine or estimate the maximum number of (0,1)-vectors in a k-dimensional subspace of the Euclidean n-space Rⁿ, such that the inner product (“intersection”) of any two is at least t. Also we are interested in the restricted (or the uniform) case of the problem; namely, the problem considered for the (0,1)-vectors of the same weight ω.The paper consists of two parts, which concern similar questions but are essentially independent with respect to the methods used.In Part I, we consider the unrestricted case of the problem. Surprisingly, in this case the problem can be reduced to a weighted version of the intersection problem for systems of finite sets. A general conjecture for this problem is proved for the cases mentioned in Ahlswede et al. [Discrete Math. 273(1-3) (2003) 9-21]. We also consider a diametric problem under dimension constraint.In Part II, we study the restricted case and solve the problem for t=1 and k<2ω, and also for any fixed 1?t?ω and k large.     

The Riemann problem for functions with polar lines of higher orders

We consider solutions of the jump problem, homogeneous and inhomogeneous Riemann problems for functions with polar lines of orders p _k +1 (k = 1, 2, … ), p _k ? 0. We study the cases of continuous and discontinuous coefficients. In the special case p _k = 0 the obtained results turn into the earlier known ones.     

Tensor products of complementary series of rank one Lie groups

We consider the tensor product π_α ? π_βof complementary series representations π_α and π_β of classical rank one groups SO_0(n, 1), SU(n, 1) and Sp(n, 1). We prove that there is a discrete component π_(α+β)for small parameters α and β(in our parametrization). We prove further that for SO_0(n, 1) there are finitely many complementary series of the form π_(α+β+2j,)j = 0, 1,..., k, appearing in the tensor product π_α ? π_βof two complementary series π_α and π_β, where k = k(α, β, n) depends on α, β and n.     

Boxicity of Leaf Powers

The boxicity of a graph G, denoted as boxi(G), is defined as the minimum integer t such that G is an intersection graph of axis-parallel t-dimensional boxes. A graph G is a k-leaf power if there exists a tree T such that the leaves of the tree correspond to the vertices of G and two vertices in G are adjacent if and only if their corresponding leaves in T are at a distance of at most k. Leaf powers are used in the construction of phylogenetic trees in evolutionary biology and have been studied in many recent papers. We show that for a k-leaf power G, boxi(G)??? k?1. We also show the tightness of this bound by constructing a k-leaf power with boxicity equal to k?1. This result implies that there exist strongly chordal graphs with arbitrarily high boxicity which is somewhat counterintuitive.     

Growth diagrams for the Schubert multiplication

We present a partial generalization of the classical Littlewood-Richardson rule (in its version based on Schützenberger's jeu de taquin) to Schubert calculus on flag varieties. More precisely, we describe certain structure constants expressing the product of a Schubert and a Schur polynomial. We use a generalization of Fomin's growth diagrams (for chains in Young's lattice of partitions) to chains of permutations in the so-called k-Bruhat order. Our work is based on the recent thesis of Beligan, in which he generalizes the classical plactic structure on words to chains in certain intervals in k-Bruhat order. Potential applications of our work include the generalization of the S₃-symmetric Littlewood-Richardson rule due to Thomas and Yong, which is based on Fomin's growth diagrams.     

The Murnaghan-Nakayama rule for k-Schur functions

We prove the Murnaghan-Nakayama rule for k-Schur functions of Lapointe and Morse, that is, we give an explicit formula for the expansion of the product of a power sum symmetric function and a k-Schur function in terms of k-Schur functions. This is proved using the noncommutative k-Schur functions in terms of the nilCoxeter algebra introduced by Lam and the affine analogue of noncommutative symmetric functions of Fomin and Greene.     

New results on the Bochner condition about classical orthogonal polynomials

The classical polynomials (Hermite, Laguerre, Bessel and Jacobi) are the only orthogonal polynomial sequences (OPS) whose elements are eigenfunctions of the Bochner second-order differential operator F (Bochner, 1929 [3]). In Loureiro, Maroni and da Rocha (2006) [18] these polynomials were described as eigenfunctions of an even order differential operator Fk with polynomial coefficients defined by a recursive relation. Here, an explicit expression of Fk for any positive integer k is given. The main aim of this work is to explicitly establish sums relating any power of F with Fk, k?1, in other words, to bring a pair of inverse relations between these two operators. This goal is accomplished with the introduction of a new sequence of numbers: the so-called A-modified Stirling numbers, which could be also called as Bessel or Jacobi-Stirling numbers, depending on the context and the values of the complex parameter A.     

Cross-intersecting sub-families of hereditary families

Families A₁,A₂,…,Ak of sets are said to be cross-intersecting if for any i and j in {1,2,…,k} with i≠j, any set in Ai intersects any set in Aj. For a finite set X, let X² denote the power set of X (the family of all subsets of X). A family H is said to be hereditary if all subsets of any set in H are in H; so H is hereditary if and only if it is a union of power sets. We conjecture that for any non-empty hereditary sub-family H≠{∅} of X² and any k?|X|+1, both the sum and the product of sizes of k cross-intersecting sub-families A₁,A₂,…,Ak (not necessarily distinct or non-empty) of H are maxima if A₁=A₂=?=Ak=S for some largest starSofH (a sub-family of H whose sets have a common element). We prove this for the case when H is compressed with respect to an element x of X, and for this purpose we establish new properties of the usual compression operation. As we will show, for the sum, the condition k?|X|+1 is sharp. However, for the product, we actually conjecture that the configuration A₁=A₂=?=Ak=S is optimal for any hereditary H and any k?2, and we prove this for a special case.     

Power convergence of Abel averages

Necessary and sufficient conditions are presented for the Abel averages of discrete and strongly continuous semigroups, T ^k and T _t , to be power convergent in the operator norm in a complex Banach space. These results cover also the case where T is unbounded and the corresponding Abel average is defined by means of the resolvent of T. They complement the classical results by Michael Lin establishing sufficient conditions for the corresponding convergence for a bounded T.