TY - JOUR
ID - 25746
TI - On the VC-dimension, covering and separating properties of the cycle and spanning tree hypergraphs of graphs
JO - Transactions on Combinatorics
JA - TOC
LA - en
SN - 2251-8657
AU - Mofidi, Alireza
AD - Department of Mathematics and Computer Science, Amirkabir University of Technology (Tehran Poly-
technic), Hafez Avenue, 15194, Tehran, Iran
Y1 - 2022
PY - 2022
VL - 11
IS - 1
SP - 29
EP - 43
KW - VC-dimension
KW - Cycle hypergraphs of graphs
KW - spanning tree hypergraphs of graphs
KW - separating number
KW - test cover
DO - 10.22108/toc.2021.127880.1832
N2 - 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 VC-dimension and some important separating and covering features of hypergraph theory and amongst the results, for example show that the VC-dimension of the cycle hypergraph is less than or equal to the VC-dimension of the spanning tree hypergraph and their gap can be arbitrary large. Note that VC-dimension 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.
UR - https://toc.ui.ac.ir/article_25746.html
L1 - https://toc.ui.ac.ir/article_25746_890e066e8b9dd269c189910e7e780475.pdf
ER -