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.     

More on Bounding Introspection in Modal Nonmonotonic Logics

Abstract By we denote the set of all propositional formulas. Let be the set of all clauses. Define . In Sec. 2 of this paper we prove that for normal modal logics , the notions of -expansions and -expansions coincide. In Sec. 3, we prove that if I consists of default clauses then the notions of -expansions for I and -expansions for I coincide. To this end, we first show, in Sec. 3, that the notion of -expansions for I is the same as that of -expansions for I. The project is supported by NSFC     

Weighted Non-Trivial Multiply Intersecting Families

Let n and r be positive integers. Suppose that a family satisfies F₁∩···∩F_r ≠∅ for all F₁, . . .,F_r ∈ and . We prove that there exists ε=ε(r) >0 such that holds for 1/2≤w≤1/2+ε if r≥13.     

The Reduced Minimum Modulus in <Emphasis>C</Emphasis><Superscript>*</Superscript>-Algebras

We define the reduced minimum modulus of a nonzero element a in a unital C ^*-algebra by . We prove that . Applying this result to and its closed two side ideal , we get that dist , and for any if RR = 0, where and is the quotient homomorphism and . These results generalize corresponding results in Hilbert spaces.     

Explicit Bounded-Degree Unique-Neighbor Concentrators

Here we solve an open problem considered by various researchers by presenting the first explicit constructions of an infinite family of bounded-degree ‘unique-neighbor’ concentrators Γ; i.e., there are strictly positive constants α and ε, such that all Γ = (X,Y,E(Γ)) ∈ satisfy the following properties. The output-set Y has cardinality times that of the input-set X, and for each subset S of X with no more than α|X| vertices, there are at least ε|S| vertices in Y that are adjacent in Γ to exactly one vertex in S. Also, the construction of is simple to specify, and each has fewer than edges. We then modify to obtain explicit unique-neighbor concentrators of maximum degree 3. * Supported by NSF grant CCR98210-58 and ARO grant DAAH04-96-1-0013.     

Properties of Auto- and Antiautomorphisms of Maximal Chain Structures and their Relations to i-Perspectivities

Let E be a non empty set, let P : = E × E, := {x × E|x ∈ E}, := {E × x|x ∈ E}, and := {C ∈ 2 ^P |∀X ∈ : |C ∩ X| = 1} and let . Then the quadruple resp. is called chain structure resp. maximal chain structure. We consider the maximal chain structure as an envelope of the chain structure . Particular chain structures are webs, 2-structures, (coordinatized) affine planes, hyperbola structures or Minkowski planes. Here we study in detail the groups of automorphisms , , , related to a maximal chain structure . The set of all chains can be turned in a group such that the subgroup of generated by the left-, by the right-translations and by ι the inverse map of is isomorphic to (cf. (2.14)).     

Tubes in three–dimensional projective spaces

A partial tube in PG(3, q) is a pair , where is a collection of mutually disjoint lines of PG(3, q) with the property that for each plane π of PG(3, q) through L, the intersection of π with the lines of is an arc. Here, we generalize the notion of partial tube allowing the ground field to be any algebraically closed field. To a generalized partial tube we will associate an irreducible surface of degree d in providing upper bounds on d. The authors were partially supported by MIUR and GNSAGA of INdAM (Italy).     

Transformations of Grassmannians preserving the class of base subsets

Let be a finite-dimensional projective space and be the Grassmannian consisting of all k-dimensional subspaces of . In the paper we show that transformations of sending base subsets to base subsets are induced by collineations of to itself or to the dual projective space . This statement generalizes the main result of the authors paper [19].     

On A Hypergraph Turán Problem Of Frankl

Let be the 2k-uniform hypergraph obtained by letting P₁, . . .,P_r be pairwise disjoint sets of size k and taking as edges all sets P_i∪P_j with i ≠ j. This can be thought of as the ‘k-expansion’ of the complete graph K_r: each vertex has been replaced with a set of size k. An example of a hypergraph with vertex set V that does not contain can be obtained by partitioning V = V1 ∪V₂ and taking as edges all sets of size 2k that intersect each of V₁ and V₂ in an odd number of elements. Let denote a hypergraph on n vertices obtained by this construction that has as many edges as possible. For n sufficiently large we prove a conjecture of Frankl, which states that any hypergraph on n vertices that contains no has at most as many edges as . Sidorenko has given an upper bound of for the Tur′an density of for any r, and a construction establishing a matching lower bound when r is of the form 2^p+1. In this paper we also show that when r=2^p+1, any -free hypergraph of density looks approximately like Sidorenko’s construction. On the other hand, when r is not of this form, we show that corresponding constructions do not exist and improve the upper bound on the Turán density of to , where c(r) is a constant depending only on r. The backbone of our arguments is a strategy of first proving approximate structure theorems, and then showing that any imperfections in the structure must lead to a suboptimal configuration. The tools for its realisation draw on extremal graph theory, linear algebra, the Kruskal–Katona theorem and properties of Krawtchouck polynomials. * Research supported in part by NSF grants DMS-0355497, DMS-0106589, and by an Alfred P. Sloan fellowship.     

Proof Of A Conjecture Of Erdős On Triangles In Set-Systems

A triangle is a family of three sets A,B,C such that A∩B, B∩C, C∩A are each nonempty, and . Let be a family of r-element subsets of an n-element set, containing no triangle. Our main result implies that for r ≥ 3 and n ≥ 3r/2, we have This settles a longstanding conjecture of Erdős [7], by improving on earlier results of Bermond, Chvátal, Frankl, and Füredi. We also show that equality holds if and only if consists of all r-element subsets containing a fixed element. Analogous results are obtained for nonuniform families.     

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     

On a Poincaré-type Inequality for Energy Forms in L p

We consider Dirichlet spaces ( ) in L ² and more general energy forms in L ^p , . For the latter we introduce the notions of an extended ’Dirichlet’ space and a transient form. Under the assumption that , resp. , are compactly embedded in L ², resp. L ^p , we prove a Poincaré inequality for transient (Dirichlet) forms. If both and its adjoint are sub-Markovian semigroups, we show that the transience of T _t is independent of ) and that it is implied by the transience of the energy form of and the form belonging to .     

The general dévissage theorem for Witt groups of schemes

Let be a closed subscheme of the noetherian scheme X. We show that if X has a dualizing complex then there exists a dualizing complex of Z such that there is an isomorphism of coherent Witt groups for all . Received: 3 March 2006     

Discrepancy After Adding A Single Set

We show that the hereditary discrepancy of a hypergraph on n points increases by a factor of at most O(log n) when one adds a new edge to .     

Lie and Jordan Ideals in Reflexive Algebras

A CDCSL algebra is a reflexive operator algebra with completely distributive and commutative subspace lattice. In this paper, we show, for a weakly closed linear subspace of a CDCSL algebra , that is a Lie ideal if and only if for all invertibles A in , and that is a Jordan ideal if and only if it is an associative ideal.     

Integral Equations on Function Spaces and Dichotomy on the Real Line

The purpose of this paper is to give new and general characterizations for uniform dichotomy and uniform exponential dichotomy of evolution families on the real line. We consider two general classes denoted and and we prove that if V,W are Banach function spaces with and , then the admissibility of the pair for an evolution family implies the uniform dichotomy of . In addition, we consider a subclass and we prove that if , then the admissibility of the pair implies the uniform exponential dichotomy of the family . This condition becomes necessary if . Finally, we present some applications of the main results.     

The Maximum Size Of Graphs With A Unique<Emphasis Type="Italic">k</Emphasis>- Factor

For suitable positive integers n and k let m(n, k) denote the maximum number of edges in a graph of order n which has a unique k-factor. In 1964, Hetyei and in 1984, Hendry proved for even n and , respectively. Recently, Johann confirmed the following conjectures of Hendry: for and kn even and for n = 2kq, where q is a positive integer. In this paper we prove for and kn even, and we determine m(n, 3).     

Remarks on balance in generalized Tate cohomology

We consider two pairs of complete hereditary cotorsion theories on the category of left R-modules, such that We prove that for any left R-modules M, N and for any n ≧ 1, the generalized Tate cohomology modules can be computed either using a left of M and a left of M or using a right a right of N. Received: 17 December 2004     

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