The number of edges of the edge polytope of a finite simple graph - Hibi, Takayuki (Ars mathematica contemporanea, 2016)
Naj bo ?$d \ge 3$? celo število. Znano je, da je število povezav povezavnega politopa polnega grafa z ?$d$? vozlišči enako ?$d(d-1)(d-2)/2$?. V tem članku študiramo največje možno število ?$μ_{d}$? povezav, ki jih lahko imajo povezavni politopi, dobljeni iz končnih enostavnih grafov z ?$d$? vozlišči. Pokažemo, da je ?$μ_{d} = d(d-1)(d-2)/2$? če in samo če ?$3 ≤ d ≤ 14$?. Poleg tega študiramo asimptotično vedenje števila ?$μ_{d}$?. Tran-Ziegler sta dobila spodnjo mejo za ?$μ_{d}$? tako, da sta konstruirala slučajni graf. Uspelo nam je izboljšati to mejo s konstruiranjem ne-slučajnega grafa in slučajnega grafa, katerega komplement je dvodelen.
Keywords: edge polytope; finite simple graph; končni enostavni graf; povezavni politop