SEMINAR: Groups and Combinatorics Seminar: The Merino-Welsh Conjecture
|Groups and Combinatorics Seminar: The Merino-Welsh Conjecture
Groups and Combinatorics Seminar
Steven Noble (Brunel University, UK)
will speak on
The Merino-Welsh Conjecture
at 11am Wednesday 2nd of May in MLR2
Abstract: The Merino-Welsh conjecture states that for any loopless, bridgeless graph G, the maximum of the number of acyclic orientations and the number of totally cyclic orientations of G is at least the number of spanning trees of G.
Each of these invariants is an evaluation of the Tutte polynomial, which is a two-variable graph polynomial with positive coefficients. Computational evidence hints that for bridgeless, loopless graphs, the Tutte polynomial might be convex along the portion of lines x+y = constant lying in the positive quadrant. The conjecture is a first small step towards resolving this question.
We will explain the motivation behind the conjecture and discuss some generalizations, in particular to matroids. We will then show that the most general convexity conjecture holds for a large class of matroids and that something much weaker holds for all loopless, bridgeless matroids. Almost no knowledge of matroids will be assumed!
Maths Lecture Room 2
Wed, 02 May 2012 11:00
Wed, 02 May 2012 11:45
Michael Giudici <[email protected]>
Thu, 26 Apr 2012 08:43
- Locations of venues on the Crawley and Nedlands campuses are
available via the Campus Maps website.
- Download this event as:
Mail this event: