Thursday December 29th

Matroids Week 2

My list is getting kind of long

  • I’m going to start putting some of my notes from this week here. I also have a private Repo where I generally collect Graphs Combinatorics stuff, which primarily started when I was first taking classes with my Graph Theory prof (I swear every time you go to their office, you come out with a book!), as well as doing research with them. I will probably not formally put links here, because some require logging in and that sort of thing (ie. institutional access for some publications I read this week).
  • The two lectures I enjoyed the most were on Tutte Grothendieck and Error-Correcting Codes. Chain groups are SICK!
  • I also fell in love with the Matroids II paper by Tutte! It made me think so much of functional programming, strangely (recursion, etc).
  • I found a post online on Rota’s Conjecture, which strangely was linked to a blog by someone I met in Art school (or rather, a weird painting and drawing group I joined in LA with a mix of science and art people), who was doing their PhD at the time in Mathematics at Princeton. They are no longer a Mathematician, sadly (the post was from 2014), but then again they moved on to being a founder (yes, like “I live in SV and I got seed-funding” founder), and if they’re super successful they can fund the work of mathematicians, so I think that’s great, too! But that coincidence this week was very unexpected!

Topics

  • I basically made my way through videos 15 through 43 this week (they’re each an hour long or so, and there is an off-by-one error in the indexing). Powered through this week, and also read a couple relevant papers. I stayed up until 4am to 5am on some mornings, because the lectures were really interesting! I’m hoping to continue digging through the Oxley book on Saturday.
    • Lattices, Flats, Posets of Flats
    • Fano matroid
    • What are Transversal Matroids wrt selection and contractions? If we take the minor of a transversal, we may not have a transversal matroid. Graphical matroids are closed under minors. Linear matroids are closed under minors (and duals). Gammoids are closed under minors
    • Pappus’s Theorem
    • Desargues’s Theorem
    • Algebraic Matroids
    • Mobius functions
    • Characteristic Polynomial (using Mobius function \mu: P -> Z) : (some review from class!)
    • Mobius Inversion Formula
    • Chain groups (see HTM II by Tutte)
    • Kuratowski Theorem (mentioned in the lecture but also mentioned in HTM II by Tutte)
    • Zaslavsky’s Theorem, notions of Topological Invariants via Computing Euler characteristic
    • Braid Arrangements
    • Tutte Polynomial (did this in class) and Deletion-Contraction Recursions
    • Tutte-Grothendieck Invariants (generality of Tutte Polynomial)
    • Flow polynomials (Applications of Tutte Polynomials)
    • Tutte polynomials related to network reliability
    • Calculating the reliability polynomial (Tutte Polynomial, have situation where an edge may or may not be present with some probability p; what is prob our graph is still connected?)
    • Error-correcting codes (the weight enumerator, calculating errors in F_2 example, how it relates to Tutte polynomials)
    • Some Knot theory (ambient isotopic)
    • Coefficients of Tutte Polynomial
    • Catalan Matroid and Bases, Dyck paths, Gröbner basis relation (see Lec 38)
    • Calculating Capo’s theorem using Up steps and bounces (coroll: Proof of Catalan matroid and its dual are isomorphic (using up steps and bounces))
    • Matroid Polytopes (finally!). Think of them as a bunch of linear inequalities.
    • Defining the Convex hull and polytopes
    • Creating an octahedron by using R^3
    • Facet descriptions
    • Introduction of Linear Programming as related to Polytopes (Simplex algo and ellipsoid methods: I’ve used these computationally!)
    • Weak and Strong Duality Theorem
    • Primal and Dual example where the Dual Polyhedra was unbounded (See Lecture 40)
    • Cyclic flats and lattices, systems of mirrors (e_i - e_j)
    • Coxeter groups and Coxeter Matroids

Note: Maybe Look at again

  • Lecture 18: Geometric lattices and coatomic property proof.
    • co-atom: in a partially ordered set, a non-unit element that has no element above it other than the unit (assuming that the poset has a top element, its “unit”). In a Boolean lattice, the complement of an atom is a co-atom. (Not a coatroom lol, which my Notes App again tried to auto-correct).

Readings this week I came across

  • Tutte (1958): A Homotopy Theorem of Matroids I, II: 2 talks about chain groups
  • Bixby, R. “On Reid’s Characterisation of the Ternary Matroids” (1975)
  • Rota, G-C. “On the Foundations of Combinatorial Theory I” (1964)
  • Geelen J., Gerards B. And Whittle G., “Solving Rota’s Conjecture”, 1999: link
  • Blog post on “Jim Geelen, Bert Gerards and Geoff Whittle Solved Rota’s Conjecture on Matroids” by G. Kalai: link
  • Athanasiadis, C, “Algebraic Combinatorics of Graph Spectra, Subspace Arrangement and Tutte Polynomials”, 1996:
    link
  • Brylawski, TH, “The Tutte-Grothendieck Ring, 1972
  • Weight Enumeration and the Geometry of Linear Codes (Greene, 1976)

Quantum

  • I joined a Quantum book club, since that actually relates to my thesis. It’s a good group! I did not have time to read this paper on Polyadic Quantum Classifiers, but someone mentioned it in the group. We just started and we’re going on to chapter 2, which is a lot of notation, operations, etc. The group seems to be a mix of persons with Physics backgrounds, Pure Mathematics backgrounds, and Computer Science, which as you know is heaven for me, because they’re nice and we have to agree upon and cross-pollinate in terms of a shared “language” between us for understanding the material. So that’s cool. The pacing is great since they only meet every two weeks, but are pretty active on Discord otherwise, so I still have time to get my main focus on Matroids done, and get the reading done for the next get together in two weeks.

Anyways

  • I’m still making my way through the last set of lectures, but so far, so good. I think at some point my mom left to head to sleep, asked me if I was heading to bed in an hour, and I completely agreed that I was, and she got up at 5am and realized I hadn’t gone to sleep yet. The material was just so good! Plus, I have this awesome schedule where I can stay up really late, get up for breakfast and then head back to sleep, and then get up really late to do work again. I keep thinking if I found a gig like this research-wise, it would kind of be ideal, because I love staying up late, and it’s when I am most focused (but I admit I can be a PITA to my peers when I am really excited about things at that hour and accidentally ping them, not realizing it’s 3am or something, and they might be asleep).
  • This week has been simultaneously restful and thrilling.

Anyways…that’s it!

Written on December 29, 2022