Description

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.

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.

Description

Ramanujan Hall, Department of Mathematics

Date

Thu, February 20, 2020

Start Time

2:00pm-3:30pm IST

Duration

1 hour 30 minutes

Priority

5-Medium

Access

Public

Created by

DEFAULT ADMINISTRATOR

Updated

Wed, February 19, 2020 7:54pm IST