Transversal numbers of translates of a convex body

Autor(es)

Kim‚ S.J. ; Nakprasit‚ K. ; Pelsmajer‚ M.J. ; Skokan‚ J.

• Tipo de documento: Artigo Científico
• Fonte: DISCRETE MATHEMATICS; v. 306, n. 18, p. 2166-2173, 2006.

Resumo

Let F be a family of translates of a fixed convex set M in R-n. Let tau(F) and nu(F) denote the transversal number and the independence number of F, respectively. We show that nu(F) <= tau(F) <= 8 nu(F) - 5 for n = 2 and tau(F) <= 2(n-1)n(n)nu(F) for n >= 3. Furthermore, if M is centrally symmetric convex body in the plane, then nu(F) <= tau(F) <= 6 nu(F) - 3. (c) 2006 Elsevier B.V. All rights reserved. (AU)

• Processo FAPESP: 03/09925-5 - Fundamentos da ciência da computação: algoritmos combinatórios e estruturas discretas
• Beneficiário: Yoshiharu Kohayakawa
• Modalidade de apoio: Auxílio à Pesquisa - Programa PRONEX - Temático
• Processo FAPESP: 04/15397-4 - Aplicacoes de quase-aleatoriedade em combinatoria.
• Beneficiário: Jozef Skokan
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado