Lower bounds on the maximum number of non-crossing acyclic graphs

DOI10.1016/J.EJC.2015.02.008zbMATH Open1314.05099DBLPjournals/ejc/HuemerM15arXiv1310.5882OpenAlexW1979048780WikidataQ61732467 ScholiaQ61732467MaRDI QIDQ2346577FDOQ2346577

Authors: Clemens Huemer, Anna de Mier 

Publication date: 2 June 2015

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: This paper is a contribution to the problem of counting geometric graphs on point sets. More concretely, we look at the maximum numbers of non-crossing spanning trees and forests. We show that the so-called double chain point configuration of N points has Omega(12.52^N) non-crossing spanning trees and Omega(13.61^N) non-crossing forests. This improves the previous lower bounds on the maximum number of non-crossing spanning trees and of non-crossing forests among all sets of N points in general position given by Dumitrescu, Schulz, Sheffer and T'oth. Our analysis relies on the tools of analytic combinatorics, which enable us to count certain families of forests on points in convex position, and to estimate their average number of components. A new upper bound of O(22.12^N) for the number of non-crossing spanning trees of the double chain is also obtained.

Full work available at URL: https://arxiv.org/abs/1310.5882

Recommendations

• An improved lower bound on the maximum number of non-crossing spanning trees
• Bounds on the maximum multiplicity of some common geometric graphs
• Bounds on the maximum multiplicity of some common geometric graphs
• Lower bounds on the number of crossing-free subgraphs of \(K_N\)
• On the number of plane geometric graphs

zbMATH Keywords

counting geometric graphs on point sets

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Cites Work

• Analytic combinatorics
• A course in combinatorics.
• Analytic combinatorics of non-crossing configurations
• Lower bounds on the number of crossing-free subgraphs of \(K_N\)
• On the number of pseudo-triangulations of certain point sets
• Bounds on the maximum multiplicity of some common geometric graphs
• Crossing-Free Subgraphs
• Title not available (Why is that?)

Cited In (7)

• A lower bound on the acyclic matching number of subcubic graphs
• Lower bound for the size of maximal nontraceable graphs
• A new lower bound on the maximum number of plane graphs using production matrices
• Lower bounds on the number of crossing-free subgraphs of \(K_N\)
• Bounds on the maximum multiplicity of some common geometric graphs
• Bounds on the maximum multiplicity of some common geometric graphs
• Extremal statistics on non-crossing configurations

This page was built for publication: Lower bounds on the maximum number of non-crossing acyclic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2346577)