Geodesic
Tropical lower bound for extended formulations. II. Deficiency graphs of matrices
Izvestiya. Mathematics , Tome 83 (2019) no. 1, pp. 184-195

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{IM2_2019_83_1_a8,
     author = {Ya. Shitov},
     title = {Tropical lower bound for extended formulations. {II.} {Deficiency} graphs of matrices},
     journal = {Izvestiya. Mathematics },
     pages = {184--195},
     publisher = {mathdoc},
     volume = {83},
     number = {1},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IM2_2019_83_1_a8/}
}
TY  - JOUR
AU  - Ya. Shitov
TI  - Tropical lower bound for extended formulations. II. Deficiency graphs of matrices
JO  - Izvestiya. Mathematics 
PY  - 2019
SP  - 184
EP  - 195
VL  - 83
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IM2_2019_83_1_a8/
LA  - en
ID  - IM2_2019_83_1_a8
ER  - 
%0 Journal Article
%A Ya. Shitov
%T Tropical lower bound for extended formulations. II. Deficiency graphs of matrices
%J Izvestiya. Mathematics 
%D 2019
%P 184-195
%V 83
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IM2_2019_83_1_a8/
%G en
%F IM2_2019_83_1_a8
Ya. Shitov. Tropical lower bound for extended formulations. II. Deficiency graphs of matrices. Izvestiya. Mathematics , Tome 83 (2019) no. 1, pp. 184-195. http://geodesic.mathdoc.fr/item/IM2_2019_83_1_a8/