Orthogonal matrix polynomials, scalar-type Rodrigues’ formulas and Pearson equations

Some families of orthogonal matrix polynomials satisfying second-order differential equations with coefficients independent of n have recently been introduced (see [Internat. Math. Res. Notices 10 (2004) 461–484]). An important difference with the scalar classical families of Jacobi, Laguerre and Hermite, is that these matrix families do not satisfy scalar type Rodrigues’ formulas of the type (ΦⁿW)⁽ⁿ⁾W^-1, where Φ is a matrix polynomial of degree not bigger than 2. An example of a modified Rodrigues’ formula, well suited to the matrix case, appears in [Internat. Math. Res. Notices 10 (2004) 482].In this note, we discuss some of the reasons why a second order differential equation with coefficients independent of n does not imply, in the matrix case, a scalar type Rodrigues’ formula and show that scalar type Rodrigues’ formulas are most likely not going to play in the matrix valued case the important role they played in the scalar valued case. We also mention the roles of a scalar-type Pearson equation as well as that of a noncommutative version of it.     

Family of Pearson discrete distributions generated by the univariate hypergeometric function 3F2(α1, α2, α3; γ1, γ2; λ)

In this work we present a study of the Pearson discrete distributions generated by the hypergeometric function ₃F₂(α₁, α₂, α₃;γ₁, γ₂; λ), a univariate extension of the Gaussian hypergeometric function, through a constructive methodology. We start from the polynomial coefficients of the difference equation that lead to such a function as a solution. Immediately after, we obtain the generating probability function and the differential equation that it satisfies, valid for any admissible values of the parameters. We also obtain the differential equations that satisfy the cumulants generating function, moments generating function and characteristic function, From this point on, we obtain a relation in recurrences between the moments about the origin, allowing us to create an equation system for estimating the parameters by the moment method. We also establish a classification of all possible distributions of such type and conclude with a summation theorem that allows us study some distributions belonging to this family. © 1997 by John Wiley & Sons, Ltd.     

W2, p estimates of the heat equation in Ω⊂ℝn and the restrictions on ∂Ω

This is an alternative approach of finding the W^{2, p} estimates of the heat equation in a domain, Ω??ⁿ. Methods used in (Acta Math. Sin. 2003; 19 (2):381–396) are expanded to the case of a bounded domain. As a result, milder restrictions are applied to ?Ω than previously required by using the classical singular integral approach. Copyright © 2005 John Wiley & Sons, Ltd.     

Finding paths between 3‐colorings

Given a 3‐colorable graph G together with two proper vertex 3‐colorings α and β of G, consider the following question: is it possible to transform α into β by recoloring vertices of G one at a time, making sure that all intermediate colorings are proper 3‐colorings? We prove that this question is answerable in polynomial time. We do so by characterizing the instances G, α, β where the transformation is possible; the proof of this characterization is via an algorithm that either finds a sequence of recolorings between α and β, or exhibits a structure which proves that no such sequence exists. In the case that a sequence of recolorings does exist, the algorithm uses O(|V(G)|²) recoloring steps and in many cases returns a shortest sequence of recolorings. We also exhibit a class of instances G, α, β that require Ω(|V(G)|²) recoloring steps. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 69‐82, 2011     

Non-broken circuits of reflection groups and factorization inD n

The set of non-broken circuits of a reflection group W, denoted NBC(W), appears as a basis of the Orlik-Solomon algebra ofW. The factorization of their enumerating polynomial with respect to their cardinality involves the exponentsd _i-1 ofW. A simple explanation of this factorization is known only for the symmetric groupsS _n (Whitney [13]) and for the hyperoctahedral groupsB _n (Lehrer [7]). In this paper, we present an elementary proof of the fact that the set NBC(W) of any refection groupW is in bijection with the group elements ofW. We give a simple characterization of the non-broken circuits of the Weyl groups of typeD _n and we use this characterization to prove the factorization of their enumerating polynomial. Work partially supported by FGIA from ASU. Work partially supported by NSERC (Canada).     

Weak Hausdorff Gaps and the 𝔭 ≤ t Problem

We find topological characterizations of the pseudointersection number ?? and the tower number t of the real line and we show that ?? < t iff there exists a compact separable T₂ space X of π-weight < ?? that can be covered by < t nowhere dense sets iff there exists a weak Hausdorff gap of size K < t, i. e., a pair ({A : i ≠ k}, {B_J : j ε K}) C [W]^W X [U]W such that A = {A_i : i ε K} is a decreasing tower, B = {B_j : j ε K) is a family of pseudointersections of A, and there is no pseudointersection S of A meeting each member of B in an infinite set.     

4‐Coloring P6‐Free Graphs with No Induced 5‐Cycles

We show that the 4‐coloring problem can be solved in polynomial time for graphs with no induced 5‐cycle C₅ and no induced 6‐vertex path P₆     

Generalized Calogero–Moser systems from rational Cherednik algebras

We consider ideals of polynomials vanishing on the W-orbits of the intersections of mirrors of a finite reflection group W. We determine all such ideals that are invariant under the action of the corresponding rational Cherednik algebra hence form submodules in the polynomial module. We show that a quantum integrable system can be defined for every such ideal for a real reflection group W. This leads to known and new integrable systems of Calogero–Moser type which we explicitly specify. In the case of classical Coxeter groups, we also obtain generalized Calogero–Moser systems with added quadratic potential.     

Enveloppes polynômiales d'ensembles compacts invariants

We consider the following problem: let V^? be a finite dimensional vector space, and U be a compact group of ?‐linear automorphisms of V^?. The polynomial envelope of a compact set Q ? V^? is defined as where ??(V^?) denotes the space of holomorphic polynomial functions on V^?. The problem is to determine the polynomial envelope of a compact set which is U‐invariant. We solve the problem when U is the isotropy subgroup at the origin of the automorphism group of a bounded symmetric domain of tube type. The case of a domain of type II has been solved by C. Sacré [1992], and, for a domain of type IV, it has been solved by L. Bou Attour [1993]. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Precoloring extension for K4‐minor‐free graphs

Let G=(V, E) be a graph where every vertex v∈V is assigned a list of available colors L(v). We say that G is list colorable for a given list assignment if we can color every vertex using its list such that adjacent vertices get different colors. If L(v)={1, …, k} for all v∈V then a corresponding list coloring is nothing other than an ordinary k‐coloring of G. Assume that W?V is a subset of V such that G[W] is bipartite and each component of G[W] is precolored with two colors taken from a set of four. The minimum distance between the components of G[W] is denoted by d(W). We will show that if G is K₄‐minor‐free and d(W)≥7, then such a precoloring of W can be extended to a 4‐coloring of all of V. This result clarifies a question posed in 10. Moreover, we will show that such a precoloring is extendable to a list coloring of G for outerplanar graphs, provided that |L(v)|=4 for all v∈V\W and d(W)≥7. In both cases the bound for d(W) is best possible. © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 284‐294, 2009     

Finite-Dimensional Subalgebras In Polynomial Lie Algebras Of Rank One

Let W _n ( \mathbb K {\mathbb K} ) be the Lie algebra of derivations of the polynomial algebra \mathbb K {\mathbb K} [X] := \mathbb K {\mathbb K} [x ₁,…,x _n ]over an algebraically closed field \mathbb K {\mathbb K} of characteristic zero. A subalgebra L í W_n(\mathbbK) L \subseteq {W_n}(\mathbb{K}) is called polynomial if it is a submodule of the \mathbb K {\mathbb K} [X]-module W _n ( \mathbb K {\mathbb K} ). We prove that the centralizer of every nonzero element in L is abelian, provided that L is of rank one. This fact allows one to classify finite-dimensional subalgebras in polynomial Lie algebras of rank one.     

Some results on λ‐designs with two block sizes

A λ‐design is a family ?? = {B₁, B₂, …, B_v} of subsets of X = {1, 2, …, v} such that |B_i∩B_j| = λ for all i≠jand not all B_i are of the same size. The only known example of λ‐designs (called type‐1 designs) are those obtained from symmetric designs by a certain complementation procedure. Ryser [J Algebra 10 (1968), 246–261] and Woodall [Proc London Math Soc 20 (1970), 669–687] independently conjectured that all λ‐designs are type‐1. Let g = gcd(r ? 1, r^* ? 1), where rand r^* are the two replication numbers. Ionin and Shrikhande [J Combin Comput 22 (1996), 135–142; J Combin Theory Ser A 74 (1996), 100–114] showed that λ‐designs with g = 1, 2, 3, 4 are type‐1 and that the Ryser–Woodall conjecture is true for λ‐designs on p + 1, 2p + 1, 3p + 1, 4p + 1 points, where pis a prime. Hein and Ionin [Codes and Designs—Proceedings of Conference honoring Prof. D. K. Ray‐Chaudhuri on the occasion of his 65th birthday, Ohio State University Mathematical Research Institute Publications, 10, Walter de Gruyter, Berlin, 2002, pp. 145–156] proved corresponding results for g = 5 and Fiala [Codes and Designs—Proceedings of Conference honoring Prof. D. K. Ray‐Chaudhuri on the occasion of his 65th birthday, Ohio State University Mathematical Research Institute Publications, 10, Walter de Gruyter, Berlin, 2002, pp. 109–124; Ars Combin 68 (2003), 17–32; Ars Combin, to appear] for g = 6, 7, and 8. In this article, we consider λ designs with exactly two block sizes. We show that in this case, the conjecture is true for g = 9, 11, 12, 13, 15, 16, 17, 19, 20, 21, and for g = 10, 14, 18, 22 with v≠4λ ? 1. We also give two results on such λ‐designs on v = 9p + 1 and 12p + 1 points, where pis a prime. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:95‐110, 2011     

Archimedean ϕ ‐tolerance graphs

Let ? be a symmetric binary function, positive valued on positive arguments. A graph G = (V,E) is a ?‐tolerance graph if each vertex υ ∈ V can be assigned a closed interval I_υ and a positive tolerance t_υ so that xy ∈ E ? | I_x ∩ I_y|≥ ? (t_x,t_y). An Archimedean function has the property of tending to infinity whenever one of its arguments tends to infinity. Generalizing a known result of [15] for trees, we prove that every graph in a large class (which includes all chordless suns and cacti and the complete bipartite graphs K_2,k) is a ?‐tolerance graph for all Archimedean functions ?. This property does not hold for most graphs. Next, we present the result that every graph G can be represented as a ?_G‐tolerance graph for some Archimedean polynomial ?_G. Finally, we prove that there is a ?universal”? Archimedean function ? ^* such that every graph G is a ?^*‐tolerance graph. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 179–194, 2002     

On ε‐biased generators in NC0

Cryan and Miltersen (Proceedings of the 26th Mathematical Foundations of Computer Science, 2001, pp. 272–284) recently considered the question of whether there can be a pseudorandom generator in NC⁰, that is, a pseudorandom generator that maps n‐bit strings to m‐bit strings such that every bit of the output depends on a constant number k of bits of the seed. They show that for k = 3, if m ≥ 4n + 1, there is a distinguisher; in fact, they show that in this case it is possible to break the generator with a linear test, that is, there is a subset of bits of the output whose XOR has a noticeable bias. They leave the question open for k ≥ 4. In fact, they ask whether every NC⁰ generator can be broken by a statistical test that simply XORs some bits of the input. Equivalently, is it the case that no NC⁰ generator can sample an ε‐biased space with negligible ε? We give a generator for k = 5 that maps n bits into cn bits, so that every bit of the output depends on 5 bits of the seed, and the XOR of every subset of the bits of the output has bias 2. For large values of k, we construct generators that map n bits to bits such that every XOR of outputs has bias . We also present a polynomial‐time distinguisher for k = 4,m ≥ 24n having constant distinguishing probability. For large values of k we show that a linear distinguisher with a constant distinguishing probability exists once m ≥ Ω(2^kn^?k/2?). Finally, we consider a variant of the problem where each of the output bits is a degree k polynomial in the inputs. We show there exists a degree k = 2 pseudorandom generator for which the XOR of every subset of the outputs has bias 2^?Ω(n) and which maps n bits to Ω(n²) bits. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

A semidefinite program approach for computing the maximum eigenvalue of a class of structured tensors and its applications in hypergraphs and copositivity test

Finding the maximum eigenvalue of a symmetric tensor is an important topic in tensor computation and numerical multilinear algebra. In this paper, we introduce a new class of structured tensors called W‐tensors, which not only extends the well‐studied nonnegative tensors by allowing negative entries but also covers several important tensors arising naturally from spectral hypergraph theory. We then show that finding the maximum H‐eigenvalue of an even‐order symmetric W‐tensor is equivalent to solving a structured semidefinite program and hence can be validated in polynomial time. This yields a highly efficient semidefinite program algorithm for computing the maximum H‐eigenvalue of W‐tensors and is based on a new structured sums‐of‐squares decomposition result for a nonnegative polynomial induced by W‐tensors. Numerical experiments illustrate that the proposed algorithm can successfully find the maximum H‐eigenvalue of W‐tensors with dimension up to 10,000, subject to machine precision. As applications, we provide a polynomial time algorithm for computing the maximum H‐eigenvalues of large‐size Laplacian tensors of hyperstars and hypertrees, where the algorithm can be up to 13 times faster than the state‐of‐the‐art numerical method introduced by Ng, Qi, and Zhou in 2009. Finally, we also show that the proposed algorithm can be used to test the copositivity of a multivariate form associated with symmetric extended Z‐tensors, whose order may be even or odd.     

Inducing <Emphasis Type="Italic">W</Emphasis>-graphs

 Let ℋ be the Hecke algebra associated with a Coxeter group W. Many interesting ℋ-modules can be described using the concept of a W-graph, as introduced in the influential paper [4] of Kazhdan and Lusztig. In particular, Kazhdan and Lusztig showed that the regular representation of ℋ has an associated W-graph. The purpose of this note is to show that if W _J is a parabolic subgroup of W and V is a module for the corresponding Hecke algebra ℋ _J , then a W _J -graph structure for V gives rise to a W-graph structure for the induced module ℋ⊗ _ℋJ V. In the case that W _J is the identity subgroup and V has dimension 1, our construction coincides with that given by Kazhdan and Lusztig for the regular representation. For arbitrary J and V of dimension 1 we recover the constructions of Couillens [1] and Deodhar [3]. Received: 14 June 2002; in final form: 13 August 2002 / Published online: 1 April 2003 Mathematics Subject Classification (2000): 20C08     

The Alexander polynomial and finite type 3-manifold invariants

Using elementary counting methods, we calculate a universal perturbative invariant (also known as the LMO invariant) of a 3-manifold M, satisfying , in terms of the Alexander polynomial of M. We show that +1 surgery on a knot in the 3-sphere induces an injective map from finite type invariants of integral homology 3-spheres to finite type invariants of knots. We also show that weight systems of degree 2m on knots, obtained by applying finite type 3m invariants of integral homology 3-spheres, lie in the algebra of Alexander-Conway weight systems, thus answering the questions raised in [Ga]. Received: 27 April 1998 / in final form: 8 August 1999     

Bernstein sets and κ ‐coverings

In this paper we study a notion of a κ ‐covering set in connection with Bernstein sets and other types of non‐measurability. Our results correspond to those obtained by Muthuvel in [7] and Nowik in [8]. We consider also other types of coverings (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Geometry and analysis of spin equations

We introduce W‐spin structures on a Riemann surface Σ and give a precise definition to the corresponding W‐spin equations for any quasi‐homogeneous polynomial W. Then we construct examples of nonzero solutions of spin equations in the presence of Ramond marked points. The main result of the paper is a compactness theorem for the moduli space of the solutions of W‐spin equations when W = W(x₁, …, x_t) is a nondegenerate, quasi‐homogeneous polynomial with fractional degrees (or weights) q_i < ½ for all i. In particular, the compactness theorem holds for the superpotentials E₆, E₇, E₈ or A_{n ? 1}, D_{n + 1} for n ≥ 3. © 2008 Wiley Periodicals, Inc.