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

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.     

Tur��n��s extremal problem on locally compact abelian groups

Let G be a locally compact abelian group (LCA group) and ?? be an open, 0-symmetric set. Let F:= F(??) be the set of all continuous functions f: G ?? ? which are supported in ?? and are positive definite. The Turán constant of ?? is then defined as $$ \mathcal{T}(\Omega ): = \sup \left\{ {\int_\Omega {f:f \in \mathcal{F}} (\Omega ),f(0) = 1} \right\} $$ . Mihalis Kolountzakis and the author has shown that structural properties ?? like spectrality, tiling or packing with a certain set ?? ?? of subsets ?? in finite, compact or Euclidean (i.e., ? ^d ) groups and in ? ^d yield estimates of T (??). However, in these estimates some notion of the size, i.e., density of ?? played a natural role, and thus in groups where we had no grasp of the notion, we could not accomplish such estimates. In the present work a recent generalized notion of asymptotic uniform upper density is invoked, allowing a more general investigation of the Turán constant in relation to the above structural properties. Our main result extends a result of Arestov and Berdysheva, (also obtained independently and along different lines by Kolountzakis and the author), stating that convex tiles of a Euclidean space necessarily have $$ \mathcal{T}_{\mathbb{R}^d } (\Omega )\left| \Omega \right|/2^d $$ . In our extension ? ^d could be replaced by any LCA group, convexity is considerably relaxed to ?? being a difference set, and the condition of tiling is also relaxed to a certain packing type condition and positive asymptotic uniform upper density of the set ??. Also our goal is to give a more complete account of all the related developments and history, because until now an exhaustive overview of the full background of the so-called Turán problem was not delivered.     

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.     

Ramsey Numbers for Triangles and Graphs of Order Four with No Isolated Vertex

Let mG denote the union of m vertex-disjoint copies of G.The Ramsey numbers r(mG, nK_3) are determined for all graphs of order four with no isolated vertex.     

Expansions for the Bollob��s-Riordan Polynomial of Separable Ribbon Graphs

We define 2-decompositions of ribbon graphs, which generalize 2-sums and tensor products of graphs. We give formulae for the Bollobás-Riordan polynomial of such a 2-decomposition, and derive the classical Brylawski formula for the Tutte polynomial of a tensor product as a (very) special case. This study was initially motivated from knot theory, and we include an application of our formulae to mutation in knot diagrams.     

Disjoint Paths in Graphs I,¶3-planar Graphs and Basic Obstructions

Let G be a graph,{a,b,c} í V(G) \{a,b,c\}\subseteq V(G) , and {a￠,b￠,c￠} í V(G) \{a',b',c'\}\subseteq V(G) such that {a,b,c} 1 {a￠,b￠,c￠} \{a,b,c\}\neq \{a',b',c'\} . We say that (G,{a,c}, {a￠,c￠}, (b, b￠)) (G,\{a,c\}, \{a',c'\}, (b, b')) is an obstruction if, for any three vertex disjoint paths from {a, b, c} to {a', b', c'} in G, one path is from b to b'. Robertson and Seymour asked the problem of characterizing all obstructions. In this paper, we present a list of "basic" obstructions and show how to produce other obstructions from these basic ones. We also prove results about disjoint paths in graphs. Results in this paper will be used in subsequent papers to characterize all obstructions.     

Universal Sets of n Points for One-bend Drawings of Planar Graphs with n Vertices

This paper shows that any planar graph with n vertices can be point-set embedded with at most one bend per edge on a universal set of n points in the plane. An implication of this result is that any number of planar graphs admit a simultaneous embedding without mapping with at most one bend per edge.     

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.     

Exact solution of the hypergraph Turán problem for k-uniform linear paths

A k-uniform linear path of length ?, denoted by ? _? ^(k) , is a family of k-sets {F ₁,...,F _? such that |F _i ∩ F _i+1|=1 for each i and F _i ∩ F _bj = \(\not 0\) whenever |i?j|>1. Given a k-uniform hypergraph H and a positive integer n, the k-uniform hypergraph Turán number of H, denoted by ex _k (n, H), is the maximum number of edges in a k-uniform hypergraph \(\mathcal{F}\) on n vertices that does not contain H as a subhypergraph. With an intensive use of the delta-system method, we determine ex _k (n, P _? ^(k) exactly for all fixed ? ≥1, k≥4, and sufficiently large n. We show that $ex_k (n,\mathbb{P}_{2t + 1}^{(k)} ) = (_{k - 1}^{n - 1} ) + (_{k - 1}^{n - 2} ) + \cdots + (_{k - 1}^{n - t} )$ . The only extremal family consists of all the k-sets in [n] that meet some fixed set of t vertices. We also show that $ex(n,\mathbb{P}_{2t + 2}^{(k)} ) = (_{k - 1}^{n - 1} ) + (_{k - 1}^{n - 2} ) + \cdots + (_{k - 1}^{n - t} ) + (_{k - 2}^{n - t - 2} )$ , and describe the unique extremal family. Stability results on these bounds and some related results are also established.     

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 >½     

Turán Inequalities and Complete Monotonicity for a Class of Entire Functions

Analysis Mathematica - The aim of this work is to derive several analytical properties for the class of entire functions defined by $${{\cal I}_\phi}(t) = \sum\limits_{n = 0}^\infty {{1 \over...     

AVDTC Numbers of Generalized Halin Graphs with Maximum Degree at Least 6

In a paper by Zhang and Chen et al.（see [11]）, a conjecture was made concerning the minimum number of colors Xat（G） required in a proper total-coloring of G so that any two adjacent vertices have different color sets, where the color set of a vertex v is the set composed of the color of v and the colors incident to v. We find the exact values of Xat（G） and thus verify the conjecture when G is a Generalized Halin graph with maximum degree at least 6, A generalized Halin graph is a 2-connected plane graph G such that removing all the edges of the boundary of the exterior face of G （the degrees of the vertices in the boundary of exterior face of G are all three） gives a tree.     

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

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

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.