On a covering problem in the hypercube

DOI10.1007/S00373-013-1379-8MaRDI QIDQ489361zbMATH OpenOpenAlexFDO

Authors Lale Özkahya, Brendon Stanton

Publication date 20 January 2015

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.0224

zbMATH Keywords

hypercubepolychromatic coloringcover number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Abstract: In this paper, we address a particular variation of the Tur'an problem for the hypercube. Alon, Krech and Szab'o (2007) asked "In an n-dimensional hypercube, Qn, and for l < d < n, what is the size of a smallest set, S, of Q_l's so that every Q_d contains at least one member of S?" Likewise, they asked a similar Ramsey type question: "What is the largest number of colors that we can use to color the copies of Q_l in Q_n such that each Q_d contains a Q_l of each color?" We give upper and lower bounds for each of these questions and provide constructions of the set S above for some specific cases.

Recommendations

• On a covering problem in the hypercube
• Some Turán type results on the hypercube
• Turán’s Theorem in the Hypercube
• Vertex Turán problems in the hypercube
• Vertex Ramsey problems in the hypercube

Cites work

• scientific article; zbMATH DE number 3198027 (Why is no real title available?)
• An extremal theorem in the hypercube
• Bounding the size of square-free subgraphs of the hypercube
• Covering complete \(r\)-graphs with spanning complete \(r\)-partite \(r\)-graphs
• Daisies and other Turán problems
• Hexagon-free subgraphs of hypercubes
• On a packing and covering problem
• On crown-free families of subsets
• On even-cycle-free subgraphs of the hypercube
• On the maximum number of edges in a c₄‐free subgraph of q_n
• Some Turán type results on the hypercube
• Some further vertex Turán numbers for cube graphs
• Subcube fault-tolerance in hypercubes
• Subgraphs of a hypercube containing no small even cycles
• Turán’s Theorem in the Hypercube
• Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube
• Vertex Turán problems in the hypercube

Cited in

(14)

• On the area of hypercube layouts.
• On a covering problem in the hypercube
• Reaching approximate agreement on hypercube
• Covering the cube by affine hyperplanes
• On the Hadwiger covering problem in low dimensions
• On almost \(k\)-covers of hypercubes
• Constructing 2-arc-transitive covers of hypercubes
• On bounds for a board covering problem
• Pairing strategies for the maker-breaker game on the hypercube with subcubes as winning sets
• scientific article; zbMATH DE number 4112541 (Why is no real title available?)
• On hypercube packings, blocking sets and a covering problem
• Linear polychromatic colorings of hypercube faces
• Linear \(d\)-polychromatic \(Q_{d-1}\)-colorings of the hypercube
• Polychromatic colorings on the integers

This page was built for publication: On a covering problem in the hypercube

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