Bulky subgraphs of the hypercube

DOI10.1006/EUJC.1999.0362MaRDI QIDQ1568786zbMATH OpenOpenAlexFDO

Authors Andreĭ V. Kotlov

Publication date 28 August 2000

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/eujc.1999.0362

zbMATH Keywords

bulk subgraphfacethypercubesimple-majority

Mathematics Subject Classification ID

Hypergraphs (05C65) Structural characterization of families of graphs (05C75)

Review text

Suppose \(Q\) is a \(d\)-dimensional hypercube on \(2^d\) vertices. The intersection of \(Q\) with one of the hyperplanes \(x_i= 0\) or \(x_i= 1\), \(i\in [1,2,\dots, d]\) is a \((d-1)\)-dimensional hypercube called a facet of \(Q\). A graph is bulky if it meets every facet of \(Q\) and is connected. An induced subgraph is said to be simple-majority if \(|G|> 2^{d-1}\). The author proves that every simple-majority \(G\) has a bulk subgraph.

Recommendations

• On induced subgraphs of the cube
• scientific article; zbMATH DE number 125454
• An extremal theorem in the hypercube
• Induced subgraphs of hypercubes

Cites work

• A Separator Theorem for Nonplanar Graphs
• scientific article; zbMATH DE number 36687 (Why is no real title available?)

Cited in

(3)

• Subgraphs of hypercubes and subdiagrams of Boolean lattices
• Decomposing hypercubes into regular connected subgraphs
• Induced subgraphs of hypercubes

This page was built for publication: Bulky subgraphs of the hypercube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1568786)