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.     

Jacobi polynomials and associated reproducing kernel Hilbert spaces

This paper deals with a generating function of the Jacobi polynomials that satisfies the following properties (I) and (II). (I) The generating function is the kernel of an integral operator that is unitary. (II) The image of the unitary operator is a reproducing kernel Hilbert space of analytic functions and the reproducing kernel is given as a special value of the generating function above. A generating function that satisfies (I) is given in Watanabe (1998) [11]. The purpose of this paper is to give a generating function that satisfies (I) and (II). From a group theoretical point of view, a similar construction for zonal spherical functions is given in Watanabe (2006) [12].     

Universal characters from the MacDonald identities

The main result of [Kostant, Invent. Math. 158 (1) (2004) 181-226, arXiv:math.GR/0309232] shows that a sequence of complexes associated with the MacDonald identities gives a sequence of universal characters which extends and generalises some representations of the exceptional series given in [Deligne, C. R. Acad. Sci. Paris Sér. Math. 322(4) (1996) 321-326]. This proves the conjectures in [Macfarlane, Pfeiffer, J. Phys. A 36 (2003) 230 5-2317. arxiv.math-ph/0208014].In this paper, we use a twisted version of this definition to define a sequence of complexes for the first row of the Freudenthal magic square.We also calculate the dimensions of these characters for the special linear groups and for the symplectic groups. This gives two new explicit expressions for the D’Arcais polynomials.     

Kibble–Slepian formula and generating functions for 2D polynomials

We prove a generalization of the Kibble–Slepian formula (for Hermite polynomials) and its unitary analogue involving the 2D Hermite polynomials recently proved in [16]. We derive integral representations for the 2D Hermite polynomials which are of independent interest. Several new generating functions for 2D q-Hermite polynomials will also be given.     

WELL-CONDITIONED FRAMES FOR HIGH ORDER FINITE ELEMENT METHODS

The purpose of this paper is to discuss representations of high order C⁰finite element spaces on simplicial meshes in any dimension.When computing with high order piecewise polynomials the conditioning of the basis is likely to be important.The main result of this paper is a construction of representations by frames such that the associated L²condition number is bounded independently of the polynomial degree.To our knowledge,such a representation has not been presented earlier.The main tools we will use for the construction is the bubble transform,introduced previously in[1],and properties of Jacobi polynomials on simplexes in higher dimensions.We also include a brief discussion of preconditioned iterative methods for the finite element systems in the setting of representations by frames.     

A general representation theorem for partially ordered commutative rings

An extension of the Kadison-Dubois representation theorem is proved. This extends both the classical version [3] and the preordering version given by Jacobi in [5]. It is then shown how this can be used to sharpen the results on representations of strictly positive polynomials given by Jacobi and Prestel in [6]. Received: 10 January 2000; in final form: 20 September 2000 / Published online: 19 October 2001     

Separants of some polynomials

The explicit form is given of the separants of the polynomials of the author’s previous article [1]. This entails clarification of the main theorem of [1].     

Spaces of bivariate spline functions over triangulation

We consider the spaces of bivariate C^μ-splines of degree k defined over arbitrary triangulations of a polygonal domain. We get an explicit formula for the dimension of such spaces when k≥3μ+2 and construct a local basis for them. The dimension formula is valid for any polygonal domain even it is complex connected, and the formula is sharp since it evaluates the lower-bound which was given by Schumaker in [11].     

Representations of orthogonal polynomials

Zeilberger's algorithm provides a method to compute recurrence and differential equations from given hypergeometric series representations, and an adaption of Almquist and Zeilberger computers recurrence and differential equations for hyperexponential integrals. Further versions of this algorithm allow the computation of recurrence and differential equations from Rodrigues type formulas and from generating functions. In particular, these algorithms can be used to compute the differential/difference and recurrence equations for the classical continuous and discrete orthogonal polynomials from their hypergeometric representations, and from their Rodrigues representations and generating functions.In recent work, we used an explicit formula for the recurrence equation of families of classical continuous and discrete orthogonal polynomials, in terms of the coefficients of their differential/difference equations, to give an algorithm to identify the polynomial system from a given recurrence equation.In this article we extend these results by presenting a collection of algorithms with which any of the conversions between the differential/difference equation, the hypergeometric representation, and the recurrence equation is possible.The main technique is again to use explicit formulas for structural identities of the given polynomial systems.     

Bilinear Generating Functions for Orthogonal Polynomials

Using realizations of the positive discrete series representations of the Lie algebra su(1,1) in terms of Meixner—Pollaczek polynomials, the action of su(1,1) on Poisson kernels of these polynomials is considered. In the tensor product of two such representations, two sets of eigenfunctions of a certain operator can be considered and they are shown to be related through continuous Hahn polynomials. As a result, a bilinear generating function for continuous Hahn polynomials is obtained involving the Poisson kernel of Meixner—Pollaczek polynomials; this result is also known as the Burchnall—Chaundy formula. For the positive discrete series representations of the quantized universal enveloping algebra U _q (su(1,1)) a similar analysis is performed and leads to a bilinear generating function for Askey—Wilson polynomials involving the Poisson kernel of Al-Salam and Chihara polynomials. July 6, 1997. Date accepted: September 23, 1998.     

On modified Chebyshev polynomials

Two elegant representations are derived for the modified Chebyshev polynomials discussed by Witula and Slota [R. Witula, D. Slota, On modified Chebyshev polynomials, J. Math. Anal. Appl. 324 (2006) 321-343].     

Peters type polynomials and numbers and their generating functions: Approach with p‐adic integral method

The aim of this paper is to introduce and investigate some of the primary generalizations and unifications of the Peters polynomials and numbers by means of convenient generating functions and p‐adic integrals method. Various fundamental properties of these polynomials and numbers involving some explicit series and integral representations in terms of the generalized Stirling numbers, generalized harmonic sums, and some well‐known special numbers and polynomials are presented. By using p‐adic integrals, we construct generating functions for Peters type polynomials and numbers (Apostol‐type Peters numbers and polynomials). By using these functions with their partial derivative eqautions and functional equations, we derive many properties, relations, explicit formulas, and identities including the Apostol‐Bernoulli polynomials, the Apostol‐Euler polynomials, the Boole polynomials, the Bernoulli polynomials, and numbers of the second kind, generalized harmonic sums. A brief revealing and historical information for the Peters type polynomials are given. Some of the formulas given in this article are given critiques and comments between previously well‐known formulas. Finally, two open problems for interpolation functions for Apostol‐type Peters numbers and polynomials are revealed.     

基于Jacobi多项式零点的Grünwald插值算子

本文考虑基于一般Jacobi多项式J_n~(α,β)(x)(—1<α,β<1)零点的Grnwald插值多项式G_n(f,x);主要证明了G_n(f,x)在(—1,1)内几乎一致收敛于连续函数f(x),并给出了点态逼近估计;拓广和完善了文献[1,2]的结果。     

Extensions of some results of P. Humbert on Bezout's identity for classical orthogonal polynomials

In this paper, the Bezout's identity is analyzed in the context of classical orthogonal polynomials solution of a second order differential equation of hypergeometric type. Differential equations, relation with the starting family as well as recurrence relations and explicit representations are given for the Bezout's pair. Extensions to classical orthogonal polynomials of a discrete variable and their q-analogues are also presented. Applications of these results for the representation of the second kind functions are given.     

Hilbert-type inequalities with a product-type homogeneous kernel and Schur polynomials

The main objective of this paper is to prove Hilbert-type and Hardy-Hilbert-type inequalities with a product-type homogeneous kernel, thus generalizing a result obtained in [Z. Xie, Z. Zheng, A Hilbert-type integral inequality whose kernel is a homogeneous form of degree −3, J. Math. Anal. Appl. 339 (2008) 324-331]. In some cases the best possible constants obtained in these inequalities are expressed using the Schur polynomials.     

Explicit Coercivity Estimates for the Linearized Boltzmann and Landau Operators

We prove explicit coercivity estimates for the linearized Boltzmann and Landau operators, for a general class of interactions including any inverse-power law interactions, and hard spheres. The functional spaces of these coercivity estimates depend on the collision kernel of these operators. They cover the spectral gap estimates for the linearized Boltzmann operator with Maxwell molecules, improve these estimates for hard potentials, and are the first explicit coercivity estimates for soft potentials (including in particular the case of Coulombian interactions). We also prove a regularity property for the linearized Boltzmann operator with non locally integrable collision kernels, and we deduce from it a new proof of the compactness of its resolvent for hard potentials without angular cutoff.     

Problems of control and information theory (Hungary)

The bezoutian matrix, which provides information concerning co-primeness and greatest common divisor of polynomials, has recently been generalized by Heinig to the case of square polynomial matrices. Some of the properties of the bezoutian for the scalar case then carry over directly. In particular, the central result of the paper is an extension of a factorization due to Barnett, which enables the bezoutian to be expressed in terms of a Kronecker matrix polynomial in an appropriate block companion matrix. The most important consequence of this result is a determination of the structure of the kernel of the bezoutian. Thus, the bezoutian is nonsingular if and only if the two polynomial matrices have no common eigenvalues (i.e., their determinants are relatively prime); otherwise, the dimension of the kernel is given in terms of the multiplicities of the common eigenvalues of the polynomial matrices. Finally, an explicit basis is developed for the kernel of the bezoutian, using the concept of Jordan chains.     

A characterization of the classical unital

We define Buekenhout unitals in derivable translation planes of dimension 2 over their kernel and provide a characterization of these unitals. We use this result to improve the characterization of classical unitals given by Lefèvre-Percsy [13] and Faina and Korchmáros [7].     

Polynomials with and without determinantal representations

The problem of writing real zero polynomials as determinants of linear matrix polynomials has recently attracted a lot of attention. Helton and Vinnikov [9] have proved that any real zero polynomial in two variables has a determinantal representation. Brändén [2] has shown that the result does not extend to arbitrary numbers of variables, disproving the generalized Lax conjecture. We prove that in fact almost no real zero polynomial admits a determinantal representation; there are dimensional differences between the two sets. The result follows from a general upper bound on the size of linear matrix polynomials. We then provide a large class of surprisingly simple explicit real zero polynomials that do not have a determinantal representation. We finally characterize polynomials of which some power has a determinantal representation, in terms of an algebra with involution having a finite dimensional representation. We use the characterization to prove that any quadratic real zero polynomial has a determinantal representation, after taking a high enough power. Taking powers is thereby really necessary in general. The representations emerge explicitly, and we characterize them up to unitary equivalence.     

Linearized trinomials with maximum kernel

Linearized polynomials have attracted a lot of attention because of their applications in both geometric and algebraic areas. Let q be a prime power, n be a positive integer and σ be a generator of $\mathrm{Gal}({\mathbb{F}}_{q^n}:{\mathbb{F}}_q)$. In this paper we provide closed formulas for the coefficients of a σ-trinomial f over ${\mathbb{F}}_{q^n}$ which ensure that the dimension of the kernel of f equals its σ-degree, that is linearized polynomials with maximum kernel. As a consequence, we present explicit examples of linearized trinomials with maximum kernel and characterize those having σ-degree 3 and 4. Our techniques rely on the tools developed in [24]. Finally, we apply these results to investigate a class of rank metric codes introduced in [8], to construct quasi-subfield polynomials and cyclic subspace codes, obtaining new explicit constructions to the conjecture posed in [37].