On the variance of random polytopes

A random polytope is the convex hull of uniformly distributed random points in a convex body K. A general lower bound on the variance of the volume and f-vector of random polytopes is proved. Also an upper bound in the case when K is a polytope is given. For polytopes, as for smooth convex bodies, the upper and lower bounds are of the same order of magnitude. The results imply a law of large numbers for the volume and f-vector of random polytopes when K is a polytope.     

On the genus of a random graph

Let p = p(n) be a function of n with 0<p<1. We consider the random graph model ??(n, p); that is, the probability space of simple graphs with vertex-set {1, 2,…, n}, where two distinct vertices are adjacent with probability p. and for distinct pairs these events are mutually independent. Archdeacon and Grable have shown that if p²(1 ? p²) ?? 8(log n)⁴/n. then the (orientable) genus of a random graph in ??(n, p) is (1 + o(1))pn²/12. We prove that for every integer i ? 1, if n^?i/(i + 1) «p «n^{?(i ? 1)/i}. then the genus of a random graph in ??(n, p) is (1 + o(1))i/4(i + 2) pn². If p = cn^?(i?1)/o, where c is a constant, then the genus of a random graph in ??(n, p) is (1 + o(1))g(i, c, n)pn² for some function g(i, c, n) with 1/12 ? g(i, c, n) ? 1. but for i > 1 we were unable to compute this function.     

On the total variation distance between the binomial random graph and the random intersection graph

When each vertex is assigned a set, the intersection graph generated by the sets is the graph in which two distinct vertices are joined by an edge if and only if their assigned sets have a nonempty intersection. An interval graph is an intersection graph generated by intervals in the real line. A chordal graph can be considered as an intersection graph generated by subtrees of a tree. In 1999, Karoński, Scheinerman, and Singer‐Cohen introduced a random intersection graph by taking randomly assigned sets. The random intersection graph has n vertices and sets assigned to the vertices are chosen to be i.i.d. random subsets of a fixed set M of size m where each element of M belongs to each random subset with probability p, independently of all other elements in M. In 2000, Fill, Scheinerman, and Singer‐Cohen showed that the total variation distance between the random graph and the Erdös‐Rényi graph tends to 0 for any if , where is chosen so that the expected numbers of edges in the two graphs are the same. In this paper, it is proved that the total variation distance still tends to 0 for any whenever .     

On the average genus of the random graph

The generalized Petersen graph GP (n, k), n ≤ 3, 1 ≥ k < n/2 is a cubic graph with vertex-set {u_j; i ? Z_n} ∪ {v_j; i ? Z_n}, and edge-set {u_iu_i, u_iv_i, v_iv_{i+k, i?}Z_n}. In the paper we prove that (i) GP(n, k) is a Cayley graph if and only if k² ? 1 (mod n); and (ii) GP(n, k) is a vertex-transitive graph that is not a Cayley graph if and only if k² ? -1 (mod n) or (n, k) = (10, 2), the exceptional graph being isomorphic to the 1-skeleton of the dodecahedon. The proof of (i) is based on the classification of orientable regular embeddings of the n-dipole, the graph consisting of two vertices and n parallel edges, while (ii) follows immediately from (i) and a result of R. Frucht, J.E. Graver, and M.E. Watkins [“The Groups of the Generalized Petersen Graphs,” Proceedings of the Cambridge Philosophical Society, Vol. 70 (1971), pp. 211-218]. © 1995 John Wiley & Sons, Inc.     

On the cycle space of a random graph

Write for the cycle space of a graph G, for the subspace of spanned by the copies of the κ‐cycle in G, for the class of graphs satisfying , and for the class of graphs each of whose edges lies in a . We prove that for every odd and , so the 's of a random graph span its cycle space as soon as they cover its edges. For κ = 3 this was shown in [6].     

On k-leaf connectivity of a random graph

We prove that, in a random graph with n vertices and N = cn log n edges, the subgraph generated by a set of all vertices of degree at least k + 1 is k-leaf connected for c > 1/4. A threshold function for k-leaf connectivity is also found.     

On the chromatic forcing number of a random graph

When we wish to compute lower bounds for the chromatic number χ(G) of a graph G, it is of interest to know something about the ‘chromatic forcing number’ f_χ(G), which is defined to be the least number of vertices in a subgraph H of G such that χ(H) = χ(G). We show here that for random graphs G_n,p with n vertices, f_χ(G_n,p) is almost surely at least ($\text{1}\text{2}$?ε)n, despite say the fact that the largest complete subgraph of G_n,p has only about log n vertices.     

On a random graph evolving by degrees

We consider a random (multi)graph growth process {Gm} on a vertex set [n], which is a special case of a more general process proposed by Laci Lovász in 2002. G₀ is empty, and Gm+1 is obtained from Gm by inserting a new edge e at random. Specifically, the conditional probability that e joins two currently disjoint vertices, i and j, is proportional to (di+α)(dj+α), where di, dj are the degrees of i, j in Gm, and α>0 is a fixed parameter. The limiting case α=∞ is the Erd?s-Rényi graph process. We show that whp Gm contains a unique giant component iff c:=2m/n>cα=α/(1+α), and the size of this giant is asymptotic to , where c^∗<cα is the root of . A phase transition window is proved to be contained, essentially, in [cα−An−1/3,cα+Bn−1/4], and we conjecture that 1/4 may be replaced with 1/3. For the multigraph version, {MGm}, we show that MGm is connected whp iff m?mn:=n1+α−1. We conjecture that, for α>1, mn is the threshold for connectedness of Gm itself.     

On the degrees of vertices in A bichromatic random graph

The asymptotic probability distribution of the number of vertices of a given degree in a random bichromatic graph is presented.     

On the number of hamilton cycles in a random graph

Let a random graph G be constructed by adding random edges one by one, starting with n isolated vertices. We show that with probability going to one as n goes to infinity, when G first has minimum degree two, it has at least (log n) distinct hamilton cycles for any fixed ?>0.     

On the sizes of large subgraphs of the binomial random graph

We consider the binomial random graph $G(n,p)$, where p is a constant, and answer the following two questions.First, given $e(k)=p\left(\begin{array}{c}k\\ 2\end{array}\right)+O(k)$, what is the maximum k such that a.a.s. the binomial random graph $G(n,p)$ has an induced subgraph with k vertices and $e(k)$ edges? We prove that this maximum is not concentrated in any finite set (in contrast to the case of a small $e(k)$). Moreover, for every constant $C>0$, with probability bounded away from 0, the size of the concentration set is bigger than $C\sqrt{n/\ln ?n}$, and, for every ${\omega }_n\to \infty$, a.a.s. it is smaller than ${\omega }_n\sqrt{n/\ln ?n}$.Second, given $k>\epsilon n$, what is the maximum μ such that a.a.s. the set of sizes of k-vertex subgraphs of $G(n,p)$ contains a full interval of length μ? The answer is $\mu =\mathrm{\Theta }\left(\sqrt{(n?k)n\ln ?\left(\begin{array}{c}n\\ k\end{array}\right)}\right)$.     

On upper bounds for the variance of functions of random variables

The upper bounds for the variance of a function g of a random variable X obtained in Cacoullos (1982) (for short CP) are improved in the case μ = E(X) ≠ 0. A main feature of these bounds is that they involve the second moment of the derivative or the difference of g. A multivariate extension for functions of independent random variables is also given.     

On limit points of spectra of the random graph first-order properties

New bounds on the minimum and maximum limit points of spectra of first-order properties of the Erdös–Rényi random graph are obtained. These results are used to improve bounds on the minimal quantifier depths of first-order formulas with infinite spectra. Moreover, we prove that there are no limit points of the spectra in the interval (1–2^1–k , 1).     

On the chromatic number of a random subgraph of the Kneser graph

Results are obtained that substantially strengthen a previously known bound for the chromatic number of a random subgraph of the Kneser graph.