Combinatorial conjectures that imply local log-concavity of graph genus polynomials

Jonathan L. Gross, Toufik Mansour, Thomas W. Tucker, David G.L. Wang

科研成果: 期刊稿件文章同行评审

4 引用 (Scopus)

摘要

The 25-year old LCGD Conjecture is that the genus distribution of every graph is log-concave. We present herein a new topological conjecture, called the Local Log-Concavity Conjecture. We also present a purely combinatorial conjecture, which we prove to be equivalent to the Local Log-Concavity Conjecture. We use the equivalence to prove the Local Log-Concavity Conjecture for graphs of maximum degree four. We then show how a formula of David Jackson could be used to prove log-concavity for the genus distributions of various partial rotation systems, with straight-forward application to proving the local log-concavity of additional classes of graphs. We close with an additional conjecture, whose proof, along with proof of the Local Log-Concavity Conjecture, would affirm the LCGD Conjecture.

源语言英语
页(从-至)207-222
页数16
期刊European Journal of Combinatorics
52
DOI
出版状态已出版 - 1 2月 2016

指纹

探究 'Combinatorial conjectures that imply local log-concavity of graph genus polynomials' 的科研主题。它们共同构成独一无二的指纹。

引用此