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.     

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.     

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.     

Homological Connectivity Of Random 2-Complexes

Let Δ_n−1 denote the (n − 1)-dimensional simplex. Let Y be a random 2-dimensional subcomplex of Δ_n−1 obtained by starting with the full 1-dimensional skeleton of Δ_n−1 and then adding each 2−simplex independently with probability p. Let denote the first homology group of Y with mod 2 coefficients. It is shown that for any function ω(n) that tends to infinity

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.     

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 .     

Translation Generalized Quadrangles In Even Characteristic

In this paper, we first introduce new objects called “translation generalized ovals” and “translation generalized ovoids”, and make a thorough study of these objects. We then obtain numerous new characterizations of the of Tits and the classical generalized quadrangle in even characteristic, including the complete classification of 2-transitive generalized ovals for the even case. Next, we prove a new strong characterization theorem for the of Tits. As a corollary, we obtain a purely geometric proof of a theorem of Johnson on semifield flocks. * The second author is a Postdoctoral Fellow of the Fund for Scientific Research—Flanders (Belgium).     

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     

A Topological View of Ramsey Families of Finite Subsets of Positive Integers

If is an initially hereditary family of finite subsets of positive integers (i.e., if and G is initial segment of F then ) and M an infinite subset of positive integers then we define an ordinal index . We prove that if is a family of finite subsets of positive integers such that for every the characteristic function χ_F is isolated point of the subspace

Ultraproducts of real interpolation spaces between L p -spaces

Let , be a family of compatible couples of L^p-spaces. We show that, given a countably incomplete ultrafilter in , the ultraproduct of interpolation spaces defined by the real method is isomorphic to the direct sum of an interpolation space of type , an intermediate K?the space between and being a purely atomic measure space, and a K?the function space K(Ω₃) defined on some purely non atomic measure space (Ω₃, ν₃) in such a way that Ω₂ ∪ Ω₃ ≠∅. The research of first and third authors is partially supported by the MEC and FEDER project MTM2004-02262 and AVCIT group 03/050.     

The 3D Inverse Problem of the Wave Equation for a General Multi-connected Vibrating Membrane with a Finite Number of Piecewise Smooth Boundary Conditions

The trace of the wave kernel μ（t） =∑ω=1^∞ exp（-itEω^1/2）, where {Eω}ω^∞=1 are the eigenvalues of the negative Laplacian -△↓2 = -∑k^3=1 （δ/δxk）^2 in the （x^1, x^2, x^3）-space, is studied for a variety of bounded domains, where -∞ 〈 t 〈 ∞ and i= √-1. The dependence of μ （t） on the connectivity of bounded domains and the Dirichlet, Neumann and Robin boundary conditions are analyzed. Particular attention is given for a multi-connected vibrating membrane Ω in Ra surrounded by simply connected bounded domains Ω j with smooth bounding surfaces S j （j = 1,……, n）, where a finite number of piecewise smooth Dirichlet, Neumann and Robin boundary conditions on the piecewise smooth components Si^＊ （i = 1 ＋ kj-1,……, kj） of the bounding surfaces S j are considered, such that S j = Ui-1＋kj-1^kj Si^＊, where k0=0. The basic problem is to extract information on the geometry Ω by using the wave equation approach from a complete knowledge of its eigenvalues. Some geometrical quantities of Ω （e.g. the volume, the surface area, the mean curvuture and the Gaussian curvature） are determined from the asymptotic expansion ofexpansion of μ（t） for small │t│.     

Polynomial Lym Inequalities

For a Sperner family A 2^[n] let A _i denote the family of all i-element sets in A. We sharpen the LYM inequality by adding to the LHS all possible products of fractions , with suitable coefficients. A corresponding inequality is established also for the linear lattice and the lattice of subsets of a multiset (with all elements having the same multiplicity).* Research supported by the Sonderforschungsbereich 343 Diskrete Strukturen in der Mathematik, University of Bielefeld.     

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.     

Addendum To Schrijver's Work On Minimum Permanents

Let denote the set of n×n binary matrices which have each row and column sum equal to k. For 2≤k≤n→∞ we show that is asymptotically equal to (k−1)^k−1k^2−k. This confirms Conjecture 23 in Minc's catalogue of open problems. * Written while the author was employed by the Department of Computer Science at the Australian National University.     

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.     

A Sharp Bound for the Number of Sets that Pairwise Intersect at <Emphasis Type="Italic">k</Emphasis> Positive Values

In this paper we prove that if is a set of k positive integers and {A ₁, ..., A _m } is a family of subsets of an n-element set satisfying , for all 1 i < j m, then . The case k = 1 was proven 50 years ago by Majumdar.     

Canonical Partitions Of Universal Structures

  Let be a universal binary countable homogeneous structure and n∈ω. We determine the equivalence relation on [U]ⁿ with the smallest number of equivalence classes r so that each one of the classes is indivisible. As a consequence we obtain

Lifts, Discrepancy and Nearly Optimal Spectral Gap*

We present a new explicit construction for expander graphs with nearly optimal spectral gap. The construction is based on a series of 2-lift operations. Let G be a graph on n vertices. A 2-lift of G is a graph H on 2n vertices, with a covering map π :H →G. It is not hard to see that all eigenvalues of G are also eigenvalues of H. In addition, H has n “new” eigenvalues. We conjecture that every d-regular graph has a 2-lift such that all new eigenvalues are in the range (if true, this is tight, e.g. by the Alon–Boppana bound). Here we show that every graph of maximal degree d has a 2-lift such that all “new” eigenvalues are in the range for some constant c. This leads to a deterministic polynomial time algorithm for constructing arbitrarily large d-regular graphs, with second eigenvalue . The proof uses the following lemma (Lemma 3.3): Let A be a real symmetric matrix with zeros on the diagonal. Let d be such that the l₁ norm of each row in A is at most d. Suppose that for every x,y ∈{0,1}ⁿ with ‹x,y›=0. Then the spectral radius of A is O(α(log(d/α)+1)). An interesting consequence of this lemma is a converse to the Expander Mixing Lemma. * This research is supported by the Israeli Ministry of Science and the Israel Science Foundation.     

Set Systems with few Disjoint Pairs

Let X = {1, . . . , n}, and let be a family of subsets of X. Given the size of , at least how many pairs of elements of must be disjoint? In this paper we give a lower bound for the number of disjoint pairs in . The bound we obtain is essentially best possible. In particular, we give a new proof of a result of Frankl and of Ahlswede, that if satisfies then contains at least as many disjoint pairs as X^(r).The situation is rather different if we restrict our attention to : then we are asking for the minimum number of edges spanned by a subset of the Kneser graph of given size. We make a conjecture on this lower bound, and disprove a related conjecture of Poljak and Tuza on the largest bipartite subgraph of the Kneser graph.* Research partially supported by NSF grant DMS-9971788     

Remarks on ample vector bundles of curve genus two

Let be an ample vector bundle of rank n – 1 on a smooth complex projective variety X of dimension n≥ 3 such that X is a -bundle over and that for any fiber F of the bundle projection . The pairs with = 2 are classified, where is the curve genus of . This allows us to improve some previous results. Received: 13 June 2006