RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Forthcoming papers
Archive
Impact factor
Subscription
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Izv. RAN. Ser. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Izv. RAN. Ser. Mat., 2019, Volume 83, Issue 1, Pages 203–216 (Mi izv8698)  

Tropical lower bound for extended formulations. II. Deficiency graphs of matrices

Ya. Shitov

National Research University "Higher School of Economics" (HSE), Moscow

Abstract: Deficiency graphs arise in the problem of decomposing a tropical vector into a sum of points of a given tropical variety. We give an application of this concept to the theory of extended formulations of convex polytopes, and we show that the chromatic number of the deficiency graph of a special tropical matrix is a lower bound for the extension complexity of the corresponding convex polytope. We compare our new lower bound for extended formulations with existing estimates and make several conjectures on the relations between deficiency graphs, extended formulations, and rank functions of tropical matrices.

Keywords: convex polytope, extended formulation, tropical mathematics.

Funding Agency Grant Number
Russian Science Foundation 17-71-10229
This work was supported by the Russian Science Foundation under grant 17-71-10229.


DOI: https://doi.org/10.4213/im8698

Full text: PDF file (648 kB)
First page: PDF file
References: PDF file   HTML file

English version:
Izvestiya: Mathematics, 2019, 83:1, 184–195

Bibliographic databases:

UDC: 512
MSC: 15A23, 15B48, 52B05
Received: 30.06.2017
Revised: 19.02.2018

Citation: Ya. Shitov, “Tropical lower bound for extended formulations. II. Deficiency graphs of matrices”, Izv. RAN. Ser. Mat., 83:1 (2019), 203–216; Izv. Math., 83:1 (2019), 184–195

Citation in format AMSBIB
\Bibitem{Shi19}
\by Ya.~Shitov
\paper Tropical lower bound for extended formulations. II. Deficiency graphs of matrices
\jour Izv. RAN. Ser. Mat.
\yr 2019
\vol 83
\issue 1
\pages 203--216
\mathnet{http://mi.mathnet.ru/izv8698}
\crossref{https://doi.org/10.4213/im8698}
\adsnasa{http://adsabs.harvard.edu/cgi-bin/bib_query?2019IzMat..83..184S}
\elib{http://elibrary.ru/item.asp?id=37045048}
\transl
\jour Izv. Math.
\yr 2019
\vol 83
\issue 1
\pages 184--195
\crossref{https://doi.org/10.1070/IM8698}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000459866800009}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85064110088}


Linking options:
  • http://mi.mathnet.ru/eng/izv8698
  • https://doi.org/10.4213/im8698
  • http://mi.mathnet.ru/eng/izv/v83/i1/p203

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya Izvestiya: Mathematics
    Number of views:
    This page:122
    References:18
    First page:17

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019