Source-linked AI summary
Local resilience of graphs
Benny Sudakov, Van Vu
TL;DR
The paper asks how strongly a graph possesses a property and studies resilience as the amount of change needed to destroy it. It estimates local resilience in random and pseudo-random graphs, including sharp bounds for perfect matching and Hamiltonicity. These estimates are made against an adversary whose bounded-degree changes may be chosen separately for each sampled graph.
Problem
Method
The authors estimate local resilience in random and pseudo-random graphs with respect to several graph properties.
Source: §2 · p. 4Results
For p ≫ log n/n, G(n,p)'s local resilience for a perfect matching is (1/2 + o(1))np; for p > log^4 n/n, its local resilience for Hamiltonicity is (1/2 + o(1))np.
Source: §2.1 · p. 4, §2.2 · p. 5Takeaways & Limitations
Some of the obtained local-resilience estimates for random and pseudo-random graphs are asymptotically best possible.
Source: §2 · p. 4For each sampled G(n,p), the adversary may choose a graph H with the smallest possible maximum degree to destroy P, and H may vary between samples.
Source: §2 · p. 3
Abstract
from arXiv · showhide
In this paper, we initiate a systematic study of graph resilience. The (local) resilience of a graph G with respect to a property P measures how much one has to change G (locally) in order to destroy P. Estimating the resilience leads to many new and challenging problems. Here we focus on random and pseudo-random graphs and prove several sharp results.
1 The notion of resilience
Resilience measures how much a graph must change to destroy a property, with local resilience bounding changes at each vertex. The paper presents local resilience as a useful parameter for global properties such as Hamiltonicity and as a basis for new questions and applications.
1 The notion of resilience
- Resilience measures how many changes destroy P: global resilience counts edge deletions, while local resilience bounds changes at each vertex.For non-monotone properties, local changes may include both additions and deletions.Source: §1 · pp. 1–2
- Deleting all edges at one vertex destroys Hamiltonicity, while K_n's local resilience for Hamiltonicity is ⌊n/2⌋.The paper presents this formulation of Dirac's classical theorem [6].Source: §1 · pp. 1–2
- The property and resilience scale are linked: global resilience suits local properties such as containing a triangle, while local resilience suits global properties such as Hamiltonicity.Source: §1 · p. 2
- The authors aim to systematically investigate resilience, which they also describe as a useful tool for proving results and as relevant to row-wise message tampering.In the communication example, high local resilience means an adversary limited to changing a few bits per row cannot prevent recovery of the graph property of interest.Source: §1 · pp. 2–3
- Examples of new questions include hypercube resilience against perfect matchings and how many Hadamard-matrix entries must change to make it singular.For the hypercube, this is also phrased as finding the minimum degree of a subgraph containing an edge from every perfect matching.Source: §1 · p. 2
2 The resilience of random graphs
The section studies typical local resilience in random graphs, where after each graph is sampled an adversary can choose a damaging modification. It gives bounds for matching, Hamiltonicity, chromatic number, and symmetry, including sharp results for several properties.
2 The resilience of random graphs
- Local resilience is defined by the minimum maximum degree of a modification that destroys a property; the section studies its typical value in G(n, p), allowing the adversary to choose a modification after sampling.The paper states that its G(n, p) results also hold for the uniform distribution on graphs with the same number of edges.Source: §2 · pp. 3–4
2.1 Perfect matching
- For even n and p ≫ log n/n, the local resilience of G(n, p) with respect to having a perfect matching is (1/2 + o(1))np.This matches the bound from deleting edges inside a set of n/2 + 1 vertices; for odd n, the result also holds for nearly perfect matchings.Source: §2.1 · p. 4
2.2 Hamiltonicity
- For p > log^4 n/n, the local resilience of G(n, p) with respect to Hamiltonicity is (1/2 + o(1))np.The proof uses edge-distribution properties and extends to pseudorandom graphs; for an (n, D, λ)-graph with D/λ > log^2 n, the resilience is (1/2 + o(1))D.Source: §2.2 · p. 5
2.3 Chromatic number
- For n^(-1/3+ε) ≤ p ≤ 3/4, the local resilience lower bound for (1 + o(1))n/(2 log_b(np))-colorability is np^2/log^5 n.At p = 1/2, this bound is off by only a polylogarithmic factor; below the stated lower range, the paper gives a weaker result.Source: §2.3 · p. 5
- For fixed d and p > c/n, adding any graph of maximum degree d has very little impact on the chromatic number of most G(n, p) graphs.The theorem applies when the average degree is at least a constant sufficiently large compared with d.Source: §2.3 · pp. 5–6
2.4 Symmetry
- When p and 1 − p are both ≫ log n/n, the global and local resilience of G(n, p) against being non-symmetric are (2 + o(1))np(1 − p) and (1 + o(1))np(1 − p), respectively.The paper also describes using local resilience to prove that random regular graphs with large degrees are almost surely non-symmetric.Source: §2.4 · p. 6
3 Perfect matchings
For sufficiently dense G(n,p), the section establishes perfect-matching resilience through a lower bound under bounded-degree deletions and a matching-destroying construction.
3 Perfect matchings
- For p ≥400 log n/n, deleting at most np/2−8√(np log n) edges per vertex still leaves a perfect matching.The lower-bound proof removes a subgraph H with that maximum-degree bound and shows G−H contains a perfect matching.Source: §3 · pp. 7–8
- For p ≥400 log n/n, the proof uses bounds on minimum degree, induced-set maximum degree, and edges between disjoint small sets.These random-graph properties support both the resilience lower bound and the matching-destroying construction.Source: §3 · p. 7
- The lower-bound proof randomly bipartitions the retained graph and finds a bipartite subgraph satisfying Hall’s condition.A partition with sufficiently large degree at every vertex is chosen before verifying Hall’s condition.Source: §3 · pp. 8–9
- Conversely, deleting all edges inside a set of n/2+1 vertices can destroy every perfect matching, since the complement has only n/2−1 vertices.The set becomes independent, so its vertices cannot all be matched to the smaller complement.Source: §3 · pp. 7, 9
4 Hamilton cycles
This section studies the local resilience of Hamiltonicity in dense pseudorandom graphs, sparse random graphs, and sparse pseudorandom graphs, establishing conditions under which deleting fewer than roughly half the incident edges at each vertex preserves a Hamilton cycle. It develops an expansion criterion and rotation-extension methods, including an endpoint-set procedure for sparse random graphs and a spectral-condition result for sparse pseudorandom graphs.
4.1 ǫ-regular graphs
- In a (d, ε)-regular graph, deleting a subgraph of maximum degree at most (d/2 − c_dε)n, where c_d = 8/d, preserves a Hamilton cycle.For fixed 0 < p < 1, this implies that almost surely deleting at most (1/2 − ε)np edges per vertex from G(n, p) cannot destroy all Hamilton cycles; the passage says the constant 1/2 cannot be improved.Source: §4.1 · p. 9
- For dense regular graphs, the proof uses Pósa’s rotation-extension technique to obtain maximum-length paths and close one to a Hamilton cycle.The graph remaining after deletions is connected, so a non-Hamilton cycle can be extended to a path covering additional vertices; maximality then forces the closed path to be Hamiltonian.Source: §4.1 · pp. 10–11
4.2 Sparse random graphs
- For fixed ε > 0 and p ≥ log^4 n/n, almost surely deleting any subgraph of maximum degree at most (1/2 − ε)np from G(n, p) leaves a Hamilton cycle.This is the sparse random graph resilience result.Source: §4.2 · p. 11
- Every connected n-vertex graph with the stated small-set and large-set neighborhood expansion conditions contains a Hamilton cycle.The conditions are |N_G(U)| ≥ |U|log^4 n/15 for |U| ≤ n/log^4 n and |N_G(W)| ≥ (1 + ε)n/2 for |W| ≥ n/log^3 n.Source: §4.2 · p. 13
- Sparse-graph hamiltonicity is proved by repeated rotations that enlarge endpoint sets by a factor of log n per round while preserving shared path segments, until a longest path can be closed to a cycle.The construction takes roughly log n/log log n rounds; the final closing step uses the expansion conditions.Source: §4.2 · p. 13
- In sparse random graphs, rotations in each of three cases enlarge the left endpoint set by ≫ log² n while preserving a universal order of broken edges across the new paths.In the third case, the procedure selects many neighbors within a segment and uses them as rotation pivots.Source: §4.2 · pp. 17–19
4.3 Sparse pseudo-random graphs
- After deleting H with maximum degree at most (1/2 − ε)D, the pseudorandom graph retains small-set expansion, and every connected component has size larger than n/2.The small-set bound is |N_G′(U)| ≥ |U| log⁴ n/15 for |U| ≤ n/log⁴ n; the component bound implies G′ is connected.Source: §4.3 · pp. 19–20
- If D/λ > log² n, deleting any subgraph of maximum degree at most (1/2 − ε)D from an (n, D, λ)-graph leaves a Hamilton cycle.Thus the local resilience with respect to hamiltonicity is at least (1/2 − ε)D.Source: §4.3 · p. 20
- The hamiltonicity resilience condition can be weakened to D/λ > log^{1+δ} n, and the corresponding sparse-random-graph threshold is p ≥ log^{2+δ} n/n.These bounds hold for any fixed δ > 0.Source: §4.3 · p. 20
5 Chromatic number
For random graphs, bounded-degree perturbations preserve the chromatic number asymptotically across stated probability ranges. The section proves this by partitioning vertices and repairing a coloring, and by repeatedly extracting independent sets in denser regimes.
Theorem 2.7
- The proof of Theorem 2.7 partitions vertices into parts, colors each induced random-graph subgraph separately, then recolors vertices incident to remaining monochromatic edges.The exceptional vertices induce a degenerate subgraph, which can be colored with fresh colors.Source: §5 · p. 21
- For p > c/n, the chromatic number after adding a graph of maximum degree d can be kept below (1 + ε)χ(G(n, p)) almost surely.For p = n^-α with constant α < 1, the assertion remains valid when the added graph has maximum degree as large as e log^(1−δ)n, for δ > 0.Source: §5 · pp. 20–21
Theorem 5.3
- Theorem 5.3 considers edge probabilities n^-1/3+ε ≤ p ≤ 3/4 and maximizes over added graphs with maximum degree at most np^2.The section invokes the asymptotic chromatic number of G(n, p) and concentration results as background.Source: §5 · pp. 20, 22
- For constant p, adding any graph with maximum degree O(n/log^5 n) does not affect the asymptotic chromatic number, and this degree bound is best possible up to a polylogarithmic factor.Theorem 5.3 applies when n^-1/3+ε ≤ p ≤ 3/4; the stated constant-p consequence and sharpness qualification are given separately.Source: §5 · p. 22
- For Theorem 5.3, large vertex subsets retain independent sets even after the perturbation, allowing the graph to be colored by repeatedly removing and coloring such sets.The remaining small vertex set is handled using a degeneracy bound.Source: §5 · pp. 21–23
6 Concluding remarks
The concluding remarks connect local resilience to transfer results between random graph models and report evidence for unbounded local resilience in important properties. They leave open questions about Hamiltonicity and a further resilience assertion for random graphs.
6.1 Local resilience and universality
- Earlier work used local resilience to transfer properties from G(n, p) to random regular graphs of approximately the same density when the property holds almost surely and has unbounded local resilience.That work called the notion “tolerance.”Source: §6.1 · p. 23
- The paper's results support the conjecture that natural graph properties have unbounded local resilience when p is sufficiently large, and bear on whether the random regular graph model is monotone in d.The authors say their results establish unbounded local resilience for some important properties.Source: §6.1 · p. 23
6.2 A few open problems
- The open problems ask for the local resilience of G(n, p) with respect to Hamiltonicity when pn/log n tends to infinity, and pose a further assertion for n^-1+δ ≤ p ≤ 3/4 and perturbations with d = o(np/log(np)).The statement of the second assertion is incomplete in the supplied passage.Source: §6.2 · p. 23