Skip to main content
Springer Nature Link
Log in

Bounds on Functionality and Symmetric Difference – Two Intriguing Graph Parameters

  • Conference paper
  • First Online:
Graph-Theoretic Concepts in Computer Science (WG 2023)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14093))

Included in the following conference series:

  • 501 Accesses

Abstract

[Alecu et al.: Graph functionality, JCTB2021] define functionality, a graph parameter that generalizes graph degeneracy. They research the relation of functionality to many other graph parameters (tree-width, clique-width, VC-dimension, etc.). Extending their research, we prove a logarithmic lower bound for functionality of random graph G(n, p) for large range of p. Previously known graphs have functionality logarithmic in number of vertices. We show that for every graph G on n vertices we have \(\textrm{fun}(G) \le O(\sqrt{ n \log n})\) and we give a nearly matching \(\varOmega (\sqrt{n})\)-lower bound provided by projective planes.

Further, we study a related graph parameter symmetric difference, the minimum of \(|N(u) \mathrm {\Delta }N(v)|\) over all pairs of vertices of the “worst possible” induced subgraph. It was observed by Alecu et al. that \(\textrm{fun}(G) \le \textrm{sd}(G)+1\) for every graph G. We compare \(\textrm{fun}\) and \(\textrm{sd}\) for the class \(\textrm{INT}\) of interval graphs and \(\textrm{CA}\) of circular-arc graphs. We let \(\textrm{INT}_n\) denote the n-vertex interval graphs, similarly for \(\textrm{CA}_n\).

Alecu et al. ask, whether \(\textrm{fun}(\textrm{INT})\) is bounded. Dallard et al. answer this positively in a recent preprint. On the other hand, we show that \(\varOmega (\root 4 \of {n}) \le \textrm{sd}(\textrm{INT}_n) \le O(\root 3 \of {n})\). For the related class \(\textrm{CA}\) we show that \(\textrm{sd}(\textrm{CA}_n) = \varTheta (\sqrt{n})\).

We propose a follow-up question: is \(\textrm{fun}(\textrm{CA})\) bounded?

P. Dvořák—Supported by Czech Science Foundation GAČR grant #22-14872O.

L. Folwarczný—Supported by Czech Science Foundation GAČR grant 19-27871X.

M. Opler—Supported by Czech Science Foundation GAČR grant 22-19557S.

P. Pudlák—Supported by Czech Science Foundation GAČR grant 19-27871X.

R. Šámal—Partially supported by grant 22-17398S of the Czech Science Foundation. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 810115).

T. A. Vu—Supported by Czech Science Foundation GAČR grant 22-22997S.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Intersection graphs of arcs of a cycle, see Sect. 1 for the proper definition.

  2. 2.

    Intersection graphs of intervals of the real line, see Sect. 1 for the proper definition.

References

  1. Alecu, B., Atminas, A., Lozin, V.V.: Graph functionality. J. Comb. Theory Ser. B 147, 139–158 (2021). https://doi.org/10.1016/j.jctb.2020.11.002

  2. Alon, N., Haussler, D., Welzl, E.: Partitioning and geometric embedding of range spaces of finite Vapnik-Chervonenkis dimension. In: Soule, D. (ed.) Proceedings of the Third Annual Symposium on Computational Geometry, Waterloo, Ontario, Canada, 8–10 June 1987, pp. 331–340. ACM (1987)

    Google Scholar 

  3. Atminas, A., Collins, A., Lozin, V., Zamaraev, V.: Implicit representations and factorial properties of graphs. Discret. Math. 338(2), 164–179 (2015). https://doi.org/10.1016/j.disc.2014.09.008

    Article  MathSciNet  MATH  Google Scholar 

  4. Balogh, J., Bollobás, B., Weinreich, D.: The speed of hereditary properties of graphs. J. Comb. Theory Ser. B 79(2), 131–156 (2000). https://doi.org/10.1006/jctb.2000.1952, https://www.sciencedirect.com/science/article/pii/S009589560091952X

  5. Dallard, C., Lozin, V., Milanič, M., Štorgel, K., Zamaraev, V.: Functionality of box intersection graphs (2023). https://doi.org/10.48550/ARXIV.2301.09493

  6. Hatami, H., Hatami, P.: The implicit graph conjecture is false. In: 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31–3 November 2022, pp. 1134–1137. IEEE (2022)

    Google Scholar 

  7. Kranakis, E., Krizanc, D., Ruf, B., Urrutia, J., Woeginger, G.: The VC-dimension of set systems defined by graphs. Discret. Appl. Math. 77(3), 237–257 (1997). https://doi.org/10.1016/S0166-218X(96)00137-0

    Article  MathSciNet  MATH  Google Scholar 

  8. Matoušek, J., Nešetřil, J.: Invitation to Discrete Mathematics, 2 ed. Oxford University Press, Oxford (2009)

    Google Scholar 

Download references

Acknowledgements

The research presented in this paper has been started during the KAMAK workshop in 2021. We are grateful to the organizers of this wonderful event.

Author information

Authors and Affiliations

  1. Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic

    Pavel Dvořák, Lukáš Folwarczný, Robert Šámal & Tung Anh Vu

  2. Tata Institute of Fundamental Research, Mumbai, India

    Pavel Dvořák

  3. Institute of Mathematics, Czech Academy of Sciences, Prague, Czech Republic

    Lukáš Folwarczný & Pavel Pudlák

  4. Faculty of Information Technology, Czech Technical University, Prague, Czech Republic

    Michal Opler

Authors
  1. Pavel Dvořák
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lukáš Folwarczný
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Michal Opler
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Pavel Pudlák
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Robert Šámal
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Tung Anh Vu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Pavel Dvořák .

Editor information

Editors and Affiliations

  1. Durham University, Durham, UK

    Daniël Paulusma

  2. University of Fribourg, Fribourg, Fribourg, Switzerland

    Bernard Ries

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Dvořák, P., Folwarczný, L., Opler, M., Pudlák, P., Šámal, R., Vu, T.A. (2023). Bounds on Functionality and Symmetric Difference – Two Intriguing Graph Parameters. In: Paulusma, D., Ries, B. (eds) Graph-Theoretic Concepts in Computer Science. WG 2023. Lecture Notes in Computer Science, vol 14093. Springer, Cham. https://doi.org/10.1007/978-3-031-43380-1_22

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-43380-1_22

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-43379-5

  • Online ISBN: 978-3-031-43380-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation