[Python and Sage Question]

All computations should use the SageMath 9.0 kernel. However, you are free to mix Python and Sage functionality in your code.

Problem 2: Diameters of random graphs Grading criteria: code correctness for a; soundness of methodology and thoroughness for b and c. a. Let G be a graph on n vertices. We say that G is compact if any two vertices are connected by a path of length at most log2 n. Write a Python function to test whether a given graph is compact. In [ ]: b. For pe [0,1], consider a graph on n = 100 vertices in which each pair of vertices is joined by an edge with probability p (uniformly at random). Estimate the minimum value of p for which the probability that the resulting graph is compact exceeds 1/2. Justify your guess with some numerical evidence. In [ ]: C. For m a positive integer, consider a graph on n = 100 vertices with exactly m edges, chosen uniformly at random from all graphs with these properties. Estimate the minimum value of m for which the 21 probability that the resulting graph is compact exceeds 1/2. Justify your guess with some numerical evidence. Problem 2: Diameters of random graphs Grading criteria: code correctness for a; soundness of methodology and thoroughness for b and c. a. Let G be a graph on n vertices. We say that G is compact if any two vertices are connected by a path of length at most log2 n. Write a Python function to test whether a given graph is compact. In [ ]: b. For pe [0,1], consider a graph on n = 100 vertices in which each pair of vertices is joined by an edge with probability p (uniformly at random). Estimate the minimum value of p for which the probability that the resulting graph is compact exceeds 1/2. Justify your guess with some numerical evidence. In [ ]: C. For m a positive integer, consider a graph on n = 100 vertices with exactly m edges, chosen uniformly at random from all graphs with these properties. Estimate the minimum value of m for which the 21 probability that the resulting graph is compact exceeds 1/2. Justify your guess with some numerical evidence