New results on expanders

Based on purely analytical methods, we exhibit new families of expanders in ${\mathrm{SL}}_2(p)$ (p prime) and $\mathrm{SU}(2)$, contributing to conjectures of A. Lubotzky and P. Sarnak. To cite this article: J. Bourgain, A. Gamburd, C. R. Acad. Sci. Paris, Ser. I 342 (2006).     

New results on quasi-subfield polynomials

Quasi-subfield polynomials were introduced by Huang et al. together with a new algorithm to solve the Elliptic Curve Discrete Logarithm Problem (ECDLP) over finite fields of small characteristic. In this paper we provide both new quasi-subfield polynomial families and a new theorem limiting their existence. Our results do not allow to derive any speedup for the new ECDLP algorithm compared to previous approaches.     

New results on the peak algebra

The peak algebra is a unital subalgebra of the symmetric group algebra, linearly spanned by sums of permutations with a common set of peaks. By exploiting the combinatorics of sparse subsets of [n−1] (and of certain classes of compositions of n called almost-odd and thin), we construct three new linear bases of . We discuss two peak analogs of the first Eulerian idempotent and construct a basis of semi-idempotent elements for the peak algebra. We use these bases to describe the Jacobson radical of and to characterize the elements of in terms of the canonical action of the symmetric groups on the tensor algebra of a vector space. We define a chain of ideals of , j = 0,..., , such that is the linear span of sums of permutations with a common set of interior peaks and is the peak algebra. We extend the above results to , generalizing results of Schocker (the case j = 0). Aguiar supported in part by NSF grant DMS-0302423 Orellana supported in part by the Wilson Foundation     

New results on LR-designs and OLKTSs

LR-designs, introduced by Lei (2002) [10], play an important role in the recursive constructions of large sets of Kirkman triple systems. In this paper, we mainly present some new infinite families of LR-designs and overlarge sets of Kirkman triple systems.     

New results on affine invariant points

We prove a conjecture of B. Grünbaum stating that the set of affine invariant points of a convex body equals the set of points invariant under all affine linear symmetries of the convex body. As a consequence we give a short proof of the fact that the affine space of affine linear points is infinite dimensional. In particular, we show that the set of affine invariant points with no dual is of the second category. We investigate extremal cases for a class of symmetry measures. We show that the centers of the John and Löwner ellipsoids can be far apart and we give the optimal order for the extremal distance between the two centers.     

New results on multi-dimensional linear discriminant analysis

Fisher linear discriminant analysis is a well-known technique for dimensionality reduction and classification. The method was first formulated in 1936 by Fisher. In this paper we concentrate on three different formulations of the multi-dimensional problem. We provide a mathematical explanation why two of the formulations are equivalent and prove that this equivalency can be extended to a broader class of objective functions. The second contribution is a rate of convergence of a fixed point method for solving the third model.     

New results on restriction of Fourier multipliers

We develop an extension of the Transference methods introduced by R. Coifman and G. Weiss and apply it to study the problem of the restriction of Fourier multipliers between rearrangement invariant spaces, obtaining natural extensions of the classical de Leeuw’s result and its further extension to maximal Fourier multipliers due to C. Kenig and P. Tomas.     

New results on equivalent integer programming formulations

Methods are given for replacing a system of equations in nonnegative integer variables by a single equation with the same solution set. These results focus on easily specified coefficient conditions rather than on the use of bounds that must be calculated externally in order to produce the desired aggregation.     

New results on 3-domination critical graphs

A graph G is said to be 3-domination critical if its domination number γ(G) = 3 and γ(G + e) = 2 for any edge e not contained in G. In this paper we first establish some structural properties of 3-domination critical graphs with diameter equal to 3. In particular, this allows us to characterize a special family of 3-domination critical graphs which contains those with minimum degree one. Moreover, we show that if the minimum degree of a 3-domination critical graph G is at least 3, then α(G) ≤ κ(G) + 1 or G is superconnected, where α(G) is the independence number and κ(G) is the vertex-connectivity of G.     

New results on measures of maximal entropy

It has recently been demonstrated that there are strongly irreducible subshifts of finite type with more than one measure of maximal entropy. Here we obtain a number of results concerning the uniqueness of the measure of maximal entropy. In addition, we construct for anyd≥2 andk a strongly irreducible subshift of finite type ind dimensions with exactlyk ergodic (extremal) measures of maximal entropy. Ford≥3, we construct a strongly irreducible subshift of finite type ind dimensions with a continuum of ergodic measures of maximal entropy. Research supported in part by AFOSR grant # 91-0215 and NSF grant # DMS-9103738. Research supported by the Swedish National Science Foundation.     

New results on averaging theory and applications

The usual averaging theory reduces the computation of some periodic solutions of a system of ordinary differential equations, to find the simple zeros of an associated averaged function. When one of these zeros is not simple, i.e., the Jacobian of the averaged function in it is zero, the classical averaging theory does not provide information about the periodic solution associated to a non-simple zero. Here we provide sufficient conditions in order that the averaging theory can be applied also to non-simple zeros for studying their associated periodic solutions. Additionally, we do two applications of this new result for studying the zero–Hopf bifurcation in the Lorenz system and in the Fitzhugh–Nagumo system.     

New results on planar and directed multicuts

We show that the multicut problem is APX-hard in directed acyclic graphs, even with three source-sink pairs. We also show that it is tractable in planar graphs with a fixed number of terminals, and even FPT if all the terminals lie on the outer face.