Trustworthy Systems

Cardinality of relations with applications

Authors

Rudolf Berghammer, Nikita Danilenko, Peter Hoefner and Insa Stucke

Christian-Albrechts-Universität zu Kiel

Data61
CSIRO

UNSW

Abstract

Based on Y. Kawahara’s characterisation of the cardinality of relations we derive some fundamental properties of cardinalities concerning vectors, points and mapping-related relations. As applications of these results we verify some properties of linear orders and graphs in a calculational manner. These include the cardinalities of rooted trees and some estimates concerning graph parameters. We also calculationally prove the result of D. König that in bipartite graphs the matching number equals the vertex cover number.

BibTeX Entry

  @article{Berghammer_DHS_16,
    author           = {Berghammer, Rudolf and Danilenko, Nikita and H\"ofner, Peter and Stucke, Insa},
    doi              = {10.1016/j.disc.2016.06.019},
    journal          = {Discrete Mathematics},
    month            = dec,
    number           = {12},
    pages            = {3089--3115},
    paperurl         = {https://trustworthy.systems/publications/nicta_full_text/9450.pdf},
    title            = {Cardinality of Relations with Applications},
    volume           = {339},
    year             = {2016}
  }

Download