Layered Subgraphs of the Hypercube

descriptionPublicationkeyboard_double_arrow_right Article , Preprint 18 Oct 2024Embargo end date: 01 Apr 2024Publisher:The Electronic Journal of CombinatoricsJournal:The Electronic Journal of Combinatorics, volume 31 (eissn: 1077-8926,

Copyright policy )Funded by:NSERC | unidentified

Authors: Natalie C. Behague; Imre Leader; Natasha Morrison; Kada Williams;

doi: 10.37236/12980 , 10.48550/arxiv.2404.18014

arXiv: 2404.18014

Layered Subgraphs of the Hypercube

- Summary
- Subjects
- Metrics

Abstract

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.

Related Organizations

University of Victoria
Canada
University of Warwick
United Kingdom
University of Victoria
Canada
International Centre for Mathematical Sciences
United Kingdom
UNIVERSITY OF VICTORIA
Canada

View all View all

Keywords

positive Turán density, Extremal problems in graph theory, cubical graph, Extremal set theory, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Hypergraphs

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	1
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average