Supersaturation For Ramsey-Turán Problems

For an l-graph , the Turán number is the maximum number of edges in an n-vertex l-graph containing no copy of . The limit is known to exist [8]. The Ramsey–Turán density is defined similarly to except that we restrict to only those with independence number o(n). A result of Erdős and Sós [3] states that as long as for every edge E of there is another edge E′of for which |E∩E′|≥2. Therefore a natural question is whether there exists for which . Another variant proposed in [3] requires the stronger condition that every set of vertices of of size at least εn (0<ε<1) has density bounded below by some threshold. By definition, for every . However, even is not known for very many l-graphs when l>2. We prove the existence of a phenomenon similar to supersaturation for Turán problems for hypergraphs. As a consequence, we construct, for each l≥3, infinitely many l-graphs for which . We also prove that the 3-graph with triples 12a, 12b, 12c, 13a, 13b, 13c, 23a, 23b, 23c, abc, satisfies . The existence of a hypergraph satisfying was conjectured by Erdős and Sós [3], proved by Frankl and R?dl [6], and later by Sidorenko [14]. Our short proof is based on different ideas and is simpler than these earlier proofs. * Research supported in part by the National Science Foundation under grants DMS-9970325 and DMS-0400812, and an Alfred P. Sloan Research Fellowship. † Research supported in part by the National Science Foundation under grants DMS-0071261 and DMS-0300529.     

The normal subgroup structure of the extended Hecke groups

We consider the extended Hecke groups generated by T(z) = −1/z, S(z) = −1/(z + λ) and R(z) = 1/z with λ ≥ 2. In this paper, firstly, we study the fundamental region of the extended Hecke groups . Then, we determine the abstract group structure of the commutator subgroups , the even subgroup , and the power subgroups of the extended Hecke groups . Also, finally, we give some relations between them.     

Network Design Via Iterative Rounding Of Setpair Relaxations

A typical problem in network design is to find a minimum-cost sub-network H of a given network G such that H satisfies some prespecified connectivity requirements. Our focus is on approximation algorithms for designing networks that satisfy vertex connectivity requirements. Our main tool is a linear programming relaxation of the following setpair formulation due to Frank and Jordan: a setpair consists of two subsets of vertices (of the given network G); each setpair has an integer requirement, and the goal is to find a minimum-cost subset of the edges of G sucht hat each setpair is covered by at least as many edges as its requirement. We introduce the notion of skew bisupermodular functions and use it to prove that the basic solutions of the linear program are characterized by “non-crossing families” of setpairs. This allows us to apply Jain’s iterative rounding method to find approximately optimal integer solutions. We give two applications. (1) In the k-vertex connectivity problem we are given a (directed or undirected) graph G=(V,E) with non-negative edge costs, and the task is to find a minimum-cost spanning subgraph H such that H is k-vertex connected. Let n=|V|, and let ε<1 be a positive number such that k≤(1−ε)n. We give an -approximation algorithm for both problems (directed or undirected), improving on the previous best approximation guarantees for k in the range . (2)We give a 2-approximation algorithm for the element connectivity problem, matching the previous best approximation guarantee due to Fleischer, Jain and Williamson. * Supported in part by NSERC researchgran t OGP0138432. † Supported in part by NSF Career Award CCR-9875024.     

On the Range of the Aluthge Transform

Let be the algebra of all bounded linear operators on a complex separable Hilbert space For an operator let be the Aluthge transform of T and we define for all where T = U|T| is a polar decomposition of T. In this short note, we consider an elementary property of the range of Δ. We prove that R(Δ) is neither closed nor dense in However R(Δ) is strongly dense if is infinite dimensional. An erratum to this article is available at .     

Polar Sets and Relative Dimension for Generalized Brownian Sheet

Let{(t);t∈R_ ~N}be a d-dimensional N-parameter generalized Brownian sheet.Necessaryand sufficient conditions for a compact set E×F to be a polar set for(t,(t))are proved.It is also provedthat if 2N≤αd,then for any compact set ER_>~N,d-2/2 Dim E≤inf{dimF:F ∈ B(R~d),P{(E)∩F≠φ}>0}≤d-2/β DimE,and if 2N>αd,then for any compact set FR~d\{0},α/2(d-DimF)≤inf{dimE:E∈B(R_>~N),P{(E)∩F≠φ}>0}≤β/2(d-DimF),where B(R~d)and B(R_>~N)denote the Borel σ-algebra in R~d and in R_>~N respectively,dim and Dim are Hausdorffdimension and Packing dimension respectively.     

Hyperbolic Mapping Classes and Their Lifts on the Bers Fiber Space

Let S be a Riemann surface with genus p and n punctures. Assume that 3p - 3 n ＞ 0 and n ≥ 1. Let a be a puncture of S and let (～S) = S ∪ {a}. Then all mapping classes in the mapping class group Mods that fixes the puncture a can be projected to mapping classes of Mod(～S) under the forgetful map. In this paper the author studies the mapping classes in Mods that can be projected to a given hyperbolic mapping class in Mod(～S).     

Wavelets and Geometric Structure for Function Spaces

Abstract With Littlewood–Paley analysis, Peetre and Triebel classified, systematically, almost all the usual function spaces into two classes of spaces: Besov spaces and Triebel–Lizorkin spaces ; but the structure of dual spaces of is very different from that of Besov spaces or that of Triebel–Lizorkin spaces, and their structure cannot be analysed easily in the Littlewood–Paley analysis. Our main goal is to characterize in tent spaces with wavelets. By the way, some applications are given: (i) Triebel–Lizorkin spaces for p = ∞ defined by Littlewood–Paley analysis cannot serve as the dual spaces of Triebel–Lizorkin spaces for p = 1; (ii) Some inclusion relations among these above spaces and some relations among and L ¹ are studied. Supported by NNSF of China (Grant No. 10001027)     

Decomposing Berge Graphs Containing No Proper Wheel, Long Prism Or Their Complements

In this paper we show that, if G is a Berge graph such that neither G nor its complement contains certain induced subgraphs, named proper wheels and long prisms, then either G is a basic perfect graph( a bipartite graph, a line graph of a bipartite graph or the complement of such graphs) or it has a skew partition that cannot occur in a minimally imperfect graph. This structural result implies that G is perfect. This work was supported in part by NSF grant DMI-0352885 and ONR grant N00014-03-1-0188.     

Some generalizations of Knopp's identity*

For integers a, b and n > 0, define

Packing Non-Returning <Emphasis Type="Italic">A</Emphasis>-Paths*

Chudnovsky et al. gave a min-max formula for the maximum number of node-disjoint nonzero A-paths in group-labeled graphs [1], which is a generalization of Mader's theorem on node-disjoint A-paths [3]. Here we present a further generalization with a shorter proof. The main feature of Theorem 2.1 is that parity is “hidden” inside , which is given by an oracle for non-bipartite matching. * Research is supported by OTKA grants T 037547 and TS 049788, by European MCRTN Adonet, Contract Grant No. 504438 and by the Egerváry Research Group of the Hungarian Academy of Sciences. † The author is a member of the Egerváry Research Group (EGRES).     

Small Complete Arcs in Projective Planes

In the late 1950s, B. Segre introduced the fundamental notion of arcs and complete arcs [48,49]. An arc in a nite projective plane is a set of points with no three on a line and it is complete if cannot be extended without violating this property. Given a projective plane , determining , the size of its smallest complete arc, has been a major open question in finite geometry for several decades. Assume that has order q, it was shown by Lunelli and Sce [41], more than 40 years ago, that . Apart from this bound, practically nothing was known about , except for the case is the Galois plane. For this case, the best upper bound, prior to this paper, was O(q ^3/4) obtained by Sznyi using the properties of the Galois field GF(q).In this paper, we prove that for any projective plane of order q, where c is a universal constant. Together with Lunelli-Sces lower bound, our result determines up to a polylogarithmic factor. Our proof uses a probabilistic method known as the dynamic random construction or Rödls nibble. The proof also gives a quick randomized algorithm which produces a small complete arc with high probability.The key ingredient of our proof is a new concentration result, which applies for non-Lipschitz functions and is of independent interest.* Research supported in part by grant RB091G-VU from UCSD, by NSF grant DMS-0200357 and by an A. Sloan fellowship.Part of this work was done at AT&T Bell Labs and Microsoft Research     

Semisimplicity of Some Class of Operator Algebras on Banach Space

Let G be a locally compact abelian group and let be a representation of G by means of isometries on a Banach space. We define W_T as the closure with respect to the weak operator topology of the set where is the Fourier transform of f ∈L¹(G) with respect to the group T. Then W_T is a commutative Banach algebra. In this paper we study semisimlicity problem for such algebras. The main result is that if the Arveson spectrum sp(T) of T is scattered (i.e. it does not contain a nonempty perfect subset) then the algebra W_T is semisimple. Some related problems are also discussed.     

Lifting Unitary Elements with Application to Approximately Inner Automorphisms

Let A be a separable unital nuclear simple C＊-algebra with torsion K0 （A）, free K1 （A） and with the UCT. Let T ： A→M（K）/K be a unital homomorphism. We prove that every unitary element in the commutant of T（A） is an exponent, thus it is liftable. We also prove that each automorphism α on E with α ∈ Aut0（A） is approximately inner, where E is a unital essential extension of A by K and α is the automorphism on A induced by α.     

Symmetrization of Closure Operators and Visibility

For an arbitrary set E and a given closure operator , we want to construct a symmetric closure operator via some – possibly infinite – iteration process. If E is finite, the corresponding symmetric closure operator . defines a matroid. If and is the convex closure operator, turns out to be the affine closure operator. Moreover, we apply the symmetrization process to closure operators induced by visibility. Received March 9, 2005     

Pseudo unitary conformal groups and Clifford algebras for standard pseudo hermitian spaces

This paper, self-contained, deals with pseudo-unitary spin geometry. First, we present pseudo-unitary conformal structures over a 2n-dimensional complex manifold V and the corresponding projective quadrics for standard pseudo-hermitian spaces H_p,q. Then we develop a geometrical presentation of a compactification for pseudo-hermitian standard spaces in order to construct the pseudo-unitary conformal group of H_p,q. We study the topology of the projective quadrics and the “generators” of such projective quadrics. Then we define the space S of spinors canonically associated with the pseudo-hermitian scalar product of signature (2ⁿ⁻¹, 2ⁿ⁻¹). The spinorial group Spin U(p,q) is imbedded into SU(2ⁿ⁻¹, 2ⁿ⁻¹). At last, we study the natural imbeddings of the projective quadrics      

Hoermander＇s Multipliers for the Weighted Herz-type Hardy Spaces

In this article, we apply the molecular characterization of the weighted Hardy space developed by the first two authors to show the boundedness of Hormander multiplier on the weighted Herz-type Hardy spaces HK^α,p 2（｜x｜^t; ｜x｜^t） and HK^α,P 2（｜x｜^t; ｜x｜^t）.     

Effective Reducibility of a Class of Linear Differential Equations with Quasiperiodic Coefficients

In this paper we consider the effective reducibility of the following linear differentialequation: x = (A ∈Q(t,∈))x, |∈| ≤ ∈0, where A is a constant matrix, Q(t,e) is quasiperiodic in t, and e is a small perturbation parameter. We prove that if the eigenvalues of A and the basic frequencies of Q satisfy some non-resonant conditions, the linear differential equation can be reduced to y = (A^*(∈) R^*(t, ∈))y, |∈| ≤ ∈o, where R^* is exponentially small in ∈.     

Matching Polynomials And Duality

Let G be a simple graph on n vertices. An r-matching in G is a set of r independent edges. The number of r-matchings in G will be denoted by p(G, r). We set p(G, 0) = 1 and define the matching polynomial of G by and the signless matching polynomial of G by .It is classical that the matching polynomials of a graph G determine the matching polynomials of its complement . We make this statement more explicit by proving new duality theorems by the generating function method for set functions. In particular, we show that the matching functions and are, up to a sign, real Fourier transforms of each other.Moreover, we generalize Foatas combinatorial proof of the Mehler formula for Hermite polynomials to matching polynomials. This provides a new short proof of the classical fact that all zeros of µ(G, x) are real. The same statement is also proved for a common generalization of the matching polynomial and the rook polynomial.     

Multilinear Singular Integrals with Rough Kernel

For a class of multilinear singular integral operators T _A ,