OFFSET
0,3
COMMENTS
The best known upper bound on the number of smaller copies needed to cover a given body in n-dimensional Euclidean space is a(n) according to Brass. In graph theory, the Hadwiger conjecture (or Hadwiger's conjecture) states that, if all proper colorings of an undirected graph G use k or more colors, then one can find k disjoint connected subgraphs of G such that each subgraph is connected by an edge to each other subgraph.
Contracting the edges within each of these subgraphs so that each subgraph collapses to a single supervertex produces a complete graph K_k on k vertices as a minor of G. In combinatorial geometry, the Hadwiger conjecture states that any convex body in n-dimensional Euclidean space may be covered by at most 2n homothetic (scaled and translated but not rotated) copies of the same body, each of which has smaller size than the original. There is also an equivalent formulation in terms of the number of floodlights needed to illuminate the body.
REFERENCES
Kostochka, A. V. (1984), "Lower bound of the Hadwiger number of graphs by their average degree", Combinatorica 4 (4): 307-316.
Brass, Peter; Moser, William; Pach, Janos (2005), "3.3 Levi-Hadwiger Covering Problem and Illumination", Research Problems in Discrete Geometry, Springer-Verlag, pp. 136-142 .
LINKS
Nathaniel Johnston, Table of n, a(n) for n = 0..250
Hugo Hadwiger, Über eine Klassifikation der Streckenkomplexe, Vierteljschr. Naturforsch. ges. Zürich 88: 133-143 (1943).
Wikipedia, Hadwiger conjecture (combinatorial geometry).
FORMULA
a(n) = floor((4^n)*(5*n*log(n))).
EXAMPLE
a(1) = (4^1) * (5 * 1 * log(1)) = 0.
a(2) = floor ((4^2) * (5 * 2 * log(2))) = floor(110.903549) = 110.
a(3) = floor(1054.6678) = 1054.
MATHEMATICA
Table[If[n==0, 0, Floor[(4^n)*(5*n*Log[n])]], {n, 0, 30}] (* G. C. Greubel, Jun 12 2018 *)
PROG
(PARI) for(n=0, 30, print1(if(n==0, 0, floor((4^n)*(5*n*log(n)))) , ", ")) \\ G. C. Greubel, Jun 12 2018
(MAGMA) [0] cat [ Floor((4^n)*(5*n*Log(n))) : n in [1..30]]; // G. C. Greubel, Jun 12 2018
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Jonathan Vos Post, Apr 14 2009
EXTENSIONS
a(7)-a(22) from Nathaniel Johnston, Apr 26 2011
STATUS
approved