A correlation inequality and a poisson limit theorem for nonoverlapping balanced subgraphs of a random graph

We consider non-overlapping subgraphs of fixed order in the random graph K_n, p(n). Fix a strictly strongly balanced graph G. A subgraph of K_{n, p(n)} isomorphic to G is called a G-subgraph. Let X_n be the number of G-subgraphs of K_{n, p(n)} vertex disjoint to all other G-subgraphs. We show that if E[X_n]→∞ as n→, then X_n/E[X_n] converges to 1 in probability. Also, if E[X_n]→c as n→∞, then X_n satisfies a Poisson limit theorem. the Poisson limit theorem is shown using a correlation inequality similar to those appeared in Janson, ?uczak, and Ruciñski[8] and Boppana and Spencer [4].     

Covering minimum spanning trees of random subgraphs

We consider the problem of finding a sparse set of edges containing the minimum spanning tree (MST) of a random subgraph of G with high probability. The two random models that we consider are subgraphs induced by a random subset of vertices, each vertex included independently with probability p, and subgraphs generated as a random subset of edges, each edge with probability p. Let n denote the number of vertices, choose p ∈ (0, 1) possibly depending on n, and let b = 1/(1 ? p). We show that in both random models, for any weighted graph G, there is a set of edges Q of cardinality O(n log_bn) that contains the minimum spanning tree of a random subgraph of G with high probability. This result is asymptotically optimal. As a consequence, we also give a bound of O(kn) on the size of the union of all minimum spanning trees of G with some k vertices (or edges) removed. More generally, we show a bound of O(n log_bn) on the size of a covering set in a matroid of rank n, which contains the minimum‐weight basis of a random subset with high probability. Also, we give a randomized algorithm that calls an MST subroutine only a polylogarithmic number of times and finds the covering set with high probability. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Limit theorems for monochromatic stars

Let T(K_1,r,G_n) be the number of monochromatic copies of the r‐star K_1,r in a uniformly random coloring of the vertices of the graph G_n. In this paper we provide a complete characterization of the limiting distribution of T(K_1,r,G_n), in the regime where is bounded, for any growing sequence of graphs G_n. The asymptotic distribution is a sum of mutually independent components, each term of which is a polynomial of a single Poisson random variable of degree at most r. Conversely, any limiting distribution of T(K_1,r,G_n) has a representation of this form. Examples and connections to the birthday problem are discussed.     

Thep-intersection number of a complete bipartite graph and orthogonal double coverings of a clique

Thep-intersection graph of a collection of finite sets {S _i } _i=1 ⁿ is the graph with vertices 1, ...,n such thati, j are adjacent if and only if |S _i S _j |p. Thep-intersection number of a graphG, herein denoted _p (G), is the minimum size of a setU such thatG is thep-intersection graph of subsets ofU. IfG is the complete bipartite graphK _n,n andp2, then _p (K _{n, n} )(n ²+(2p–1)n)/p. Whenp=2, equality holds if and only ifK _n has anorthogonal double covering, which is a collection ofn subgraphs ofK _n , each withn–1 edges and maximum degree 2, such that each pair of subgraphs shares exactly one edge. By construction,K _n has a simple explicit orthogonal double covering whenn is congruent modulo 12 to one of {1, 2, 5, 7, 10, 11}.Research supported in part by ONR Grant N00014-5K0570.     

Covering a graph by topological complete subgraphs

Every graph onn vertices can be covered byex(n, TK ₄ ) =2n – 3 TK ₄ -subgraphs and edges. A similar result might hold for arbitrary topological (complete) subgraphs as indicated by the following result: Every graph onn vertices can be covered by 65ex(n, TK _p )TK _p -subgraphs and edges. IfH is a connected graph (|H| 3) then every graph onn vertices can be covered by 400ex(n, TH) TH-subgraphs and edges. Similar questions for coverings by odd and even cycles are also considered.This author's work was done while he was a guest at the Hungarian Academy of Sciences.     

On martingale tail sums for the path length in random trees

For a martingale (X_n) converging almost surely to a random variable X, the sequence (X_n– X) is called martingale tail sum. Recently, Neininger (Random Structures Algorithms 46 (2015), 346–361) proved a central limit theorem for the martingale tail sum of Régnier's martingale for the path length in random binary search trees. Grübel and Kabluchko (in press) gave an alternative proof also conjecturing a corresponding law of the iterated logarithm. We prove the central limit theorem with convergence of higher moments and the law of the iterated logarithm for a family of trees containing binary search trees, recursive trees and plane‐oriented recursive trees. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 493–508, 2017     

Asymptotic bounds for irredundant and mixed Ramsey numbers

The irredundant Ramsey number s(m, n) is the smallest N such that in every red-blue coloring of the edges of K_N, either the blue graph contains an m-element irredundant set or the red graph contains an n-element irredundant set. The definition of the mixed Ramsey number t(m, n) differs from s(m, n) in that the n-element irredundant set is replaced by an n-element independent set. We prove asymptotic lower bounds for s(n, n) and t(m, n) (with m fixed and n large) and a general upper bound for t(3, n). © 1993 John Wiley & Sons, Inc.     

Vertex Partitions of K4,4-Minor Free Graphs

 We prove that a 4-connected K _4,4-minor free graph on n vertices has at most 4n−8 edges and we use this result to show that every K _4,4-minor free graph has vertex-arboricity at most 4. This improves the case (n,m)=(7,3) of the following conjecture of Woodall: the vertex set of a graph without a K _n -minor and without a -minor can be partitioned in n−m+1 subgraphs without a K _m -minor and without a -minor. Received: January 7, 1998 Final version received: May 17, 1999     

The Reverse H‐free Process for Strictly 2‐Balanced Graphs

Consider the random graph process that starts from the complete graph on n vertices. In every step, the process selects an edge uniformly at random from the set of edges that are in a copy of a fixed graph H and removes it from the graph. The process stops when no more copies of H exist. When H is a strictly 2‐balanced graph we give the exact asymptotics on the number of edges remaining in the graph when the process terminates and investigate some basic properties namely the size of the maximal independent set and the presence of subgraphs.     

Multiplicities of subgraphs

A former conjecture of Burr and Rosta [1], extending a conjecture of Erds [2], asserted that in any two-colouring of the edges of a large complete graph, the proportion of subgraphs isomorphic to a fixed graphG which are monochromatic is at least the proportion found in a random colouring. It is now known that the conjecture fails for some graphsG, includingG=K _p forp4.We investigate for which graphsG the conjecture holds. Our main result is that the conjecture fails ifG containsK ₄ as a subgraph, and in particular it fails for almost all graphs.     

The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph

The minimal weight of a spanning tree in a complete graph K_n with independent, uniformly distributed random weights on the edges is shown to have an asymptotic normal distribution. The proof uses a functional limit extension of results by Barbour and Pittel on the distribution of the number of tree components of given sizes in a random graph.     

Mutually orthogonal graph squares

A decomposition ??={G₁, G₂,…,G_s} of a graph G is a partition of the edge set of G into edge‐disjoint subgraphs G₁, G₂,…,G_s. If G_i?H for all i∈{1, 2, …, s}, then ?? is a decomposition of G by H. Two decompositions ??={G₁, G₂, …, G_n} and ?={F₁, F₂,…,F_n} of the complete bipartite graph K_n,n are orthogonal if |E(G_i)∩E(F_j)|=1 for all i,j∈{1, 2, …, n}. A set of decompositions {??₁, ??₂, …, ??_k} of K_{n, n} is a set of k mutually orthogonal graph squares (MOGS) if ??_i and ??_j are orthogonal for all i, j∈{1, 2, …, k} and i≠j. For any bipartite graph G with n edges, N(n, G) denotes the maximum number k in a largest possible set {??₁, ??₂, …, ??_k} of MOGS of K_{n, n} by G. El‐Shanawany conjectured that if p is a prime number, then N(p, P_{p+ 1})=p, where P_{p+ 1} is the path on p+ 1 vertices. In this article, we prove this conjecture. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 369–373, 2009     

Probabilistic analysis of a parallel algorithm for finding the lexicographically first depth first search tree in a dense random graph

We describe an O((log n)²) time parallel algorithm, using n processors, for finding the lexicographically first depth first search tree in the random graph G _{n, p}, with p fixed. The problem itself is complete for P, and so is unlikely to be efficiently parallelizable always.     

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.     

On the variance of the random sphere of influence graph

We show that the variance of the number of edges in the random sphere of influence graph built on n i.i.d. sites which are uniformly distributed over the unit cube in R ^d, grows linearly with n. This is then used to establish a central limit theorem for the number of edges in the random sphere of influence graph built on a Poisson number of sites. Some related proximity graphs are discussed as well. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 139–152, 1999     

Restricted greedy clique decompositions and greedy clique decompositions ofK 4-free graphs

A greedy clique decomposition of a graph is obtained by removing maximal cliques from a graph one by one until the graph is empty. It has recently been shown that any greedy clique decomposition of a graph of ordern has at mostn ²/4 cliques. In this paper, we extend this result by showing that for any positive integerp, 3≤p any clique decomposisitioof a graph of ordern obtained by removing maximal cliques of order at leastp one by one until none remain, in which case the remaining edges are removed one by one, has at mostt _p-1( ⁿ ) cliques. Heret _p-1( ⁿ ) is the number of edges in the Turán graph of ordern, which has no complete subgraphs of orderp. In connection with greedy clique decompositions, P. Winkler conjectured that for any greedy clique decompositionC of a graphG of ordern the sum over the number of vertices in each clique ofC is at mostn ²/2. We prove this conjecture forK ₄-free graphs and show that in the case of equality forC andG there are only two possibilities:

1. G?K _n/2,n/2
2. G is complete 3-partite, where each part hasn/3 vertices.

We show that in either caseC is completely determined.     

Distance-2-Matchings of Random Graphs

In this paper we study the maximal size of a distance-2-matching in a random graph G _n;M , i.e., the probability space consisting of subgraphs of the complete graph over n vertices, K _n , having exactly M edges and uniform probability measure. A distance-2-matching in a graph Y, M ₂, is a set of Y-edges with the property that for any two elements every pair of their 4 incident vertices has Y-distance 2. Let M₂(Y) be the maximal size of a distance-2-matching in Y. Our main results are the derivation of a lower bound for M₂(Y) and a sharp concentration result for the random variable AMS Subject Classification: 05C80, 05C70.     

Two remarks on the Burr–Erdős conjecture

The Ramsey number r(H) of a graph H is the minimum positive integer N such that every two-coloring of the edges of the complete graph K_N on N vertices contains a monochromatic copy of H. A graph H is d-degenerate if every subgraph of H has minimum degree at most d. Burr and Erdős in 1975 conjectured that for each positive integer d there is a constant c_d such that r(H)≤c_dn for every d-degenerate graph H on n vertices. We show that for such graphs , improving on an earlier bound of Kostochka and Sudakov. We also study Ramsey numbers of random graphs, showing that for d fixed, almost surely the random graph G(n,d/n) has Ramsey number linear in n. For random bipartite graphs, our proof gives nearly tight bounds.     

On two Hamilton cycle problems in random graphs

We study two problems related to the existence of Hamilton cycles in random graphs. The first question relates to the number of edge disjoint Hamilton cycles that the random graph G _n,p contains. δ(G)/2 is an upper bound and we show that if p ≤ (1 + o(1)) ln n/n then this upper bound is tight whp. The second question relates to how many edges can be adversarially removed from G _n,p without destroying Hamiltonicity. We show that if p ≥ K ln n/n then there exists a constant α > 0 such that whp G − H is Hamiltonian for all choices of H as an n-vertex graph with maximum degree Δ(H) ≤ αK ln n. Research supported in part by NSF grant CCR-0200945. Research supported in part by USA-Israel BSF Grant 2002-133 and by grant 526/05 from the Israel Science Foundation.     

Graphs with unavoidable subgraphs with large degrees

Let ??(n, m) denote the class of simple graphs on n vertices and m edges and let G ∈ ?? (n, m). There are many results in graph theory giving conditions under which G contains certain types of subgraphs, such as cycles of given lengths, complete graphs, etc. For example, Turan's theorem gives a sufficient condition for G to contain a K_{k + 1} in terms of the number of edges in G. In this paper we prove that, for m = αn², α > (k - 1)/2k, G contains a K_{k + 1}, each vertex of which has degree at least f(α)n and determine the best possible f(α). For m = ?n²/4? + 1 we establish that G contains cycles whose vertices have certain minimum degrees. Further, for m = αn², α > 0 we establish that G contains a subgraph H with δ(H) ≥ f(α, n) and determine the best possible value of f(α, n).