Signed tropical convexity

Georg Loho; László A. Végh

doi:10.4230/LIPIcs.ITCS.2020.24

Signed tropical convexity

Georg Loho, László A. Végh

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

3 Citations (Scopus)

51 Downloads (Pure)

Abstract

We establish a new notion of tropical convexity for signed tropical numbers. We provide several equivalent descriptions involving balance relations and intersections of open halfspaces as well as the image of a union of polytopes over Puiseux series and hyperoperations. Along the way, we deduce a new Farkas’ lemma and Fourier-Motzkin elimination without the non-negativity restriction on the variables. This leads to a Minkowski-Weyl theorem for polytopes over the signed tropical numbers.

Original language	English
Title of host publication	11th Innovations in Theoretical Computer Science Conference, ITCS 2020
Editors	Thomas Vidick
Publisher	Dagstuhl
ISBN (Electronic)	9783959771344
DOIs	https://doi.org/10.4230/LIPIcs.ITCS.2020.24
Publication status	Published - Jan 2020
Externally published	Yes
Event	11th Innovations in Theoretical Computer Science Conference, ITCS 2020 - Seattle, United States Duration: 12 Jan 2020 → 14 Jan 2020 Conference number: 11

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	151
ISSN (Print)	1868-8969

Conference

Conference	11th Innovations in Theoretical Computer Science Conference, ITCS 2020
Abbreviated title	ITCS 2020
Country/Territory	United States
City	Seattle
Period	12/01/20 → 14/01/20

Keywords

Farkas’ lemma
Signed tropical numbers
Tropical convexity

Access to Document

10.4230/LIPIcs.ITCS.2020.24Licence: CC BY

LIPIcs-ITCS-2020-24Final published version, 681 KBLicence: CC BY

Cite this

@inproceedings{448d0ced1456493a8e3685d4e8041d10,

title = "Signed tropical convexity",

abstract = "We establish a new notion of tropical convexity for signed tropical numbers. We provide several equivalent descriptions involving balance relations and intersections of open halfspaces as well as the image of a union of polytopes over Puiseux series and hyperoperations. Along the way, we deduce a new Farkas{\textquoteright} lemma and Fourier-Motzkin elimination without the non-negativity restriction on the variables. This leads to a Minkowski-Weyl theorem for polytopes over the signed tropical numbers.",

keywords = "Farkas{\textquoteright} lemma, Signed tropical numbers, Tropical convexity",

author = "Georg Loho and V{\'e}gh, {L{\'a}szl{\'o} A.}",

year = "2020",

month = jan,

doi = "10.4230/LIPIcs.ITCS.2020.24",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Dagstuhl",

editor = "Thomas Vidick",

booktitle = "11th Innovations in Theoretical Computer Science Conference, ITCS 2020",

address = "Germany",

note = "11th Innovations in Theoretical Computer Science Conference, ITCS 2020, ITCS 2020 ; Conference date: 12-01-2020 Through 14-01-2020",

}

Loho, G & Végh, LA 2020, Signed tropical convexity. in T Vidick (ed.), 11th Innovations in Theoretical Computer Science Conference, ITCS 2020., 24, Leibniz International Proceedings in Informatics, LIPIcs, vol. 151, Dagstuhl, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, Seattle, Washington, United States, 12/01/20. https://doi.org/10.4230/LIPIcs.ITCS.2020.24

TY - GEN

T1 - Signed tropical convexity

AU - Loho, Georg

AU - Végh, László A.

N1 - Conference code: 11

PY - 2020/1

Y1 - 2020/1

N2 - We establish a new notion of tropical convexity for signed tropical numbers. We provide several equivalent descriptions involving balance relations and intersections of open halfspaces as well as the image of a union of polytopes over Puiseux series and hyperoperations. Along the way, we deduce a new Farkas’ lemma and Fourier-Motzkin elimination without the non-negativity restriction on the variables. This leads to a Minkowski-Weyl theorem for polytopes over the signed tropical numbers.

AB - We establish a new notion of tropical convexity for signed tropical numbers. We provide several equivalent descriptions involving balance relations and intersections of open halfspaces as well as the image of a union of polytopes over Puiseux series and hyperoperations. Along the way, we deduce a new Farkas’ lemma and Fourier-Motzkin elimination without the non-negativity restriction on the variables. This leads to a Minkowski-Weyl theorem for polytopes over the signed tropical numbers.

KW - Farkas’ lemma

KW - Signed tropical numbers

KW - Tropical convexity

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

U2 - 10.4230/LIPIcs.ITCS.2020.24

DO - 10.4230/LIPIcs.ITCS.2020.24

M3 - Conference contribution

AN - SCOPUS:85078018402

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 11th Innovations in Theoretical Computer Science Conference, ITCS 2020

A2 - Vidick, Thomas

PB - Dagstuhl

T2 - 11th Innovations in Theoretical Computer Science Conference, ITCS 2020

Y2 - 12 January 2020 through 14 January 2020

ER -

Signed tropical convexity

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this