In a 2006 presentation titled EXPANDER GRAPHS - ARE THERE ANY MYSTERIES LEFT?  , Nati Linial posed the following open problem:Which $NP$-hard computational problem on graph remain hard when restricted to expander graphs?Since then, Has any progress been made to prove such result for an $NP$-hard problem?
NP-hard problems on expander graphs?
cc.complexity theory;np hardness;expanders
If unbalanced expanders count as expanders for the purpose of this question (an unbalanced expander: a bipartite graph $G=(A,B,E)$, such that for every subsets $A'\subseteq A$, $B'\subseteq B$, the fraction of edges between $A'$ and $B'$ is about ${|A'||B'|}/{|A||B|}$), then yes, many problems on expanders (e.g., constraint satisfaction problems) are NP-hard to approximate.In particular, the proof of the two-query, low error, PCP Theorem [with Ran Raz in 2008] constructs expander graphs.    