Better Bounds for Planar Sets Avoiding Unit Distances

Autor(es)

Keleti, Tamas ^[1] ; Matolcsi, Mate ^[2] ; de Oliveira Filho, Fernando Mario ^[3] ; Ruzsa, Imre Z. ^[2]

Afiliação do(s) autor(es)

^[1] Eotvos Lorand Univ, Inst Math, Pazmany P Setany 1-C, H-1117 Budapest - Hungary

^[2] Hungarian Acad Sci, Alfred Renyi Inst Math, POB 127, H-1364 Budapest - Hungary

^[3] Univ Sao Paulo, Inst Matemat & Estat, Rua Matao 1010, BR-05508090 Sao Paulo, SP - Brazil

• Tipo de documento: Artigo Científico
• Fonte: DISCRETE & COMPUTATIONAL GEOMETRY; v. 55, n. 3, p. 642-661, APR 2016.
• Citações Web of Science: 0

Resumo

A 1-avoiding set is a subset of that does not contain pairs of points at distance 1. Let denote the maximum fraction of that can be covered by a measurable 1-avoiding set. We prove two results. First, we show that any 1-avoiding set in that displays block structure (i.e., is made up of blocks such that the distance between any two points from the same block is less than 1 and points from distinct blocks lie farther than 1 unit of distance apart from each other) has density strictly less than . For the special case of sets with block structure this proves a conjecture of ErdAs asserting that . Second, we use linear programming and harmonic analysis to show that m(1) (R-2) <= 0.258795. (AU)

• Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
• Beneficiário: Carlos Eduardo Ferreira
• Modalidade de apoio: Auxílio à Pesquisa - Temático