Combinatorial conjectures that imply local log-concavity of graph genus polynomials. (February 2016)

• Record Type: Journal Article
• Authors: Gross, Jonathan L.; Mansour, Toufik; Tucker, Thomas W.; Wang, David G.L.
• Is Part Of: European journal of combinatorics. Volume 52: Part A (2016:Feb.)
• Page Start: 207
• Page End: 222
• Publication Date: 2016-02
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2015.10.002
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: 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.