The Turán problem for projective geometries

We consider the following Turán problem. How many edges can there be in a (q+1)-uniform hypergraph on n vertices that does not contain a copy of the projective geometry PG_m(q)? The case q=m=2 (the Fano plane) was recently solved independently and simultaneously by Keevash and Sudakov (The Turán number of the Fano plane, Combinatorica, to appear) and Füredi and Simonovits (Triple systems not containing a Fano configuration, Combin. Probab. Comput., to appear). Here we obtain estimates for general q and m via the de Caen-Füredi method of links combined with the orbit-stabiliser theorem from elementary group theory. In particular, we improve the known upper and lower bounds in the case q=2, m=3.     

On the Turán number for the hexagon

A long-standing conjecture of Erd?s and Simonovits is that ex(n,C_2k), the maximum number of edges in an n-vertex graph without a 2k-gon is asymptotically as n tends to infinity. This was known almost 40 years ago in the case of quadrilaterals. In this paper, we construct a counterexample to the conjecture in the case of hexagons. For infinitely many n, we prove that

     

Extremal problems,partition theorems,symmetric hypergraphs

We compare extremal theorems such as Turán’s theorem with their corresponding partition theorems such as Ramsey’s theorem. We derive a general inequality involving chromatic number and independence number of symmetric hypergraphs. We give applications to Ramsey numbers and to van der Waerden numbers.     

Algorithms for solving Hermite interpolation problems using the Fast Fourier Transform

We present a method for computing the Hermite interpolation polynomial based on equally spaced nodes on the unit circle with an arbitrary number of derivatives in the case of algebraic and Laurent polynomials. It is an adaptation of the method of the Fast Fourier Transform (FFT) for this type of problems with the following characteristics: easy computation, small number of operations and easy implementation.In the second part of the paper we adapt the algorithm for computing the Hermite interpolation polynomial based on the nodes of the Tchebycheff polynomials and we also study Hermite trigonometric interpolation problems.     

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     

On Gautschi’s conjecture for generalized Gauss-Radau and Gauss-Lobatto formulae

Recently, Gautschi introduced so-called generalized Gauss-Radau and Gauss-Lobatto formulae which are quadrature formulae of Gaussian type involving not only the values but also the derivatives of the function at the endpoints. In the present note we show the positivity of the corresponding weights; this positivity has been conjectured already by Gautschi.As a consequence, we establish several convergence theorems for these quadrature formulae.     

Extremal hypergraph problems and convex hulls

Theprofile of a hypergraph onn vertices is (f ₀, f₁, ...,f _n) wheref _i denotes the number ofi-element edges. The extreme points of the set of profiles is determined for certain hypergraph classes. The results contain many old theorems of extremal set theory as particular cases (Sperner. Erdős—Ko—Rado, Daykin—Frankl—Green—Hilton).     

Unavoidable Traces Of Set Systems

Sauer, Shelah, Vapnik and Chervonenkis proved that if a set system on n vertices contains many sets, then the set system has full trace on a large set. Although the restriction on the size of the groundset cannot be lifted, Frankl and Pach found a trace structure that is guaranteed to occur in uniform set systems even if we do not bound the size of the groundset. In this note we shall give three sequences of structures such that every set system consisting of sufficiently many sets contains at least one of these structures with many sets.     

An approximate Dirac-type theorem for k-uniform hypergraphs

A k-uniform hypergraph is hamiltonian if for some cyclic ordering of its vertex set, every k consecutive vertices form an edge. In 1952 Dirac proved that if the minimum degree in an n-vertex graph is at least n/2 then the graph is hamiltonian. We prove an approximate version of an analogous result for uniform hypergraphs: For every K ≥ 3 and γ > 0, and for all n large enough, a sufficient condition for an n-vertex k-uniform hypergraph to be hamiltonian is that each (k − 1)-element set of vertices is contained in at least (1/2 + γ)n edges. Research supported by NSF grant DMS-0300529. Research supported by KBN grant 2P03A 015 23 and N201036 32/2546. Part of research performed at Emory University, Atlanta. Research supported by NSF grant DMS-0100784.     

An intersection theorem for four sets

Fix integers n,r?4 and let F denote a family of r-sets of an n-element set. Suppose that for every four distinct A,B,C,D∈F with |A∪B∪C∪D|?2r, we have A∩B∩C∩D≠∅. We prove that for n sufficiently large, , with equality only if _?F∈FF≠∅. This is closely related to a problem of Katona and a result of Frankl and Füredi [P. Frankl, Z. Füredi, A new generalization of the Erd?s-Ko-Rado theorem, Combinatorica 3 (3-4) (1983) 341-349], who proved a similar statement for three sets. It has been conjectured by the author [D. Mubayi, Erd?s-Ko-Rado for three sets, J. Combin. Theory Ser. A, 113 (3) (2006) 547-550] that the same result holds for d sets (instead of just four), where d?r, and for all n?dr/(d−1). This exact result is obtained by first proving a stability result, namely that if |F| is close to then F is close to satisfying _?F∈FF≠∅. The stability theorem is analogous to, and motivated by the fundamental result of Erd?s and Simonovits for graphs.     

Small Forbidden Configurations IV: The 3 Rowed Case

The present paper continues the work begun by Anstee, Griggs and Sali on small forbidden configurations. We define a matrix to be simple if it is a (0,1)-matrix with no repeated columns. Let F be a k×l (0,1)-matrix (the forbidden configuration). Small refers to the size of k and in this paper k = 3. Assume A is an m×n simple matrix which has no submatrix which is a row and column permutation of F. We define forb(m,F) as the best possible upper bound on n, for such a matrix A, which depends on m and F. We complete the classification for all 3-rowed (0,1)-matrices of forb (m,F) as either Θ(m), Θ(m²) or Θ(m³) (with constants depending on F). * Research is supported in part by NSERC. † Research was done while the second author visited the University of British Columbia supported by NSERC of first author. Research was partially supported by Hungarian National Research Fund (OTKA) numbers T034702 and T037846.     

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.     

Katona’s Intersection Theorem: Four Proofs

It is known from a previous paper [3] that Katonas Intersection Theorem follows from the Complete Intersection Theorem by Ahlswede and Khachatrian via a Comparison Lemma. It also has been proved directly in [3] by the pushing–pulling method of that paper. Here we add a third proof via a new (k,k+1)-shifting technique, whose impact will be exploared elsewhere. The fourth and last of our proofs is a gift from heaven for Gyulas birthday.Presented on the Conference on Hypergraphs held in Budapest June 7–9, 2001 in Honour of Gyula Katona on the occasion of his 60th Birthday.     

On Shadows Of Intersecting Families

The shadow minimization problem for t-intersecting systems of finite sets is considered. Let be a family of k-subsets of . The -shadow of is the set of all (k-)-subsets contained in the members of . Let be a t-intersecting family (any two members have at least t elements in common) with . Given k,t,m the problem is to minimize (over all choices of ). In this paper we solve this problem when m is big enough.     

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.     

Erd?s-Ko-Rado for three sets

Fix integers k?3 and n?3k/2. Let F be a family of k-sets of an n-element set so that whenever A,B,C∈F satisfy |A∪B∪C|?2k, we have A∩B∩C≠∅. We prove that with equality only when ?_F∈FF≠∅. This settles a conjecture of Frankl and Füredi [2], who proved the result for n?k²+3k.     

On a theorem of lovász on covers inr-partite hypergraphs

A theorem of Lovász asserts that (H)/*(H)r/2 for everyr-partite hypergraphH (where and * denote the covering number and fractional covering number respectively). Here it is shown that the same upper bound is valid for a more general class of hypergraphs: those which admit a partition (V ₁, ...,V _k ) of the vertex set and a partitionp ₁+...+p _k ofr such that |eV _i |p _i r/2 for every edgee and every 1ik. Moreover, strict inequality holds whenr>2, and in this form the bound is tight. The investigation of the ratio /* is extended to some other classes of hypergraphs, defined by conditions of similar flavour. Upper bounds on this ratio are obtained fork-colourable, stronglyk-colourable and (what we call)k-partitionable hypergraphs.Supported by grant HL28438 at MIPG, University of Pennsylvania, and by the fund for the promotion of research at the Technion.This author's research was supported by the fund for the promotion of research at the Technion.     

A full-Newton step non-interior continuation algorithm for a class of complementarity problems

In this paper, we investigate a class of nonlinear complementarity problems arising from the discretization of the free boundary problem, which was recently studied by Sun and Zeng [Z. Sun, J. Zeng, A monotone semismooth Newton type method for a class of complementarity problems, J. Comput. Appl. Math. 235 (5) (2011) 1261–1274]. We propose a new non-interior continuation algorithm for solving this class of problems, where the full-Newton step is used in each iteration. We show that the algorithm is globally convergent, where the iteration sequence of the variable converges monotonically. We also prove that the algorithm is globally linearly and locally superlinearly convergent without any additional assumption, and locally quadratically convergent under suitable assumptions. The preliminary numerical results demonstrate the effectiveness of the proposed algorithm.     

The numerical stability of evaluation schemes for polynomials based on the lagrange interpolation form

For evaluation schemes based on the Lagrangian form of a polynomial with degreen, a rigorous error analysis is performed, taking into account that data, computation and even the nodes of interpolation might be perturbed by round-off. The error norm of the scheme is betweenn ² andn ²+(3n+7) _n , where _n denotes the Lebesgue constant belonging to the nodes. Hence, the error norm is of least possible orderO(n ²) if, for instance, the nodes are chosen to be the Chebyshev points or the Fekete points.