Turán problems for integer‐weighted graphs

A multigraph is (k,r)‐dense if every k‐set spans at most r edges. What is the maximum number of edges ex_?(n,k,r) in a (k,r)‐dense multigraph on n vertices? We determine the maximum possible weight of such graphs for almost all k and r (e.g., for all r>k³) by determining a constant m=m(k,r) and showing that ex_?(n,k,r)=m +O(n), thus giving a generalization of Turán's theorem. We find exact answers in many cases, even when negative integer weights are also allowed. In fact, our main result is to determine the maximum weight of (k,r)‐dense n‐vertex multigraphs with arbitrary integer weights with an O(n) error term. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 195–225, 2002     

A generalization of Turán's theorem

In this paper, we obtain an asymptotic generalization of Turán's theorem. We prove that if all the non‐trivial eigenvalues of a d‐regular graph G on n vertices are sufficiently small, then the largest K_t‐free subgraph of G contains approximately (t ? 2)/(t ? 1)‐fraction of its edges. Turán's theorem corresponds to the case d = n ? 1. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Extremal graphs for the k‐flower

The Turán number of a graph H, , is the maximum number of edges in any graph of order n that does not contain an H as a subgraph. A graph on vertices consisting of k triangles that intersect in exactly one common vertex is called a k‐fan, and a graph consisting of k cycles that intersect in exactly one common vertex is called a k‐flower. In this article, we determine the Turán number of any k‐flower containing at least one odd cycle and characterize all extremal graphs provided n is sufficiently large. Erdős, Füredi, Gould, and Gunderson determined the Turán number for the k‐fan. Our result is a generalization of their result. The addition aim of this article is to draw attention to a powerful tool, the so‐called progressive induction lemma of Simonovits.     

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 Numbers for Disjoint Copies of Graphs

The Turán number ex(n,H){ex(n,\mathcal H)} of H{\mathcal H} is the maximum number of edges of an n-vertex simple graph having no member of H{\mathcal H} as a subgraph. We show lower and upper bounds for Turán numbers for disjoint copies of graphs.     

Extension of Turán's Theorem to the 2-Stability Number

 Given a graph G with n vertices and stability number α(G), Turán's Theorem gives a lower bound on the number of edges in G. Furthermore, Turán has proved that the lower bound is only attained if G is the union of α(G) disjoint balanced cliques. We prove a similar result for the 2-stability number α₂(G) of G, which is defined as the largest number of vertices in a 2-colorable subgraph of G. Given a graph G with n vertices and 2-stability number α₂(G), we give a lower bound on the number of edges in G and characterize the graphs for which this bound is attained. These graphs are the union of isolated vertices and disjoint balanced cliques. We then derive lower bounds on the 2-stability number, and finally discuss the extension of Turán's Theorem to the q-stability number, for q>2. Received: July 21, 1999 Final version received: August 22, 2000 Present address: GERAD, 3000 ch. de la Cote-Ste-Catherine, Montreal, Quebec H3T 2A7, Canada. e-mail: Alain.Hertz@gerad.ca     

A class of constructions for turán’s (3, 4)-problem

Letf(n) denote the minimal number of edges of a 3-uniform hypergraphG=(V, E) onn vertices such that for every quadrupleY ⊂V there existsY ⊃e ∈E. Turán conjectured thatf(3k)=k(k−1)(2k−1). We prove that if Turán’s conjecture is correct then there exist at least 2 ^k−2 non-isomorphic extremal hypergraphs on 3k vertices.     

Triangle-free partial graphs and edge covering theorems

In section 1 some lower bounds are given for the maximal number of edges ofa (p ? 1)- colorable partial graph. Among others we show that a graph on n vertices with m edges has a (p?1)-colorable partial graph with at least mT_n.p/(ⁿ₂) edges, where T_n.p denotes the so called Turán number. These results are used to obtain upper bounds for special edge covering numbers of graphs. In Section 2 we prove the following theorem: If G is a simple graph and μ is the maximal cardinality of a triangle-free edge set of G, then the edges of G can be covered by μ triangles and edges. In Section 3 related questions are examined.     

Turánnical hypergraphs

This paper is motivated by the question of how global and dense restriction sets in results from extremal combinatorics can be replaced by less global and sparser ones. The result we consider here as an example is Turán's theorem, which deals with graphs G = ([n],E) such that no member of the restriction set \begin{align*}\mathcal {R}\end{align*} = \begin{align*}\left( {\begin{array}{*{20}c} {[n]} \\ r \\ \end{array} } \right)\end{align*} induces a copy of K_r. Firstly, we examine what happens when this restriction set is replaced by \begin{align*}\mathcal {R}\end{align*} = {X∈ \begin{align*}\left( {\begin{array}{*{20}c} {[n]} \\ r \\ \end{array} } \right)\end{align*}: X ∩ [m]≠??}. That is, we determine the maximal number of edges in an n ‐vertex such that no K_r hits a given vertex set. Secondly, we consider sparse random restriction sets. An r ‐uniform hypergraph \begin{align*}\mathcal R\end{align*} on vertex set [n] is called Turánnical (respectively ε ‐Turánnical), if for any graph G on [n] with more edges than the Turán number t_r(n) (respectively (1 + ε)t_r(n) ), no hyperedge of \begin{align*}\mathcal {R}\end{align*} induces a copy of K_r in G. We determine the thresholds for random r ‐uniform hypergraphs to be Turánnical and to be ε ‐Turánnical. Thirdly, we transfer this result to sparse random graphs, using techniques recently developed by Schacht [Extremal results for random discrete structures] to prove the Kohayakawa‐?uczak‐Rödl Conjecture on Turán's theorem in random graphs.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Extremal problems for triple systems

In this article Turán-type problems for several triple systems arising from (k, k ? 2)-configurations [i.e. (k ? 2) triples on k vertices] are considered. It will be shown that every Steiner triple system contains a (k, k ? 2)-configuration for some k < c log n/ log log n. Moreover, the Turán numbers of (k, k ? 2)-trees are determined asymptotically to be ((k ? 3)/3).(ⁿ₂) (1?o(1)). Finally, anti-Pasch hypergraphs avoiding (5, 3) -and (6, 4)-Configurations are considered. © 1993 John Wiley & Sons, Inc.     

A Ramsey‐type problem and the Turán numbers*

For each n and k, we examine bounds on the largest number m so that for any k‐coloring of the edges of K_n there exists a copy of K_m whose edges receive at most k?1 colors. We show that for , the largest value of m is asymptotically equal to the Turá number , while for any constant then the largest m is asymptotically larger than that Turá number. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 120–129, 2002     

Multicolored trees in complete graphs

A multicolored tree is a tree whose edges have different colors. Brualdi and Hollingsworth 5 proved in any proper edge coloring of the complete graph K_2n(n > 2) with 2n ? 1 colors, there are two edge‐disjoint multicolored spanning trees. In this paper we generalize this result showing that if (a₁,…, a_k) is a color distribution for the complete graph K_n, n ≥ 5, such that , then there exist two edge‐disjoint multicolored spanning trees. Moreover, we prove that for any edge coloring of the complete graph K_n with the above distribution if T is a non‐star multicolored spanning tree of K_n, then there exists a multicolored spanning tree T' of K_n such that T and T' are edge‐disjoint. Also it is shown that if K_n, n ≥ 6, is edge colored with k colors and , then there exist two edge‐disjoint multicolored spanning trees. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 221–232, 2007     

Improved lower bounds on k-independence

A vertex set Y in a (hyper)graph is called k-independent if in the sub(hyper)-graph induced by Y every vertex is incident to less than k edges. We prove a lower bound for the maximum cardinality of a k-independent set—in terms of degree sequences—which strengthens and generalizes several previously known results, including Turán's theorem.     

Turán's theorem in sparse random graphs

We prove the analogue of Turán's Theorem in random graphs with edge probability p(n) ? n^?1/(k?1.5). With probability 1 ? o(1), one needs to delete approximately ‐fraction of the edges in a random graph in order to destroy all cliques of size k. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 225–234, 2003     

The chromatic Ramsey number of odd wheels

We prove that the chromatic Ramsey number of every odd wheel W_{2k+ 1}, k?2 is 14. That is, for every odd wheel W_{2k+ 1}, there exists a 14‐chromatic graph F such that when the edges of F are two‐coloured, there is a monochromatic copy of W_{2k+ 1} in F, and no graph F with chromatic number 13 has the same property. We ask whether a natural extension of odd wheels to the family of generalized Mycielski graphs could help to prove the Burr–Erd?s–Lovász conjecture on the minimum possible chromatic Ramsey number of an n‐chromatic graph. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:198‐205, 2012     

Complete subgraphs with large degree sums

Let t(n, k) denote the Turán number—the maximum number of edges in a graph on n vertices that does not contain a complete graph K_k+1. It is shown that if G is a graph on n vertices with n ≥ k²(k – 1)/4 and m < t(n, k) edges, then G contains a complete subgraph K_k such that the sum of the degrees of the vertices is at least 2km/n. This result is sharp in an asymptotic sense in that the sum of the degrees of the vertices of K_k is not in general larger, and if the number of edges in G is at most t(n, k) – ? (for an appropriate ?), then the conclusion is not in general true. © 1992 John Wiley & Sons, Inc.     

A generalized Turán problem in random graphs

We study a generalization of the Turán problem in random graphs. Given graphs T and H, let ex(G(n,p),T,H) be the largest number of copies of T in an H‐free subgraph of G(n,p). We study the threshold phenomena arising in the evolution of the typical value of this random variable, for every H and every 2‐balanced T. Our results in the case when m₂(H) > m₂(T) are a natural generalization of the Erd?s‐Stone theorem for G(n,p), proved several years ago by Conlon‐Gowers and Schacht; the case T = K_m was previously resolved by Alon, Kostochka, and Shikhelman. The case when m₂(H) ≤ m₂(T) exhibits a more complex behavior. Here, the location(s) of the (possibly multiple) threshold(s) are determined by densities of various coverings of H with copies of T and the typical value(s) of ex(G(n,p),T,H) are given by solutions to deterministic hypergraph Turán‐type problems that we are unable to solve in full generality.     

The structure of graphs with given lengths of cycles

The cycle spectrum of a given graph G is the lengths of cycles in G. In this paper, we introduce the following problem: determining the maximum number of edges of an n-vertex graph with given cycle spectrum. In particular, we determine the maximum number of edges of an n-vertex graph without containing cycles of lengths three and at least k. This can be viewed as an extension of a well-known result of Erd?s and Gallai concerning the maximum number of edges of an n-vertex graph without containing cycles of lengths at least k. We also determine the maximum number of edges of an n-vertex graph whose cycle spectrum is a subset of two positive integers.     

On splittable colorings of graphs and hypergraphs

The notion of a split coloring of a complete graph was introduced by Erd?s and Gyárfás [ 7 ] as a generalization of split graphs. In this work, we offer an alternate interpretation by comparing such a coloring to the classical Ramsey coloring problem via a two‐round game played against an adversary. We show that the techniques used and bounds obtained on the extremal (r,m)‐split coloring problem of [ 7 ] are closer in nature to the Turán theory of graphs rather than Ramsey theory. We extend the notion of these colorings to hypergraphs and provide bounds and some exact results. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 226–237, 2002     

Some remarks on trigonometric interpolation

The object of this paper is to consider the problem of (0, 1, 2, 4) trigonometric interpolation when nodes are taken to bex _kn=(2kπ/n),k=0, 1 …,n−1. Here the interpolatory polynomials are explicitly constructed and the corresponding convergence theorem is proved, which is shown to be best possible in a certain sense. It is interesting to compare these results with those of Saxena [6], where the convergence theorem requires the existence off ^m (x). I take this opportunity to express my thanks to Professor P. Turán for some valuable conversation which led to this work. The author is at present a member of the faculty of the Dept. of Mathematics, University of Florida, Gainesville, U.S.A.