login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 18 14:29 EDT 2021. Contains 345114 sequences. (Running on oeis4.)