Faculty of Mathematics, Physics
and Informatics
Comenius University Bratislava

Seminar of Graph Theory - Babak Ghanbari (14.12.2023)

Thursday 14.12.2023 at 9:50 hod., Lecture room C


12. 12. 2023 20.43 hod.
By: Martin Škoviera

Babak Ghanbari (Charles University, Prague):
Fractional forcing number of graphs


Abstract:
The notion of "defining set" is an important concept in studying combinatorial structures. Roughly speaking, when we talk about a defining set for a particular object, we mean a part of it that uniquely extends to the entire object. As an example, a defining set for a particular perfect matching M of a graph (known as a "forcing set") is a subset of M such that M is the unique perfect matching of the graph containing it. The size of the smallest forcing sets of a perfect matching is called the "forcing number" of it.  

In this talk, we introduce the notion of the forcing function of fractional perfect matchings, which is continuous analogous to forcing sets defined over the perfect matching polytope of graphs. Our defined object is a continuous and concave function extension of the integral forcing set. Then, we use our results about this extension to conclude new bounds and results about the integral case of forcing sets for the family of edge and vertex-transitive graphs, and in particular, hypercube graphs.

More information