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.     

A Ramsey–Turán theory for tilings in graphs

For a $k$-vertex graph $F$ and an $n$-vertex graph $G$, an $F$-tiling in $G$ is a collection of vertex-disjoint copies of $F$ in $G$. For $r\in \mathbb{N}$, the $r$-independence number of $G$, denoted ${\alpha }_r(G)$, is the largest size of a $K_r$-free set of vertices in $G$. In this article, we discuss Ramsey–Turán-type theorems for tilings where one is interested in minimum degree and independence number conditions (and the interaction between the two) that guarantee the existence of optimal $F$-tilings. Our results unify and generalise previous results of Balogh–Molla–Sharifzadeh [Random Struct. Algoritm. 49 (2016), no. 4, 669–693], Nenadov–Pehova [SIAM J. Discret. Math. 34 (2020), no. 2, 1001–1010] and Balogh–McDowell–Molla–Mycroft [Comb. Probab. Comput. 27 (2018), no. 4, 449–474] on the subject.     

On the Ramsey-Turán numbers of graphs and hypergraphs

Let t be an integer, f(n) a function, and H a graph. Define the t-Ramsey-Turán number of H, RT _t (n,H, f(n)), to be the maximum number of edges in an n-vertex, H-free graph G with α _t (G) ≤ f(n), where α _t (G) is the maximum number of vertices in a K _t -free induced subgraph of G. Erd?s, Hajnal, Simonovits, Sós and Szemerédi [6] posed several open questions about RT _t (n,K _s , o(n)), among them finding the minimum ? such that RT _t (n,K _t+? , o(n)) = Ω(n ²), where it is easy to see that RT _t (n,K _t+1, o(n)) = o(n ²). In this paper, we answer this question by proving that RT _t (n,K _t+2, o(n)) = Ω(n ²); our constructions also imply several results on the Ramsey-Turán numbers of hypergraphs.     

Turán and Ramsey numbers in linear triple systems II

In this paper we continue our studies of Turán and Ramsey numbers in linear triple systems, defined as 3-uniform hypergraphs in which any two triples intersect in at most one vertex. In [7] the two main problems left open were the Turán number of the wicket and the Ramsey property of the sail. In this paper we present some progress towards both of these problems.     

Turán numbers for K s,t -free graphs: Topological obstructions and algebraic constructions

We show that every hypersurface in ? ^s × ? ^s contains a large grid, i.e., the set of the form S × T, with S, T ? ? ^s . We use this to deduce that the known constructions of extremal K _2,2-free and K _3,3-free graphs cannot be generalized to a similar construction of K _s,s -free graphs for any s ≥ 4. We also give new constructions of extremal K _s,t -free graphs for large t.     

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.     

Turán-type bounds for distance graphs

A lower bound is obtained for the number of edges in a distance graph G in an infinitesimal plane layer ?² × [0, ε] ^d , which relates the number of edges e(G), the number of vertices ν(G), and the independence number α(G). It is proved that \(e\left( G \right) \geqslant \frac{{19\nu \left( G \right) - 50\alpha \left( G \right)}}{3}\). This result generalizes a previous bound for distance graphs in the plane. It substantially improves Turán’s bound in the case where \(\frac{1}{5} \leqslant \frac{{\alpha \left( G \right)}}{{\nu \left( G \right)}} \leqslant \frac{2}{7}\).     

Tiling Turán Theorems

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

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

Regular Turán numbers and some Gan–Loh–Sudakov-type problems

Motivated by a Gan–Loh–Sudakov-type problem, we introduce the regular Turán numbers, a natural variation on the classical Turán numbers where we restrict ourselves to the class of regular graphs. Among other results, we prove a striking supersaturation version of Mantel's theorem in the case of a regular host graph of odd order. We also characterize the graphs for which the regular Turán numbers behave classically or otherwise.     

Turán's extremal problem in random graphs: Forbidding odd cycles

For 0<1 and graphsG andH, we writeGH if any -proportion of the edges ofG span at least one copy ofH inG. As customary, we writeC ^k for a cycle of lengthk. We show that, for every fixed integerl1 and real >0, there exists a real constantC=C(l, ), such that almost every random graphG _{n, p} withp=p(n)Cn ^–1+1/2l satisfiesG _n,p1/2+ C ^2l+1. In particular, for any fixedl1 and >0, this result implies the existence of very sparse graphsG withG _1/2+ C ^2l+1.The first author was partially supported by NSERC. The second author was partially supported by FAPESP (Proc. 93/0603-1) and by CNP_q (Proc. 300334/93-1). The third author was partially sopported by KBN grant 2 1087 91 01.     

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

ON possible Turán densities

The Turán density π(F) of a family F of k-graphs is the limit as n → ∞ of the maximum edge density of an F-free k-graph on n vertices. Let Π _∞ ^(k) consist of all possible Turán densities and let Π _fin ^(k) ? Π _∞ ^(k) be the set of Turán densities of finite k-graph families. Here we prove that Π _fin ^(k) contains every density obtained from an arbitrary finite construction by optimally blowing it up and using recursion inside the specified set of parts. As an application, we show that Π _fin ^(k) contains an irrational number for each k ≥ 3. Also, we show that Π _∞ ^(k) has cardinality of the continuum. In particular, Π _∞ ^(k) ≠ Π _fin ^(k) .     

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

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

Turán-type results for partial orders and intersection graphs of convex sets

We prove Ramsey-type results for intersection graphs of geometric objects. In particular, we prove the following bounds, all of which are tight apart from the constant c. There is a constant c > 0 such that for every family F of n convex sets in the plane, the intersection graph of F or its complement contains a balanced complete bipartite graph of size at least cn. There is a constant c > 0 such that for every family F of n x-monotone curves in the plane, the intersection graph G of F contains a balanced complete bipartite graph of size at least cn/log n or the complement of G contains a balanced complete bipartite graph of size at least cn. Our bounds rely on new Turán-type results on incomparability graphs of partially ordered sets.