For a graph G, and a nonnegative integer g, let ag(G) be the number of $2$-cell embeddings of G in an orientable surface of genus g (counted up to the combinatorial homeomorphism equivalence). In 1989, Gross, Robbins, and Tucker [Genus distributions for bouquets of circles, J. Combin. Theory Ser. B 47 (1989), 292-306] proposed a conjecture that the sequence a₀(G),a₁(G),a₂(G), is log-concave for every graph G. This conjecture is reminiscent to the Heron-Rota-Welsh Log Concavity Conjecture that was recently resolved in the affirmative by June Huh et al., except that it is closer to the notion of Δ-matroids than to the usual matroids. In this short paper, we disprove the Log Concavity Conjecture of Gross, Robbins, and Tucker by providing examples that show strong deviation from log-concavity at multiple terms of their genus sequences.
No takes yet. Share an insight, caveat, or question.
Bojan Mohar (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: