Layered subgraphs of the hypercube

Fuente: arXiv
Enregistré dans:
Détails bibliographiques
Auteurs principaux: Behague, Natalie, Leader, Imre, Morrison, Natasha, Williams, Kada
Format: Preprint
Publié: 2024
Sujets:
Accès en ligne:
Tags: Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
_version_ 1866913333363343360
author Behague, Natalie
Leader, Imre
Morrison, Natasha
Williams, Kada
author_facet Behague, Natalie
Leader, Imre
Morrison, Natasha
Williams, Kada
contents A subgraph of the $n$-dimensional hypercube is called 'layered' if it is a subgraph of a layer of some hypercube. In this paper we show that there exist subgraphs of the cube of arbitrarily large girth that are not layered. This answers a question of Axenovich, Martin and Winter. Perhaps surprisingly, these subgraphs may even be taken to be induced.
format Preprint
id arxiv_https___arxiv_org_abs_2404_18014
institution arXiv
publishDate 2024
record_format arxiv
spellingShingle Layered subgraphs of the hypercube
Behague, Natalie
Leader, Imre
Morrison, Natasha
Williams, Kada
Combinatorics
A subgraph of the $n$-dimensional hypercube is called 'layered' if it is a subgraph of a layer of some hypercube. In this paper we show that there exist subgraphs of the cube of arbitrarily large girth that are not layered. This answers a question of Axenovich, Martin and Winter. Perhaps surprisingly, these subgraphs may even be taken to be induced.
title Layered subgraphs of the hypercube
topic Combinatorics
url https://arxiv.org/abs/2404.18014