Complete positivity and distance-avoiding sets

Evan DeCorte; Fernando Mário de Oliveira Filho; Frank Vallentin

doi:10.1007/s10107-020-01562-6

Complete positivity and distance-avoiding sets

Evan DeCorte, Fernando Mário de Oliveira Filho^*, Frank Vallentin

^*Corresponding author for this work

Discrete Mathematics and Optimization

Research output: Contribution to journal › Article › Scientific › peer-review

4 Citations (Scopus)

73 Downloads (Pure)

Abstract

We introduce the cone of completely positive functions, a subset of the cone of positive-type functions, and use it to fully characterize maximum-density distance-avoiding sets as the optimal solutions of a convex optimization problem. As a consequence of this characterization, it is possible to reprove and improve many results concerning distance-avoiding sets on the sphere and in Euclidean space.

Original language	English
Pages (from-to)	487-558
Number of pages	72
Journal	Mathematical Programming
Volume	191
Issue number	2
DOIs	https://doi.org/10.1007/s10107-020-01562-6
Publication status	Published - 2020

Keywords

Chromatic number of Euclidean space
Copositive programming
Hadwiger-Nelson problem
Harmonic analysis
Semidefinite programming

Access to Document

10.1007/s10107-020-01562-6

DeCorte2020_Article_CompletePositivityAndDistance-Final published version, 632 KBLicence: CC BY

Cite this

@article{145db99090bc45198f5c15f31050f99f,

title = "Complete positivity and distance-avoiding sets",

abstract = "We introduce the cone of completely positive functions, a subset of the cone of positive-type functions, and use it to fully characterize maximum-density distance-avoiding sets as the optimal solutions of a convex optimization problem. As a consequence of this characterization, it is possible to reprove and improve many results concerning distance-avoiding sets on the sphere and in Euclidean space.",

keywords = "Chromatic number of Euclidean space, Copositive programming, Hadwiger-Nelson problem, Harmonic analysis, Semidefinite programming",

author = "Evan DeCorte and Filho, {Fernando M{\'a}rio de Oliveira} and Frank Vallentin",

year = "2020",

doi = "10.1007/s10107-020-01562-6",

language = "English",

volume = "191",

pages = "487--558",

journal = "Mathematical Programming",

issn = "0025-5610",

publisher = "Springer",

number = "2",

}

TY - JOUR

T1 - Complete positivity and distance-avoiding sets

AU - DeCorte, Evan

AU - Filho, Fernando Mário de Oliveira

AU - Vallentin, Frank

PY - 2020

Y1 - 2020

N2 - We introduce the cone of completely positive functions, a subset of the cone of positive-type functions, and use it to fully characterize maximum-density distance-avoiding sets as the optimal solutions of a convex optimization problem. As a consequence of this characterization, it is possible to reprove and improve many results concerning distance-avoiding sets on the sphere and in Euclidean space.

AB - We introduce the cone of completely positive functions, a subset of the cone of positive-type functions, and use it to fully characterize maximum-density distance-avoiding sets as the optimal solutions of a convex optimization problem. As a consequence of this characterization, it is possible to reprove and improve many results concerning distance-avoiding sets on the sphere and in Euclidean space.

KW - Chromatic number of Euclidean space

KW - Copositive programming

KW - Hadwiger-Nelson problem

KW - Harmonic analysis

KW - Semidefinite programming

UR - http://www.scopus.com/inward/record.url?scp=85091064136&partnerID=8YFLogxK

U2 - 10.1007/s10107-020-01562-6

DO - 10.1007/s10107-020-01562-6

M3 - Article

AN - SCOPUS:85091064136

SN - 0025-5610

VL - 191

SP - 487

EP - 558

JO - Mathematical Programming

JF - Mathematical Programming

IS - 2

ER -

Complete positivity and distance-avoiding sets

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this