On a covering problem in the hypercube
From MaRDI portal
Publication:489361
DOI10.1007/S00373-013-1379-8zbMATH Open1306.05071arXiv1110.0224OpenAlexW2098910136MaRDI QIDQ489361FDOQ489361
Authors: Lale Özkahya, Brendon Stanton 
Publication date: 20 January 2015
Published in: Graphs and Combinatorics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1110.0224
Recommendations
Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)
Cites Work
- Daisies and other Turán problems
- On a packing and covering problem
- Title not available (Why is that?)
- Some Turán type results on the hypercube
- Hexagon-free subgraphs of hypercubes
- Turán’s Theorem in the Hypercube
- On crown-free families of subsets
- Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube
- An extremal theorem in the hypercube
- Bounding the size of square-free subgraphs of the hypercube
- Subcube fault-tolerance in hypercubes
- Some further vertex Turán numbers for cube graphs
- Subgraphs of a hypercube containing no small even cycles
- On the maximum number of edges in a c4‐free subgraph of qn
- Covering complete \(r\)-graphs with spanning complete \(r\)-partite \(r\)-graphs
- On even-cycle-free subgraphs of the hypercube
- Vertex Turán problems in the hypercube
Cited In (14)
- On a covering problem in the hypercube
- On the area of hypercube layouts.
- Reaching approximate agreement on hypercube
- On the Hadwiger covering problem in low dimensions
- Covering the cube by affine hyperplanes
- 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
- Title not available (Why is that?)
- 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)
