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.     

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.     

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.     

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.     

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.     

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.     

The Extremal Function For Noncomplete Minors

  We investigate the maximum number of edges that a graph G can have if it does not contain a given graph H as a minor (subcontraction). Let

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).     

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.     

On the Order of Magnitude of the Divisor Function

Let D be an increasing sequence of positive integers, and consider the divisor functions： d（n, D） =∑d｜n,d∈D,d≤√n1, d2（n,D）=∑[d,δ]｜n,d,δ∈D,[d,δ]≤√n1, where [d,δ]=1.c.m.（d,δ）. A probabilistic argument is introduced to evaluate the series ∑n=1^∞and（n,D） and ∑n=1^∞and2（n,D）.     

Colorings Of Plane Graphs With No Rainbow Faces

We prove that each n-vertex plane graph with girth g≥4 admits a vertex coloring with at least ⌈n/2⌉+1 colors with no rainbow face, i.e., a face in which all vertices receive distinct colors. This proves a conjecture of Ramamurthi and West. Moreover, we prove for plane graph with girth g≥5 that there is a vertex coloring with at least if g is odd and if g is even. The bounds are tight for all pairs of n and g with g≥4 and n≥5g/2−3. * Supported in part by the Ministry of Science and Technology of Slovenia, Research Project Z1-3129 and by a postdoctoral fellowship of PIMS. ** Institute for Theoretical Computer Science is supported by Ministry of Education of CzechR epublic as project LN00A056.     

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).     

Weak Hopf Algebras Corresponding to Borcherds-Cartan Matrices

Let y be a generalized Kac-Moody algebra with an integral Borcherds-Cartan matrix. In this paper, we define a d-type weak quantum generalized Kac-Moody algebra wUq^d（y）, which is a weak Hopf algebra. We also study the highest weight module over the weak quantum algebra wUdq^d（y） and weak A-forms of wUq^d（y）.     

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.     

Upper Bounds on Character Sums with Rational Function Entries

We obtain formulac and estimates for character sums of the type S(x,f,p^m)=∑x=1^p^mx(f(f)),where p^m is a prime power with m≥2,x is a multiplicative character(mod p^m),and f=f1/f2 is a rational function over Z.In particular,if p is odd,d=deg(f1) deg(f2) and d^*=max(deg(f1),deg(f2)) then we obtain |S(x,f,p^m)|≤(d-1)p^m(1-1/d^*) for any non-constant f (mod p) and primitive character x.For p=2 an extra factor of 2√2 is needed.     

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.     

8-ranks of Class Groups of Some Imaginary Quadratic Number Fields

Let F = Q（√-p1p2） be an imaginary quadratic field with distinct primes p1 = p2 = 1 mod 8 and the Legendre symbol （p1/p2） = 1. Then the 8-rank of the class group of F is equal to 2 if and only Pl if the following conditions hold： （1） The quartic residue symbols （p1/p2）4 = （p2/p1）4 = 1; （2） Either both p1 and p2 are represented by the form a^2 ＋ 32b^2 over Z and p^h2＋（2p1）/4=x^2-2p1y^2,x,y∈Z,or both p1 and p2 are not represented by the form a^2 ＋ 32b^2 over Z and p^h2＋（2p1）/4=ε（2x^2-p1y^2）,x,y∈Z,ε∈{±1},where h＋（2p1） is the narrow class number of Q（√2p1）,Moreover, we also generalize these results.     

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     

Blow-up criterion for 2-D Boussinesq equations in bounded domain

We extend the results for 2-D Boussinesq equations from ℝ² to a bounded domain Ω. First, as for the existence of weak solutions, we transform Boussinesq equations to a nonlinear evolution equation U _t + A(t, U) = 0. In stead of using the methods of fundamental solutions in the case of entire ℝ², we study the qualities of F(u, υ) = (u · ▽)υ to get some useful estimates for A(t, U), which helps us to conclude the local-in-time existence and uniqueness of solutions. Second, as for blow-up criterions, we use energy methods, Sobolev inequalities and Gronwall inequality to control and by and . Furthermore, can control by using vorticity transportation equations. At last, can control . Thus, we can find a blow-up criterion in the form of .      

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