{"?xml":{"@version":"1.0"},"edm:RDF":{"@xmlns:dc":"http://purl.org/dc/elements/1.1/","@xmlns:edm":"http://www.europeana.eu/schemas/edm/","@xmlns:wgs84_pos":"http://www.w3.org/2003/01/geo/wgs84_pos","@xmlns:foaf":"http://xmlns.com/foaf/0.1/","@xmlns:rdaGr2":"http://rdvocab.info/ElementsGr2","@xmlns:oai":"http://www.openarchives.org/OAI/2.0/","@xmlns:owl":"http://www.w3.org/2002/07/owl#","@xmlns:rdf":"http://www.w3.org/1999/02/22-rdf-syntax-ns#","@xmlns:ore":"http://www.openarchives.org/ore/terms/","@xmlns:skos":"http://www.w3.org/2004/02/skos/core#","@xmlns:dcterms":"http://purl.org/dc/terms/","edm:WebResource":[{"@rdf:about":"http://www.dlib.si/stream/URN:NBN:SI:doc-10EH7ZFN/b442d8eb-373d-4b12-87af-d04c4ff4cc39/PDF","dcterms:extent":"247 KB"},{"@rdf:about":"http://www.dlib.si/stream/URN:NBN:SI:doc-10EH7ZFN/8c219f7a-a01a-449f-baf5-95054522194c/TEXT","dcterms:extent":"12 KB"}],"edm:TimeSpan":{"@rdf:about":"2008-2025","edm:begin":{"@xml:lang":"en","#text":"2008"},"edm:end":{"@xml:lang":"en","#text":"2025"}},"edm:ProvidedCHO":{"@rdf:about":"URN:NBN:SI:doc-10EH7ZFN","dcterms:isPartOf":[{"@rdf:resource":"https://www.dlib.si/details/URN:NBN:SI:spr-UP1WMFAR"},{"@xml:lang":"sl","#text":"Ars mathematica contemporanea"}],"dcterms:issued":"2020","dc:creator":["Lehner, Florian","Verret, Gabriel"],"dc:format":[{"@xml:lang":"sl","#text":"številka:1"},{"@xml:lang":"sl","#text":"letnik:19"},{"@xml:lang":"sl","#text":"str. 77-82"}],"dc:identifier":["ISSN:1855-3974","COBISSID_HOST:43107843","URN:URN:NBN:SI:doc-10EH7ZFN"],"dc:language":"en","dc:publisher":{"@xml:lang":"sl","#text":"Univerza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologije"},"dc:subject":[{"@xml:lang":"en","#text":"Cayley graphs"},{"@xml:lang":"sl","#text":"Cayleyevi grafi"},{"@xml:lang":"sl","#text":"občutljivostna domneva"},{"@xml:lang":"en","#text":"sensitivity conjecture"},{"@xml:lang":"sl","#text":"točkovno tranzitivni grafi"},{"@xml:lang":"en","#text":"vertex-transitive graphs"}],"dcterms:temporal":{"@rdf:resource":"2008-2025"},"dc:title":{"@xml:lang":"sl","#text":"Counterexamples to \"A conjecture on induced subgraphs of Cayley graphs\"|"},"dc:description":[{"@xml:lang":"sl","#text":"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 ?$\\sqrt{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"},{"@xml:lang":"sl","#text":"Nedavno je Huang predstavil zelo eleganten dokaz t. i. občutljivostne domneve, ko je dokazal, da imajo grafi hiperkock naslednjo lastnost: vsak induciran podgraf na množici, ki vsebuje več kot polovico točk, ima maksimalno stopnjo najmanj ?$\\sqrt{d}$?, kjer je ?$d$? valenca hiperkocke. Ta rezultat sta posplošila Alon in Zheng, ki sta dokazala, da ima vsak Cayleyev graf na elementarni abelski 2-grupi isto lastnost. Prav pred kratkim sta Potechin in Tsang dokazala analogen rezultat za Cayleyeve grafe na abelskih grupah. Postavila sta tudi domnevo, da imajo vsi Cayleyevi grafi analogno lastnost. To domnevo ovržemo s konstrukcijo različnih protiprimerov, med katerimi je tudi neskončna družina Cayleyevih grafov neomejene stopnje, ki dopuščajo induciran podgraf maksimalne stopnje 1 na množici, ki vsebuje več kot polovico točk"}],"edm:type":"TEXT","dc:type":[{"@xml:lang":"sl","#text":"znanstveno časopisje"},{"@xml:lang":"en","#text":"journals"},{"@rdf:resource":"http://www.wikidata.org/entity/Q361785"}]},"ore:Aggregation":{"@rdf:about":"http://www.dlib.si/?URN=URN:NBN:SI:doc-10EH7ZFN","edm:aggregatedCHO":{"@rdf:resource":"URN:NBN:SI:doc-10EH7ZFN"},"edm:isShownBy":{"@rdf:resource":"http://www.dlib.si/stream/URN:NBN:SI:doc-10EH7ZFN/b442d8eb-373d-4b12-87af-d04c4ff4cc39/PDF"},"edm:rights":{"@rdf:resource":"http://creativecommons.org/licenses/by/4.0/"},"edm:provider":"Slovenian National E-content Aggregator","edm:intermediateProvider":{"@xml:lang":"en","#text":"National and University Library of Slovenia"},"edm:dataProvider":{"@xml:lang":"sl","#text":"Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije"},"edm:object":{"@rdf:resource":"http://www.dlib.si/streamdb/URN:NBN:SI:doc-10EH7ZFN/maxi/edm"},"edm:isShownAt":{"@rdf:resource":"http://www.dlib.si/details/URN:NBN:SI:doc-10EH7ZFN"}}}}