Lower bounds for sensitivity of graph properties

2016/09/17 by Ilan Karpas, Karpas, Ilan
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1609.05320

openalex publication_date 2016/09/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that the sensitivity of any non-trivial graph property on n vertices is at least \lfloor (1)/(2)n \rfloor , provided n is sufficiently large.

Related

• Graph Sensitivity under Join and Decomposition
• On the Sensitivity of k-Uniform Hypergraph Properties
• Average Sensitivity of Graph Algorithms
• Sabotage the Mantel Theorem
• Sensitivity Lower Bounds for Approximaiton Algorithms