

A159484


Upper bound arising in Hadwiger's conjecture.


1



0, 0, 110, 1054, 7097, 41201, 220171, 1115862, 5451131, 25919515, 120721773, 553162595, 2501388936, 11188504443, 49589159037, 218081007181, 952654230982, 4137309942806, 17876235129762, 76889316253171, 329384246847644, 1405944884946771, 5981601330173431
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

The best known upper bound on the number of smaller copies needed to cover a given body in ndimensional 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 ndimensional 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): 307316.
Brass, Peter; Moser, William; Pach, Janos (2005), "3.3 LeviHadwiger Covering Problem and Illumination", Research Problems in Discrete Geometry, SpringerVerlag, pp. 136142 .


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: 133143 (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

Sequence in context: A234760 A234753 A205610 * A283219 A283137 A213087
Adjacent sequences: A159481 A159482 A159483 * A159485 A159486 A159487


KEYWORD

easy,nonn


AUTHOR

Jonathan Vos Post, Apr 14 2009


EXTENSIONS

a(7)a(22) from Nathaniel Johnston, Apr 26 2011


STATUS

approved



