“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
Paper IPM / M / 16936  


Abstract:  
In this paper, we delve into studying some relations between the structure of the cycles and spanning trees of a graph through the lens of its cycle and spanning tree hypergraphs which are hypergraphs with the edge set of the graph as their vertices and the edge sets of the cycles and spanning trees as their hyperedges respectively. In particular, we investigate relations between these hypergraphs from the perspective of the VCdimension and some important separating and covering features of hypergraph theory and amongst the results, for example show that the VCdimension of the cycle hypergraph is less than or equal to the VCdimension of the spanning tree hypergraph and their gap can be arbitrary large. Note that VCdimension is an important measure of complexity and a fundamental notion in numerous fields such as extremal combinatorics, graph theory, statistics and the theory of machine learning. Also we compare the separating and covering features of the mentioned hypergraphs and for instance show that the separating number of the cycle hypergraph is less than or equal to that of the spanning tree hypergraph. These hypergraphs help us to make several connections between cycles and spanning trees of graphs and compare their complexities.
Download TeX format 

back to top 