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     

A weighted generalization of Turán's theorem

We obtain a generalization of Turáns theorem for graphs whose edges are assigned integer weights. We also characterize the extremal graphs in certain cases. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 267–275, 1997     

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án's theorem for pseudo-random graphs

The generalized Turán number ex(G,H) of two graphs G and H is the maximum number of edges in a subgraph of G not containing H. When G is the complete graph Km on m vertices, the value of ex(Km,H) is , where o(1)→0 as m→∞, by the Erd?s-Stone-Simonovits theorem.In this paper we give an analogous result for triangle-free graphs H and pseudo-random graphs G. Our concept of pseudo-randomness is inspired by the jumbled graphs introduced by Thomason [A. Thomason, Pseudorandom graphs, in: Random Graphs '85, Poznań, 1985, North-Holland, Amsterdam, 1987, pp. 307-331. MR 89d:05158]. A graph G is (q,β)-bi-jumbled if

     

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.     

An upper estimate in Turán's pure power sum problem

Let z₁, z₂, …, z_n be complex numbers, and write for their power sums. Let where the minimum is taken under the condition that . In this paper we prove that .     

Countable sparse random graphs

For each irrational a, 0<a<1, a particular countable graph G is defined which mirrors the asymptotic behavior of the random graph G(n, p) with edge probability p = n^?a.     

Bisecting sparse random graphs

Consider partitions of the vertex set of a graph G into two sets with sizes differing by at most 1: the bisection width of G is the minimum over all such partitions of the number of “cross edges” between the parts. We are interested in sparse random graphs G_{n, c/n} with edge probability c/n. We show that, if c>ln 4, then the bisection width is Ω(n) with high probability; while if c<ln 4, then it is equal to 0 with high probability. There are corresponding threshold results for partitioning into any fixed number of parts. ©2001 John Wiley & Sons, Inc. Random Struct. Alg., 18, 31–38, 2001     

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     

Right-convergence of sparse random graphs

The paper is devoted to the problem of establishing right-convergence of sparse random graphs. This concerns the convergence of the logarithm of number of homomorphisms from graphs or hyper-graphs \(\mathbb{G }_N, N\ge 1\) to some target graph \(W\) . The theory of dense graph convergence, including random dense graphs, is now well understood (Borgs et al. in Ann Math 176:151–219, 2012; Borgs et al. in Adv Math 219:1801–1851, 2008; Chatterjee and Varadhan in Eur J Comb 32:1000–1017, 2011; Lovász and Szegedy in J Comb Theory Ser B 96:933–957, 2006), but its counterpart for sparse random graphs presents some fundamental difficulties. Phrased in the statistical physics terminology, the issue is the existence of the limits of appropriately normalized log-partition functions, also known as free energy limits, for the Gibbs distribution associated with \(W\) . In this paper we prove that the sequence of sparse Erdös-Rényi graphs is right-converging when the tensor product associated with the target graph \(W\) satisfies a certain convexity property. We treat the case of discrete and continuous target graphs \(W\) . The latter case allows us to prove a special case of Talagrand’s recent conjecture [more accurately stated as level III Research Problem 6.7.2 in his recent book (Talagrand in Mean Field Models for Spin Glasses: Volume I: Basic examples. Springer, Berlin, 2010)], concerning the existence of the limit of the measure of a set obtained from \(\mathbb{R }^N\) by intersecting it with linearly in \(N\) many subsets, generated according to some common probability law. Our proof is based on the interpolation technique, introduced first by Guerra and Toninelli (Commun Math Phys 230:71–79, 2002) and developed further in (Abbe and Montanari in On the concentration of the number of solutions of random satisfiability formulas, 2013; Bayati et al. in Ann Probab Conference version in Proceedings of 42nd Ann. Symposium on the Theory of Computing (STOC), 2010; Contucci et al. in Antiferromagnetic Potts model on the Erdös-Rényi random graph, 2011; Franz and Leone in J Stat Phys 111(3/4):535–564, 2003; Franz et al. in J Phys A Math Gen 36:10967–10985, 2003; Montanari in IEEE Trans Inf Theory 51(9):3221–3246, 2005; Panchenko and Talagrand in Probab Theory Relat Fields 130:312–336, 2004). Specifically, Bayati et al. (Ann Probab Conference version in Proceedings of 42nd Ann. Symposium on the Theory of Computing (STOC), 2010) establishes the right-convergence property for Erdös-Rényi graphs for some special cases of \(W\) . In this paper most of the results in Bayati et al. (Ann Probab Conference version in Proceedings of 42nd Ann. Symposium on the Theory of Computing (STOC), 2010) follow as a special case of our main theorem.     

Chromatic thresholds in sparse random graphs

The chromatic threshold of a graph H with respect to the random graph G (n, p ) is the infimum over d > 0 such that the following holds with high probability: the family of H‐free graphs with minimum degree has bounded chromatic number. The study of was initiated in 1973 by Erd?s and Simonovits. Recently was determined for all graphs H . It is known that for all fixed , but that typically if Here we study the problem for sparse random graphs. We determine for most functions when , and also for all graphs H with © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 215–236, 2017     

Induced trees in sparse random graphs

The random graphG(n, p) onn vertices with edge probabilityp = c/n contains an induced tree of order _c n where _c > 0 forc > 1. This proves a conjecture of Erdös and Palka.     

Large holes in sparse random graphs

We show that there is a function α(r) such that for each constantr≧3, almost everyr-regular graph onn vertices has a hole (vertex induced cycle) of size at least α(r)n asn→∞. We also show that there is a function β(c) such that forc>0 large enough,G _{n, p} ,p=c/n almost surely has a hole of size at least β(c)n asn→∞.     

Long paths in sparse random graphs

We consider random graphs withn labelled vertices in which edges are chosen independently and with probabilityc/n. We prove that almost every random graph of this kind contains a path of length ≧(1 −α(c))n where α(c) is an exponentially decreasing function ofc. Dedicated to Tibor Gallai on his seventieth birthday     

Dynamic choosability of triangle‐free graphs and sparse random graphs

Ther‐dynamic choosability of a graph G, written , is the least k such that whenever each vertex is assigned a list of at least k colors a proper coloring can be chosen from the lists so that every vertex v has at least neighbors of distinct colors. Let ch(G) denote the choice number of G. In this article, we prove when is bounded. We also show that there exists a constant C such that the random graph with almost surely satisfies . Also if G is a triangle‐free regular graph, then we have .     

Dirac's theorem for random graphs

A classical theorem of Dirac from 1952 asserts that every graph on n vertices with minimum degree at least \begin{align*}\left\lceil n/2 \right\rceil\end{align*} is Hamiltonian. In this paper we extend this result to random graphs. Motivated by the study of resilience of random graph properties we prove that if p ? log n/n, then a.a.s. every subgraph of G(n,p) with minimum degree at least (1/2 + o (1) )np is Hamiltonian. Our result improves on previously known bounds, and answers an open problem of Sudakov and Vu. Both, the range of edge probability p and the value of the constant 1/2 are asymptotically best possible. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Bandwidth theorem for random graphs

A graph G is said to have bandwidth at most b, if there exists a labeling of the vertices by 1,2,…,n, so that |i−j|?b whenever {i,j} is an edge of G. Recently, Böttcher, Schacht, and Taraz verified a conjecture of Bollobás and Komlós which says that for every positive r, Δ, γ, there exists β such that if H is an n-vertex r-chromatic graph with maximum degree at most Δ which has bandwidth at most βn, then any graph G on n vertices with minimum degree at least (1−1/r+γ)n contains a copy of H for large enough n. In this paper, we extend this theorem to dense random graphs. For bipartite H, this answers an open question of Böttcher, Kohayakawa, and Taraz. It appears that for non-bipartite H the direct extension is not possible, and one needs in addition that some vertices of H have independent neighborhoods. We also obtain an asymptotically tight bound for the maximum number of vertex disjoint copies of a fixed r-chromatic graph H₀ which one can find in a spanning subgraph of G(n,p) with minimum degree (1−1/r+γ)np.     

The diameter of sparse random graphs

We derive an expression of the form c ln n + o(ln n) for the diameter of a sparse random graph with a specified degree sequence. The result holds asymptotically almost surely, assuming that certain convergence and supercriticality conditions are met, and is applicable to the classical random graph G_n,p with np = Θ(1) + 1, as well as certain random power law graphs. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Mantel's theorem for random graphs

For a graph G, denote by t(G) (resp. b(G)) the maximum size of a triangle‐free (resp. bipartite) subgraph of G. Of course for any G, and a classic result of Mantel from 1907 (the first case of Turán's Theorem) says that equality holds for complete graphs. A natural question, first considered by Babai, Simonovits and Spencer about 20 years ago is, when (i.e., for what p = p(n)) is the “Erd?s‐Rényi” random graph G = G(n,p) likely to satisfy t(G) = b(G)? We show that this is true if for a suitable constant C, which is best possible up to the value of C. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 59–72, 2015     

Regular pairs in sparse random graphs I

We consider bipartite subgraphs of sparse random graphs that are regular in the sense of Szemerédi and, among other things, show that they must satisfy a certain local pseudorandom property. This property and its consequences turn out to be useful when considering embedding problems in subgraphs of sparse random graphs. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 22: 359–434, 2003