Matching Theory Lecture-8: CLM Theorem (Lovász's Conjecture) & Subadditivity of b (number of bricks) скачать в хорошем качестве

Matching Theory Lecture-8: CLM Theorem (Lovász's Conjecture) & Subadditivity of b (number of bricks)

(Apologies for the reverberation. Tomorrow, we move back to the better classroom.)In today's lecture, we had a brief discussion pertaining to some history that hopefully puts things in perspective.In particular, one consequence of Lovász's Unique Tight Cut Decomposition Theorem is that the number of bricks, denoted by b(G), is an invariant of any matching covered graph G. This invariant plays a crucial role in the theory as we shall see throughout this course.Another interesting phenomenon is that most problems may be reduced to bricks and braces. In other words, solving the problem for bricks and braces typically solves it for all matching covered graphs. One famous example is the Pfaffian orientation problem. One may read about this in the third part of Lucchesi-Murty (2024).Consequently, one needs induction tools (aka generation theorems) for bricks and braces.An edge e of a matching covered graph G is removable if G - e is also matching covered.It is worth noting that b(G-e) is greater than or equal to b(G). This should seem surprising or somewhat counterintuitive (at least to those who are new to the subject).Lovász (1983) proved that every brick G, except K_4 and the triangular prism, has a removable edge. However, b(G - e) may be arbitrarily large; in other words, the graph G - e may be very far away from being a brick! This inspires the following definitions:A matching covered graph G is a near-brick if b(G)=1.A removable edge e of a matching covered graph G is b-invariant if b(G - e) = b(G).For instance, in the Bicorn graph (discussed in earlier lectures), there is a unique removable edge, and it is also b-invariant. On the other hand, in the Petersen graph, one may check that every edge is removable but none of them is b-invariant. (Of course, Petersen graph is edge-transitive; so, one simply has to check for one edge.)Lovász conjectured that every brick, except K_4, triangular prism and the Petersen graph, has a b-invariant edge.This conjecture was proved by CLM (Carvalho, Lucchesi and Murty) in 2002 in a series of two JCT-B papers. Subsequently, CLM used this result to give simpler proofs of important known results, and also to establish stronger results than some of the earlier ones. A further simplified version of their proof appears in Lucchesi-Murty 2024, and we will hopefully see this proof during this course.In particular, given a removable edge e, it is important that we are able to deduce whether it is b-invariant or NOT. Motivated by this, we shall spend significant time on understanding the behavior of the b function/invariant. The first such result is the following:Theorem 4.20 (Subadditivity of b function): Let G be a matching covered graph, C be a separating cut, and let G_1 and G_2 denote the C-contractions. Then, b(G) is at most b(G_1) + b(G_2); furthermore, equality holds if and only if C is a tight cut.We started the proof of the above theorem, and we shall complete it at tomorrow's lecture.