On the VC-dimension‎, ‎covering and separating properties of the cycle and spanning tree hypergraphs of graphs

Document Type : Research Paper

Author

Department of Mathematics and Computer Science, Amirkabir University of Technology (Tehran Poly- technic), Hafez Avenue, 15194, Tehran, Iran

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 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‎.

Keywords

Main Subjects

References

[1] R. Anstee, L. Ronyai and A. Sali, Shattering news, Graphs Combin., 18 (2002) 59–73.
[2] L. Beaudou, P. Dankelmann, F. Foucaud, M. A. Henning, A. Mary and A. Parreau, Bounding the order of a graph
using its diameter and metric dimension: a study through tree decomposition and VC dimension, SIAM J. Discrete
Math., 32 (2018) 902–918.
[3] C. Berge, Graphs and hypergraphs, Translated from the French by Edward Minieka, North-Holland Mathematical
Library, 6, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York,
1973.
[4] B. Bollobas, Combinatorics: et systems, hypergraphs, families of vectors and combinatorial probability, Cambridge
University Press, Cambridge, 1986.
[5] N. Bousquet, S. Thomasse, VC-dimension and Erdos-Posa property, Discrete Math., 338 (2015) 2302–2317.
[6] A. Bretto, Hypergraph theory, an introduction, Mathematical Engineering, Springer, Cham, 2013.
[7] V. D. Chepoi, B. Estellon and Y. Vaxes, Covering planar graphs with a fixed number of balls, Discrete Comput.
Geom., 37 (2007) 237–244.
[8] K. Ch. Das, A sharp upper bound for the number of spanning trees of a graph, Graphs Combin., 23 (2007) 625–632.
[9] R. Diestel, Graph Theory, Third edition. Graduate Texts in Mathematics, 173, Springer-Verlag, Berlin, 2005.
[10] L. Feng, G. Yu, Z. Jiang and L. Ren, Sharp upper bounds for the number of spanning trees of a graph, Appl. Anal.
Discrete Math., 2 (2008) 255–259.
[11] G. R. Grimmett, An upper bound for the number of spanning trees of a graph, Discrete Math., 16 (1976) 323–324.
[12] S. Jukna, Extremal Combinatorics. With Applications in Computer Science, 2nd ed., Springer, Heidelberg, 2011.
[13] E. Kranakis, D. Krizanc, B. Ruf, J. Urrutia and G. Woeginger, The VC-dimension of set systems defined by graphs,
Discrete Appl. Math., 77 (1997) 237–257.
[14] E. Kranakis, D. Krizanc and G. Woeginger, VC-dimensions for graphs, in: M. Nagl, editor, Graph-theoretic concepts
in computer science, LNCS 1017, (1995) 1–13.
[15] J. Li, W. C. Shiu and A. Chang, The number of spanning trees of a graph, Appl. Math. Lett., 23 (2010) 286–290.
[16] J. Matousek, Lectures on discrete geometry, Graduate Texts in Mathematics, 212, Springer-Verlag, New York, 2002.
[17] A. Mofidi, On some dynamical aspects of NIP theories, Arch. Math. Logic, 57 (2018) 37–71.
[18] A. Mofidi, On partial cubes, well-graded families and their duals with some applications in graphs, Discrete Appl.
Math., 283 (2020) 207–230.
Transactions on Combinatorics
Volume 11, Issue 1
March 2022
Pages 29-43

Files

History

  • Receive Date: 19 March 2021
  • Revise Date: 07 June 2021
  • Accept Date: 08 June 2021
  • Published Online: 01 March 2022

Share

How to cite

Statistics