Distortion coefficients for cryptocontractions

For complex Hilbert space H of d dimensions and for any number K ? 1, we may define m(K, d) as the least number with the following property: if 6p(T)6 ? K for all polynomials p mapping the complex unit disk into itself, then the operator T may be made a contraction by changing to a new norm |·|, derived from an inner product, such that

$\text{6h6 ? |h| ?m(K,d)6h6 (h∈H).}$

It is a long-standing open question whether m(K, d) has a finite bound independent of d. The present paper studies this and related questions and provides, in particular, an explicit estimate for m(K,d)—which, however, grows with d.     

A degree condition for the circumference of a graph

We present a new condition on the degree sums of a graph that implies the existence of a long cycle. Let c(G) denote the length of a longest cycle in the graph G and let m be any positive integer. Suppose G is a 2-connected graph with vertices x₁,…,x_n and edge set E that satisfies the property that, for any two integers j and k with j < k, x_jx_k ? E, d(x_i) ? j and d(x_k) ? K - 1, we have (1) d(x_i) + d(x_k ? m if j + k ? n and (2) if j + k < n, either m ? n or d(x_j) + d(x_k) ? min(K + 1,m). Then c(G) ? min(m, n). This result unifies previous results of J.C. Bermond and M. Las Vergnas, respectively.     

On local Poincaré via transportation

It is shown that curvature-dimension bounds CD(N,K) for a metric measure space (X,d,m) in the sense of Sturm imply a weak L ¹-Poincaré-inequality provided (X,d) has m-almost surely no branching points. Work supported by the Alexander von Humboldt-Foundation (AvH).     

The automorphism groups of the Delsarte-Goethals codes

We determine the automorphism groups of the Delsarte-Goethals codesDG(m, d) (m=2t+26, 2dt). The groups that we obtain are the same as those of the Kerdock codesK(m) of the same length.LAMIFA Université de Picardie, France.     

The upper bound of the $${{\rm L}_{\mu}^2}$$ spectrum

Let M be an n-dimensional complete non-compact Riemannian manifold, dμ = e ^h (x)dV(x) be the weighted measure and \triangle_m{\triangle_{\mu}} be the weighted Laplacian. In this article, we prove that when the m-dimensional Bakry–émery curvature is bounded from below by Ric _m ≥ −(m − 1)K, K ≥ 0, then the bottom of the L_m²{{\rm L}_{\mu}^2} spectrum λ₁(M) is bounded by

On a conjecture of R. E. Miles about the convex hull of random points

Denoty byp _d+i (B _d ,d+m) the probability that the convex hull ofd+m points chosen independently and uniformly from ad-dimensional ballB _d possessesd+i(i=1,...,m) vertices. We prove Mile's conjecture that, given any integerm, p _d+m (B _d ,d+m)»1 asd». This is obvious form=1 and was shown by Kingman form=2 and by Miles form=3. Further, a related result by Miles is generalized, and several consequences are deduced.Dedicated to Professor E. Halwaka on the occasion of his seventieth     

On cliques and bicliques

For integers m, n ≥ 2, let g(m, n) be the minimum order of a graph, where every vertex belongs to both a clique K_m of order m and a biclique K(n, n). We show that g(m, n) = 2(m + n − 2) if m ≤ n − 2. Furthermore, for m ≥ n − 1, we establish that ≡ 0 mod(n − 1) or, if m is sufficiently large and is not an integer. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 60–66, 2000     

Tilting modules for classical groups and howe duality in positive characteristics

We use the theory of tilting modules for algebraic groups to propose a characteristic free approach to “Howe duality” in the exterior algebra. To any series of classical groups (general linear, symplectic, orthogonal, or spinor) over an algebraically closed field k, we set in correspondence another series of classical groups (usually the same one). Denote byG ₁(m) the group of rankm from the first series and byG ₂(n) the group of rankn from the second series. For any pair (G ₁(m), G₂(n)) we construct theG ₁(m)×G₂(n)-module M(m, n). The construction of M(m, n) is independent of characteristic; for chark=0, the actions ofG ₁(m) andG ₂(n) on M(m, n) form a reductive dual pair in the sense of Howe. We prove that M(m, n) is a tiltingG ₁(m)-andG ₂(n)-module and that End _{G 1}(m) M(m, n) is generated byG ₂(n) and vice versa. The existence of such a module provides much information about the relations between the categoryK ₁(m, n) of rationalG ₁(m)-modules with highest weights bounded in a certain sense byn and the categoryK ₂(m, n) of rationalG ₂(n)-modules with highest weights bounded in the same sense bym. More specifically, we prove that there is a bijection of the set of dominant weights ofG ₁(m)-modules fromK ₁(m, n) to the set of dominant weights ofG ₂(m)-modules fromK ₂(m, n) such that Ext groups for inducedG ₁(m)-modules fromK ₁(m, n) are isomorphic to Ext groups for corresponding Weyl modules overG ₂(n). Moreover, the derived categoriesD ^bK₁(m, n) andD ^bK₂(m, n) appear to be equivalent. We also use our study of the modules M(m, n) to find generators and relations for the algebra of allG-invariants in , whereG=GL _m, Sp_2m, O_m and V is the naturalG-module. Research was supported in part by Grant M7N000/M7N300 from the International Science Foundation and Russian Government and by INTAS Grant 94-4720. Research was supported in part by Grant M8H000/M8H300 from the International Science Foundation and Russian Government and by INTAS Grant 94-4720.     

Irredundance in inflated graphs

The inflation G_I of a graph G with n(G) vertices and m(G) edges is obtained by replacing every vertex of degree d of G by a clique K_d. We study the lower and upper irredundance parameters ir and IR of an inflation. We prove in particular that if γ denotes the domination number of a graph, γ(G_I) − ir(G_I) can be arbitrarily large, IR(G_I) ≤ m(G) and IR(G_I) ≤ n²(G)/4. These results disprove a conjecture of Dunbar and Haynes (Congr. Num. 118 (1996), 143–154) and answer another open question. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 97–104, 1998     

On the generalized critical values of a polynomial mapping

 Let be a polynomial dominant mapping and let deg f _i ≤d. We prove that the set K(f) of generalized critical values of f is contained in the algebraic hypersurface of degree at most D=(d+s(m−1)(d−1)) ⁿ , where . This implies in particular that the set B(f) of bifurcations points of f is contained in the hypersurface of degree at most D=(d+s(m−1)(d−1)) ⁿ . We give also an algorithm to compute the set K(f) effectively. Received: 11 June 2001 / Revised version: 1 July 2002 Published online: 24 January 2003 The author is partially supported by the KBN grant 2 PO3A 017 22. Mathematics Subject Classification (2000): 14D06, 14Q20, 51N10, 51N20, 15A04     

A problem in extremal quasiconformal extensions

A constantK ₀ ^(m) (h) is introduced for every quasisymmetric mappingh of the unit circle and every integerm≥4 which contains the constantK ₀(h) (indicated by the change in module of the quadrilaterals with vertices on the circle) as a special case. A necessary and sufficient condition is established forK ₀ ^(m) (h) =K ₁(h). It is shown that there are infinitely many quasisymmetric mappings of the unit circle having the property thatK ₀ ^(m) (h)<K ₁(h), wherek ₁(h) is the maximal dilatation ofh.     

On the log-concavity of Hilbert series of Veronese subrings and Ehrhart series

For every positive integer n, consider the linear operator U _n on polynomials of degree at most d with integer coefficients defined as follows: if we write ${\frac{h(t)}{(1 - t)^{d + 1}}=\sum_{m \geq 0} g(m) \, t^{m}}For every positive integer n, consider the linear operator U _n on polynomials of degree at most d with integer coefficients defined as follows: if we write \frach(t)(1 - t)^{d + 1}=?_{m 3 0} g(m)  t^m{\frac{h(t)}{(1 - t)^{d + 1}}=\sum_{m \geq 0} g(m) \, t^{m}} , for some polynomial g(m) with rational coefficients, then \fracU_nh(t)(1- t)^d+1 = ?_{m 3 0}g(nm)  t^m{\frac{{\rm{U}}_{n}h(t)}{(1- t)^{d+1}} = \sum_{m \geq 0}g(nm) \, t^{m}} . We show that there exists a positive integer n _d , depending only on d, such that if h(t) is a polynomial of degree at most d with nonnegative integer coefficients and h(0) = 1, then for n ≥ n _d , U _n h(t) has simple, real, negative roots and positive, strictly log concave and strictly unimodal coefficients. Applications are given to Ehrhart δ-polynomials and unimodular triangulations of dilations of lattice polytopes, as well as Hilbert series of Veronese subrings of Cohen–Macauley graded rings.     

The number of K m,m -free graphs

A graph is called H-free if it contains no copy of H. Denote by f _n (H) the number of (labeled) H-free graphs on n vertices. Erdős conjectured that f _n (H) ≤ 2^{(1+o(1))ex(n,H)}. This was first shown to be true for cliques; then, Erdős, Frankl, and R?dl proved it for all graphs H with χ(H)≥3. For most bipartite H, the question is still wide open, and even the correct order of magnitude of log₂ f _n (H) is not known. We prove that f _n (K _m,m ) ≤ 2 ^O (n ^2−1/m ) for every m, extending the result of Kleitman and Winston and answering a question of Erdős. This bound is asymptotically sharp for m∈{2,3}, and possibly for all other values of m, for which the order of ex(n,K _m,m ) is conjectured to be Θ(n ^2−1/m ). Our method also yields a bound on the number of K _m,m -free graphs with fixed order and size, extending the result of Füredi. Using this bound, we prove a relaxed version of a conjecture due to Haxell, Kohayakawa, and Łuczak and show that almost all K _3,3-free graphs of order n have more than 1/20·ex(n,K _3,3) edges.     

On the rate of points in projective spaces

The rate of a standard gradedK-algebraR is a measure of the growth of the shifts in a minimal free resolution ofK as anR-module. It is known that rate(R)=1 if and only ifR is Koszul and that rate(R) ≥m(I)−1 wherem(I) denotes the highest degree of a generator of the defining idealI ofR. We show that the rate of the coordinate ring of certain sets of pointsX of the projective space P ⁿ is equal tom(I)−1. This extends a theorem of Kempf. We study also the rate of algebras defined by a space of forms of some fixed degreed and of small codimension.     

Some extremal results in cochromatic and dichromatic theory

For a graph G, the cochromatic number of G, denoted z(G), is the least m for which there is a partition of the vertex set of G having order m. where each part induces a complete or empty graph. We show that if {G_n} is a family of graphs where G_n has o(n² log²(n)) edges, then z(G_n) = o(n). We turn our attention to dichromatic numbers. Given a digraph D, the dichromatic number of D is the minimum number of parts the vertex set of D must be partitioned into so that each part induces an acyclic digraph. Given an (undirected) graph G, the dichromatic number of G, denoted d(G), is the maximum dichromatic number of all orientations of G. Let m be an integer; by d(m) we mean the minimum size of all graphs G where d(G) = m. We show that d(m) = θ(m² ln²(m)).     

Asymptotic consistency of fixed-width sequential confidence intervals for a multiple regression function

Summary Letm _n (x) be the recursive kernel estimator of the multiple regression functionm(x)=E[Y|X=x]. For given α (0<α<1) andd>0 we define a certain class of stopping timesN=N(α,d, x) and takeI _N,d (x)=[m _N (x)−d, m _N (x)+d] as a 2d-width confidence interval form(x) at a given pointx. In this paper it is shown that the probability P{m(x)∈I _N,d (x)} converges to α asd tends to zero.     

A discrete version of Koldobsky’s slicing inequality

Let #K be a number of integer lattice points contained in a set K. In this paper we prove that for each d ∈ N there exists a constant C(d) depending on d only, such that for any origin-symmetric convex body K ? R ^d containing d linearly independent lattice points

$$\# K \leqslant C\left( d \right)\max \left( {\# \left( {K \cap H} \right)} \right)vo{l_d}{\left( K \right)^{\frac{{d - m}}{d}}},$$

where the maximum is taken over all m-dimensional subspaces of R ^d . We also prove that C(d) can be chosen asymptotically of order O(1) ^d d ^d?m . In particular, we have order O(1) ^d for hyperplane slices. Additionally, we show that if K is an unconditional convex body then C(d) can be chosen asymptotically of order O(d) ^d?m .

     

On Translational Clouds for a Convex Body

For a d-dimensional convex body K let C(K) denote the minimum size of translational clouds for K. That is, C(K) is the minimum number of mutually non-overlapping translates of K which do not overlap K and block all the light rays emanating from any point of K. In this paper we prove the general upper bound . Furthermore, for an arbitrary centrally symmetric d-dimensional convex body S we show . Finally, for the d-dimensional ball B^d we obtain the bounds .     

On the connectivity of unit distance graphs

For a number fieldK , consider the graphG(K^d), whose vertices are elements ofK ^d, with an edge between any two points at (Euclidean) distance 1. We show thatG(K²) is not connected whileG(K^d) is connected ford 5. We also give necessary and sufficient conditions for the connectedness ofG(K³) andG(K⁴).     

Characterization of a class of triangle-free graphs with a certain adjacency property

Let m and n be nonnegative integers. Denote by P(m,n) the set of all triangle-free graphs G such that for any independent m-subset M and any n-subset N of V(G) with M ∩ N = Ø, there exists a unique vertex of G that is adjacent to each vertex in M and nonadjacent to any vertex in N. We prove that if m ? 2 and n ? 1, then P(m,n) = Ø whenever m ? n, and P(m,n) = {K_m,n+1} whenever m > n. We also have P(1,1) = {C₅} and P(1,n) = Ø for n ? 2. In the degenerate cases, the class P(0,n) is completely determined, whereas the class P(m,0), which is most interesting, being rich in graphs, is partially determined.