Combinatorics Seminar.
Speaker: Nishad Kothari.
Affiliation: Institute of Computing, Campinas, Brazil.
Date and Time: Thursday 20 February, 02:00 pm - 3:30 pm.
Venue: Ramanujan Hall, Department of Mathematics.
Title: Generation Theorems for Bricks and Braces.
Abstract:
A connected graph G, on two or more vertices, is matching covered if each edge belongs to
some perfect matching. For problems pertaining to perfect matchings of a graph — such as
counting the number of perfect matchings — one may restrict attention to matching covered
graphs.
Every matching covered graph may be decomposed into a list of special matching covered
graphs called bricks (nonbipartite) and braces (bipartite); Lov´asz (1987) proved that this
decomposition is unique. The significance of this decomposition arises from the fact that
several important open problems in Matching Theory may be reduced to bricks and braces.
(For instance, a matching covered graph G is Pfaffian if and only if each of its bricks and
braces is Pfaffian.) However, in order to solve these problems for bricks and braces, one needs
induction tools; these may also be viewed as generation theorems for bricks and braces.
Norine and Thomas (2007) proved a generation theorem for simple bricks. In a joint work
with Murty (2016), we used their result to characterize K4-free planar bricks. However, it
seems very difficult to characterize K4-free nonplanar bricks. For this reason, I decided to
develop induction tools for a special class of bricks called ‘near-bipartite bricks’.
A brick G is near-bipartite if it has a pair of edges {α, β} such that G−α−β is matching
covered and bipartite. During my PhD, I (
https://onlinelibrary.wiley.com/doi/10.
1002/jgt.22414) proved a generation theorem for near-bipartite bricks. In a joint work with
Carvalho (
https://arxiv.org/abs/1704.08796), we used this result to prove a generation
theorem for simple near-bipartite bricks. Our theorem states that all near-bipartite bricks
may be built from 8 infinite families by means of (a finite sequence of) three operations.
McCuaig (2001) proved a generation theorem for simple braces, and used it to obtain
a structural characterization of Pfaffian braces — thus solving the Pfaffian Recognition
Problem for all bipartite graphs. A brace is minimal if removing any edge results in a graph
that is not a brace. In a recent work with Fabres and Carvalho (
https://arxiv.org/abs/
1903.11170), we used McCuaig’s brace generation theorem to deduce an induction tool for
minimal braces. As an application, we proved that a minimal brace with 2n vertices has at
most 5n − 10 edges, when n ≥ 6, and we obtained a complete description of minimal braces
that meet this upper bound.
I will present the necessary background, and describe our aforementioned results. The
talk will be self-contained. I shall assume only basic knowledge of graph theory, and will not
present any lengthy proofs.