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

详细信息    查看全文

• 作者：Jonathan L. Gross^a ; ^{gross@cs.columbia.edu" class="auth_mail" title="E-mail the corresponding author} ; Toufik Mansour^b ; ^{tmansour@univ.haifa.ac.il" class="auth_mail" title="E-mail the corresponding author} ; Thomas W. Tucker^c ; ^{ttucker@colgate.edu" class="auth_mail" title="E-mail the corresponding author} ; David G.L. Wang^d ; ^{glw@bit.edu.cn" class="auth_mail" title="E-mail the corresponding author}
• 刊名：European Journal of Combinatorics
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：52
• 期：part_PA
• 页码：207-222
• 全文大小：469 K

文摘

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.