Tiling Turán Theorems

H in a large graph G. Received June 2, 1998     

Two Turán type inequalities

Turán’s book [2], in Section 19.4, refers to the following result of Gábor Halász. Let a ₀, a ₁, ..., a _n−1 be complex numbers such that the roots α ₁, ⋯, α _n of the polynomial x ⁿ + a _n−1 x ⁿ⁻¹ + ⋯ + a ₁ x + a ₀ satisfy min _j Re α _j ≧ 0 and let function Y(t) be a solution of the linear differential equation Y ⁽ⁿ⁾ + a _n−1 Y ⁽ⁿ⁻¹⁾ + ⋯ + a ₁ Y′ + a ₀ Y = 0. Then

Turán numbers for odd wheels

The Turán number $\text{ex}(n,G)$ is the maximum number of edges in any $n$-vertex graph that does not contain a subgraph isomorphic to $G$. A wheel$W_n$ is a graph on $n$ vertices obtained from a $C_{n?1}$ by adding one vertex $w$ and making $w$ adjacent to all vertices of the $C_{n?1}$. We obtain two exact values for small wheels:

$\text{ex}(n,W_5)=?\frac{n^2}{4}+\frac{n}{2}?,$

$\text{ex}(n,W_7)=?\frac{n^2}{4}+\frac{n}{2}+1?.$

Given that $\text{ex}(n,W_6)$ is already known, this paper completes the spectrum for all wheels up to 7 vertices. In addition, we present the construction which gives us the lower bound $\text{ex}(n,W_{2k+1})>?\frac{n^2}{4}?+?\frac{n}{2}?$ in general case.     

Explicit evaluations of Turán expressions

Summary Positive representations for [P _n ^(λ) (x)]²−P _n ^−1/(λ) (x)P _n ^+1/(λ) (x) and for analogous expressions involving orthogonal polynomials are obtained. This is an excerpt from the author's doctoral dissertation, written under the direction of ProfessorW. Seidel, to whom the author is grateful for his encouragement and assistance.     

Notes on a problem of Turán

Let z1,z2, ... ,znbe complex numbers, and write S= z ^j _{1 + ... +} z ^j _n for their power sums. Let R _n= min_{z 1,z2,...,zn} max_1≤j≤n |Sj| where the minimum is taken under the condition that max_1≤t≤n |z_t| = 1 Improving a result of Komlós, Sárközy and Szemerédi (see [KSSz]) we prove here that Rn <1 -(1 - ") log log n /log n We also discuss a related extremal problem which occurred naturally in our earlier proof ([B1]) of the fact that Rn >½     

On the Turán Density of Uniform Hypergraphs

Acta Mathematicae Applicatae Sinica, English Series - Let p, q be two positive integers. The 3-graph F(p, q) is obtained from the complete 3-graph K 3 by adding q new vertices and $$p(_2^q)$$ new...     

The Turán Number Of The Fano Plane

  Let PG₂(2) be the Fano plane, i. e., the unique hypergraph with 7 triples on 7 vertices in which every pair of vertices is contained in a unique triple. In this paper we prove that for sufficiently large n, the maximum number of edges in a 3-uniform hypergraph on n vertices not containing a Fano plane is

Hypergraph Turán Numbers of Vertex Disjoint Cycles

The Turán number of a k-uniform hypergraph H,denoted by ex_k(n;H),is the maximum number of edges in any k-uniform hypergraph F on n vertices which does not contain H as a subgraph.Let C_l~((k)) denote the family of all k-uniform minimal cycles of length l;S(?₁,…,?_r) denote the family of hypergraphs consisting of unions of r vertex disjoint minimal cycles of length ?₁,…?_r,respectively,and C_l~((k))denote a k-uniform linear ...     

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.     

On Ramsey—Turán type theorems for hypergraphs

LetH ^r be anr-uniform hypergraph. Letg=g(n;H ^r ) be the minimal integer so that anyr-uniform hypergraph onn vertices and more thang edges contains a subgraph isomorphic toH ^r . Lete =f(n;H ^r ,εn) denote the minimal integer such that everyr-uniform hypergraph onn vertices with more thane edges and with no independent set ofεn vertices contains a subgraph isomorphic toH ^r . We show that ifr>2 andH ^r is e.g. a complete graph then $$\mathop {\lim }\limits_{\varepsilon \to 0} \mathop {\lim }\limits_{n \to \infty } \left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)^{ - 1} f(n;H^r ,\varepsilon n) = \mathop {\lim }\limits_{n \to \infty } \left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)^{ - 1} g(n;H^r )$$ while for someH ^r with \(\mathop {\lim }\limits_{n \to \infty } \left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)^{ - 1} g(n;H^r ) \ne 0\) $$\mathop {\lim }\limits_{\varepsilon \to 0} \mathop {\lim }\limits_{n \to \infty } \left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)^{ - 1} f(n;H^r ,\varepsilon n) = 0$$ . This is in strong contrast with the situation in caser=2. Some other theorems and many unsolved problems are stated.     

Turán Type Inequalities for Tricomi Confluent Hypergeometric Functions

Some sharp two-sided Turán type inequalities for parabolic cylinder functions and Tricomi confluent hypergeometric functions are deduced. The proofs are based on integral representations for quotients of parabolic cylinder functions and Tricomi confluent hypergeometric functions, which arise in the study of the infinite divisibility of the Fisher–Snedecor F distribution. Moreover, some complete monotonicity results are given concerning Turán determinants of Tricomi confluent hypergeometric functions. These complement and improve some of the results of Ismail and Laforgia (in Constr. Approx. 26:1–9, 2007).     

The shifted Turán sieve method on tournaments II

In a previous work [5], we developed the shifted Turán sieve method on a bipartite graph and applied it to problems on cycles in tournaments. More precisely, we obtained upper bounds for the number of tournaments which contain a small number of r-cycles. In this paper, we improve our sieve inequality and apply it to obtain an upper bound for the number of bipartite tournaments which contain a number of 2r-cycles far from the average. We also provide the exact bound for the number of tournaments which contain few 3-cycles, using other combinatorial arguments.     

A Note on Turán Numbers for Even Wheels

The Turán number ex(n, G) is the maximum number of edges in any n-vertex graph that does not contain a subgraph isomorphic to G. We consider a very special case of the Simonovits’s theorem (Simonovits in: Theory of graphs, Academic Press, New York, 1968) which determine an asymptotic result for Turán numbers for graphs with some properties. In the paper we present a more precise result for even wheels. We provide the exact value for Turán number ex(n, W _2k ) for n ≥ 6k ? 10 and k ≥ 3. In addition, we show that ${ex(n,W_6)= \lfloor\frac{n^2}{3}\rfloor}$ for all n ≥ 6. These numbers can be useful to calculate some Ramsey numbers.     

An exact Turán result for the generalized triangle

Let Σ _k consist of all k-graphs with three edges D ₁, D ₂, D ₃ such that |D ₁ ∩ D ₂| = k − 1 and D ₁ Δ D ₂ ⊆ D ₃. The exact value of the Turán function ex(n, Σ _k ) was computed for k = 3 by Bollobás [Discrete Math. 8 (1974), 21–24] and for k = 4 by Sidorenko [Math Notes 41 (1987), 247–259]. Let the k-graph T _k ∈ Σ _k have edges

Turán type inequalities for Krätzel functions

Complete monotonicity, Laguerre and Turán type inequalities are established for the so-called Krätzel function $Z_{\rho }^{\nu }$, defined by$Z_{\rho }^{\nu }(u)=\underset{0}{\overset{\infty }{\int }}{t}^{\nu ?1}{e}^{?t^{\rho }?\frac{u}{t}}\mathrm{d}t,$ where $u>0$ and $\rho ,\nu \in \mathbb{R}$. Moreover, we prove the complete monotonicity of a determinant function of which entries involve the Krätzel function.