Counterexamples to “A conjecture on induced subgraphs of Cayley graphs”

Show simple item record

dc.contributor.author Lehner, Florian
dc.contributor.author Verret, Gabriel
dc.date.accessioned 2021-01-15T01:34:56Z
dc.date.available 2021-01-15T01:34:56Z
dc.date.issued 2020-11-7
dc.identifier.citation Ars Mathematica Contemporanea 19(1):77-82 07 Nov 2020
dc.identifier.issn 1855-3966
dc.identifier.uri https://hdl.handle.net/2292/54275
dc.description.abstract © 2020 Society of Mathematicians, Physicists and Astronomers of Slovenia. All rights reserved. Recently, Huang gave a very elegant proof of the Sensitivity Conjecture by proving that hypercube graphs have the following property: Every induced subgraph on a set of more than half the vertices has maximum degree at least √ d, where d is the valency of the hypercube. This was generalised by Alon and Zheng who proved that every Cayley graph on an elementary abelian 2-group has the same property. Very recently, Potechin and Tsang proved an analogous results for Cayley graphs on abelian groups. They also conjectured that all Cayley graphs have the analogous property. We disprove this conjecture by constructing various counterexamples, including an infinite family of Cayley graphs of unbounded valency which admit an induced subgraph of maximum valency 1 on a set of more than half the vertices.
dc.language en
dc.publisher University of Primorska Press
dc.relation.ispartofseries Ars Mathematica Contemporanea
dc.rights Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
dc.rights.uri https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
dc.rights.uri https://creativecommons.org/licenses/by/4.0/
dc.subject 0101 Pure Mathematics
dc.subject 0102 Applied Mathematics
dc.subject 0104 Statistics
dc.title Counterexamples to “A conjecture on induced subgraphs of Cayley graphs”
dc.type Journal Article
dc.identifier.doi 10.26493/1855-3974.2301.63f
pubs.issue 1
pubs.begin-page 77
pubs.volume 19
dc.date.updated 2020-12-18T02:50:29Z
dc.rights.holder Copyright: The authors en
pubs.end-page 82
pubs.publication-status Published online
dc.rights.accessrights http://purl.org/eprint/accessRights/OpenAccess en
pubs.subtype Journal Article
pubs.elements-id 832113
dc.identifier.eissn 1855-3974
pubs.online-publication-date 2020-11-7


Files in this item

Find Full text

This item appears in the following Collection(s)

Show simple item record

Share

Search ResearchSpace


Browse

Statistics