English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Recently, Huang gave a very elegant proof of the Sensitivity Conjecture byproving that hypercube graphs have the following property: every inducedsubgraph on a set of more than half its vertices has maximum degree at least$\sqrt{d}$, where $d$ is the valency of the hypercube. This was generalised byAlon and Zheng who proved that every Cayley graph on an elementary abelian$2$-group has the same property. Very recently, Potechin and Tsang proved ananalogous results for Cayley graphs on abelian groups. They also conjecturedthat all Cayley graphs have the analogous property. We disprove this conjectureby constructing various counterexamples, including an infinite family of Cayleygraphs of unbounded valency which admit an induced subgraph of maximum valency$1$ on a set of more than half its vertices.

Counterexamples to "A Conjecture on Induced Subgraphs of Cayley Graphs" [arXiv:2003.13166]