2026-332

As the average degree \( \langle k \rangle \) of an Erdős-Rényi random network increases, the network's topology undergoes distinct phases of evolution. Which of the following statements accurately characterizes the network exactly at its critical point (\( \langle k \rangle = 1 \) )?

A) The size of the largest component scales as \( N^{2/3} \), containing a vanishing fraction of all nodes, and the cluster size distribution follows a power law. 

B) The network lacks a giant component, and the size of the largest cluster scales logarithmically with the total number of nodes. 

C) A giant component emerges that contains a finite fraction of the network's nodes, and the distribution of cluster sizes is exponential. 

D) The giant component absorbs all isolated nodes and clusters, rendering the network fully connected. 

E) None of the above.

Original idea by: João Vianini

2026-331

Regarding the models G(N, p) and G(N, L), choose the correct alternative:

A) Choosing p = 2L/N(N-1) will guarantee that the graphs generated by G(N, p) and G(N, L) have the same number of edges.

B) If N1 > N2 and L > 0, any graph generated by G(N1, p) will have more edges than any graph generated by G(N2, L).

C) For N1 > N2, and p1 > 0,  G(N1, p1) can generate graphs with an impossible number of edges for any graph generated by G(N2, p2) to reach, regardless of the value of p2.

D) The degree distribution of graphs generated by G(N, p) follow a power-law, as very often real-world graphs do.

E) None of the above.

Original idea by: João Pedro Carolino Morais

2026-330

Consider graphs with \(N = 4\) nodes. Below are three sample outcomes of \( G(N, p) \) at different values of \( p \). Dashed lines show absent edges.

  

Which graph is in the supercritical regime?

(A) All three are supercritical since every node has at least one neighbor

(B) Graph A, because it has at least one edge and \( \langle k\rangle = 0.3 > 0 \)

(C) Graph B, because \(\langle k\rangle = 1 \) satisfies the condition for the giant component

(D) Graph C, because \( \langle k\rangle = 2.4 > 1 \) and \( p = 0.8 > p_c = 1/3 \)

(E) None of the above.

Original idea by: Gustavo P. C. P. da Luz

2026-329

A company is looking for people that have really close acquaintances with its three interviewers. Therefore, candidates whose average length to each interviewer are closer to 1 will have the most chances to get the job.

Given the network of acquaintances of each of the following three applicants, indicate which of the following statements are true (T) or False (F).

Robert:

John:

Casey:

1. Casey has the most chances of getting the job.
2. For Robert’s network of aquaintances: If the clustering coeficient of Taylor were higher while maintaining the same degree, then Robert would have more chances of being hired.
3. The chances of Casey getting the job does not depends on knowing Micah, Mary or Harry.
4. John has the least chances of getting the job.

1. F F T T
2. T T T F
3. T F T F
4. T F F F
5. None of the above

Original idea by: Giuliano Macedo

 

2026-328

Consider two random graphs, G_a and G_b, where edges are created independently with probabilities p_a and p_b, respectively. Additionally, consider the following binomial degree distribution:

 

Consider N_a = 200 and  N_b = 100 

Evaluate the following statements:

I) The average degree <k> is higher in graph G_b.  

II) The variance of the degree distribution in G_b  is greater than in G_a .  

III) The expected number of edges in G_a is greater than in G_b.  

Select the correct alternative:

A) Only I is correct.  

B) Only I and II are correct.  

C) Only II and III are correct.  

D) I, II, and III are correct. 

E) None of the above.


Original idea by: Gabriel Ukstin Talasso

2026-327

 In a random network with \( N \gg 1 \) and average degree \( \langle k \rangle = 3 \), what is the expected fraction of nodes with degree 0 or 1?

1. \( 1 - e^{-3} \)
2. \( 4 e^{-3} \)
3. \( 3 e^{-3} \)
4. \( 2 e^{-3} \)
5. None of the above

Original idea by: Antonio De Cesare Del Nero

2026-326

Consider the graph on the figure below. Determine the number of back edges, cross edges, and forward edges generated by the Depth-First Search (DFS) algorithm. Assume the algorithm visits neighboring vertices in ascending order.

A) 2 back edges, 4 cross edges, and 2 forward edges. 

B) 2 back edges, 5 cross edges, and 1 forward edge.

C) 1 back edge, 4 cross edges, and 2 forward edges.

D) 1 back edge, 5 cross edges, and 2 forward edges.

E) None of the above.

Original idea by: Melissa Araújo.