Resilience (mathematics)

The resilience of a graph property P with respect to a graph G is the minimum over all graphs H on the same vertex set that do not satisfy P of the ratio of the number of edges in the symmetric difference between G and H to the number of edges in G. In other words, it is the largest fraction of edges that can be removed from G without destroying property P, assuming the deletion is adversarial. This definition extends naturally to vertex deletion and to properties of random graphs, where one considers the resilience of a property in the G(n,p) model. The concept was formalized by Krivelevich, Sudakov, and others in the context of extremal graph theory, building on earlier notions of stability and robustness in combinatorics.¹

One of the landmark results is that the complete graph K_n has edge-resilience of 1/2 for Hamiltonicity: one can delete up to half of the edges and still guarantee a Hamiltonian cycle, but deleting more may destroy it. This result, proved by Krivelevich and Sudakov, extends to Dirac graphs (graphs with minimum degree at least n/2), where the vertex-resilience for Hamiltonicity is also n/2. For random graphs G(n,p), the resilience of properties like having a perfect matching or being Hamiltonian has been determined asymptotically, showing that these properties are highly robust to random edge deletion. These findings have direct implications for network reliability, where resilience quantifies how many link failures a communication network can tolerate before losing connectivity or routing capabilities.²

Resilience has several variants: edge-resilience, vertex-resilience, and local resilience, where the latter restricts deletions to a neighborhood of each vertex. Local resilience is particularly relevant in percolation theory and in the study of random regular graphs. Another related concept is stability, which in extremal combinatorics refers to the structural rigidity of extremal examples; resilience can be seen as a quantitative version of stability. The notion also connects to fault-tolerance in distributed computing and to the robustness of Boolean functions in theoretical computer science. Recent work has extended resilience to hypergraphs and to properties of directed graphs, broadening its applicability.

Beyond the classical results, resilience has surprising connections to game theory: in the Maker-Breaker game, the resilience of a property determines the threshold for the breaker to win. Also, the concept has been applied to Ramsey theory, where one studies the resilience of Ramsey properties in random graphs. A niche application is in cryptography, where the resilience of expander graphs under edge deletion is used to design robust pseudorandom generators. Historically, the idea of resilience appears implicitly in the work of Erdős and Rényi on random graphs, but it was only formalized later. The term "resilience" was popularized by Sudakov's 2004 survey, which highlighted its role in unifying several extremal problems.³

Hamiltonicity

The property of a graph having a Hamiltonian cycle, i.e., a cycle that visits every vertex exactly once.

Dirac graph

A graph on n vertices with minimum degree at least n/2, which guarantees a Hamiltonian cycle by Dirac's theorem.

G(n,p)

The Erdős–Rényi random graph model where each possible edge appears independently with probability p.

Local resilience

A variant of resilience where deletions are limited to the neighborhood of each vertex, measuring robustness under localized failures.

Maker-Breaker game

A positional game where two players, Maker and Breaker, alternately claim edges; Maker wins if he claims all edges of a target structure.