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.     

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     

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     

Bounds on Turán determinants

Let μ denote a symmetric probability measure on [−1,1] and let (p_n) be the corresponding orthogonal polynomials normalized such that p_n(1)=1. We prove that the normalized Turán determinant Δ_n(x)/(1−x²), where , is a Turán determinant of order n−1 for orthogonal polynomials with respect to . We use this to prove lower and upper bounds for the normalized Turán determinant in the interval −1<x<1.     

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     

On Turán problems for Cartesian products of graphs

Let be disjoint sets of sizes and . Let be a family of quadruples, having elements from and from , such that any subset with and contains one of the quadruples. We prove that the smallest size of is as . We also solve asymptotically a more general two‐partite Turán problem for quadruples.     

An application of the Turán theorem to domination in graphs

A function f:V(G)→{+1,−1} defined on the vertices of a graph G is a signed dominating function if for any vertex v the sum of function values over its closed neighborhood is at least 1. The signed domination number γ_s(G) of G is the minimum weight of a signed dominating function on G. By simply changing “{+1,−1}” in the above definition to “{+1,0,−1}”, we can define the minus dominating function and the minus domination number of G. In this note, by applying the Turán theorem, we present sharp lower bounds on the signed domination number for a graph containing no (k+1)-cliques. As a result, we generalize a previous result due to Kang et al. on the minus domination number of k-partite graphs to graphs containing no (k+1)-cliques and characterize the extremal graphs.     

Sparse halves in K 4-free graphs

A conjecture of Chung and Graham states that every $K_4$-free graph on $n$ vertices contains a vertex set of size $?n∕2?$ that spans at most $n^2∕18$ edges. We make the first step toward this conjecture by showing that it holds for all regular graphs.     

Lagrangian densities of linear forests and Turán numbers of their extensions

The Lagrangian of a hypergraph has been a useful tool in hypergraph extremal problems. Recently, Lagrangian densities of hypergraphs and Turán numbers of their extensions have been studied actively. However, determining the Lagrangian density of a hypergraph is not an easy task even for a “simple” hypergraph. For example, to determine the Lagrangian density of $K_4^3$ is equivalent to determine the Turán density of $K_4^3$ (a long standing conjecture of Turán). Hefetz and Keevash studied the Lagrangian density of the 3‐uniform matching of size 2. Pikhurko determined the Lagrangian density of a 4‐uniform tight path of length 2 and this led to confirm the conjecture of Frankl and Füredi on the Turán number of the $r$‐uniform generalized triangle for the case $r=4$. It is natural and interesting to consider Lagrangian densities of other “basic” hypergraphs. In this paper, we determine the Lagrangian densities for a class of 3‐uniform linear forests. For positive integers $s$ and $t$, let $P_{s,t}$ be the disjoint union of a 3‐uniform linear path of length $s$ and $t$ pairwise disjoint edges. In this paper, we determine the Lagrangian densities of $P_{s,t}$ for any $t$ and $s=2$ or 3. Applying a modified version of Pikhurko's transference argument used by Brandt, Irwin, and Jiang, we obtain the Turán numbers of their extensions.     

An Extremal Property of Turán Graphs,II

Let denote Turán's graph—the complete 2‐partite graph on n vertices with partition sizes as equal as possible. We show that for all , the graph has more proper vertex colorings in at most 4 colors than any other graph with the same number of vertices and edges.     

Turán type reverse Markov inequalities for compact convex sets

For a compact convex set the well-known general Markov inequality holds asserting that a polynomial p of degree n must have p^′c(K)n²p. On the other hand for polynomials in general, p^′ can be arbitrarily small as compared to p.The situation changes when we assume that the polynomials in question have all their zeroes in the convex set K. This was first investigated by Turán, who showed the lower bounds p^′(n/2)p for the unit disk D and for the unit interval I[-1,1]. Although partial results provided general lower estimates of order , as well as certain classes of domains with lower bounds of order n, it was not clear what order of magnitude the general convex domains may admit here.Here we show that for all bounded and convex domains K with nonempty interior and polynomials p with all their zeroes lying in K p^′c(K)np holds true, while p^′C(K)np occurs for any K. Actually, we determine c(K) and C(K) within a factor of absolute numerical constant.     

Stability results for random discrete structures

Two years ago, Conlon and Gowers, and Schacht proved general theorems that allow one to transfer a large class of extremal combinatorial results from the deterministic to the probabilistic setting. Even though the two papers solve the same set of long‐standing open problems in probabilistic combinatorics, the methods used in them vary significantly and therefore yield results that are not comparable in certain aspects. In particular, the theorem of Schacht yields stronger probability estimates, whereas the one of Conlon and Gowers also implies random versions of some structural statements such as the famous stability theorem of Erd?s and Simonovits. In this paper, we bridge the gap between these two transference theorems. Building on the approach of Schacht, we prove a general theorem that allows one to transfer deterministic stability results to the probabilistic setting. We then use this theorem to derive several new results, among them a random version of the Erd?s‐Simonovits stability theorem for arbitrary graphs, extending the result of Conlon and Gowers, who proved such a statement for so‐called strictly 2‐balanced graphs. The main new idea, a refined approach to multiple exposure when considering subsets of binomial random sets, may be of independent interest.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 269‐289, 2014     

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     

Extremal graphs with bounded densities of small subgraphs

Let Ex(n, k, μ) denote the maximum number of edges of an n-vertex graph in which every subgraph of k vertices has at most μ edges. Here we summarize some known results of the problem of determining Ex(n, k, μ), give simple proofs, and find some new estimates and extremal graphs. Besides proving new results, one of our main aims is to show how the classical Turáan theory can be applied to such problems. The case μ = is the famous result of Turáan. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 185–207, 1998     

A Generalization of a Theorem of Birch

We generalize a theorem of Birch on solving systems of homogeneous equations of odd degree to the case of solving systems of homogeneous equations of degree not divisible by a fixed integer s ≥ 2. Birch's theorem is the case s = 2. In addition, we give a new exposition of the proof of Brauer's theorem on solving systems of homogeneous equations.     

Valuation of Two-Factor Interest Rate Contingent Claims Using Green's Theorem

Abstract

Over the years a number of two-factor interest rate models have been proposed that have formed the basis for the valuation of interest rate contingent claims. This valuation equation often takes the form of a partial differential equation that is solved using the finite difference approach. In the case of two-factor models this has resulted in solving two second-order partial derivatives leading to boundary errors, as well as numerous first-order derivatives. In this article we demonstrate that using Green's theorem, second-order derivatives can be reduced to first-order derivatives that can be easily discretized; consequently, two-factor partial differential equations are easier to discretize than one-factor partial differential equations. We illustrate our approach by applying it to value contingent claims based on the two-factor CIR model. We provide numerical examples that illustrate that our approach shows excellent agreement with analytical prices and the popular Crank–Nicolson method.