Tag Archives: notes

Minimum rank of graphs with loops

28 Jun

A few months ago I was one of two Distinguished Graduate Speakers at this awesome conference, Underrepresented Students in Topology and Algebra Research Symposium (USTARS).  The conference started in 2011, when a bunch of advanced grad students and postdocs (I don’t think anyone on the committee was a professor yet) decided that there needed to be a place for underrepresented students to see other people like them doing the math they did.  And now they’re all professors and still organizing this traveling conference!  So many people of color!  So many women!  So many homosexual people!  (Not so many trans people…) So many first-generation college students!  So great!  Too many slides!  (I pretty actively hate slide talks unless there are pictures that are impossible to make on a chalk board.)

Credit: Erik Insko for this picture of me giving a talk at USTARS 2016!

Anyway, I wanted to blog about some math I saw there, based on a talk by Chassidy Bozeman, a grad student at Iowa State and a fellow EDGE-r.  The talk is from a paper that resulted from her graduate research course, which Iowa offers to intermediate grad students and gets them started on research (hence the eight authors on that paper).  I thought it was fun and approachable!  And I have one crumpled page of two-month old notes, so we’ll see how this goes.

First, let’s remember what a graph is: a collection of vertices (dots) and edges (lines between dots).  A graph is simple if there’s at most one edge between any two vertices, and if no vertex has an edge to itself (aka a loop).  A loop graph allows loops, but still no multiple edges.

Left is a simple graph, right is a loop graph

You can associate an infinite family of symmetric matrices to a loop graph.  These square matrices will have the number of vertices of the graph as the number of columns and rows, and the entry $a_{ij}$ will be 0 if and only if there is no edge between the corresponding vertices and  in the graph.  The rest of the entries will just be real nonzero numbers.  This infinite family is useful for defining the minimum rank of a loop graph: it’s the minimum rank over all of this infinite family of matrices.  The rank of a matrix is a measure of how large it is.  For definition by example, $\left( \begin{array}{cc} 1 & 0 \\ 1 & 0 \end{array} \right)$ has rank 1, and $\left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right)$ has rank 2.

So the goal of Chassidy’s talk was to characterize all loop graphs whose minimum rank is the full size of the graph.  A couple more definitions before the theorem: a generalized cycle is a subgraph whose connected components are either a loop, a single edge, or a cycle.  It’s spanning if it touches every vertex in the graph.  Spanning generalized cycles don’t always exist!

Components of a generalized cycle: loop, edge, cycle

No spanning generalized cycle, womp womp

Theorem: A loop graph has minimum rank equal to its size if and only if there exists a unique spanning generalized cycle.

Quick nonexample: here’s a picture of a loop graph that has more than one spanning generalized cycle, so from the theorem we know it doesn’t have minimum rank four.

This is theorem 3.1 in their paper.  It’s also comically the end of my notes on this talk.  Here are a few facts they use to prove the theorem:

• If is an induced subgraph of G (that means the vertices of H are a subset of the vertices of G, and its edges are all the edges that appear in G within that subset), then it minimum rank is bounded above by the minimum rank of G.  Succinctly, $mr(H)\leq mr(G)$.
• If is a disjoint union of a bunch of connected components, the its minimum rank is the sum of the minimum ranks of those components.  $mr(G)=\sum mr(G_i)$.

Here’s a picture of my notes!  Read the actual paper if you want to know more!

Jet lag but here are some (very hard) math notes

31 Jul

Hi!  I just got back from a fun weeklong trip with two of my best friends from college (you can read about our Turkish bath adventure and making friends with a local on Edward’s blog).  My entire body feels like it’s made out of wet noodles and my head also feels like that delicious chocolate mousse.  You guys, I rock at jet lag.  It takes me three or four days each time to become a functional person again.

In the meantime, I’ll link you to these math notes that I typed up from a mini course that the incredible Matt Clay gave at a summer school I attended in Marseille.  Also, if you want to know why I call Matt incredible (besides his math), go to his website and click on the “running” header.  Ridiculous.  I actually know a few ultramarathoners now (I mean three) and when I read the latest Oatmeal comic, I kept thinking of them.

Anyway, here are the notes, about the Guirardel Core in Outer Space (the other notes on Catherine’s website should help with the definition of Outer Space; these notes define the core).  Someday I’ll edit my website and they’ll be up there (along with those ones from that conference I went to in Haifa).

Also, sometimes when I look at stuff I’m just in total awe of how long it must have taken.  Those notes are 14 pages long and they aren’t that great (for one thing, I just MS Paint-copied the figures from Matt’s handwritten notes), but they still took me probably 15-20 hours to write.  It took 5 hours for Matt to give his lectures.  I probably spent an hour, all told, chatting with him for clarifications.  And it probably took him 7-10 hours to put together the lectures, and countless hours to put together the material for the lectures (aka do the research).  I think as you get farther in academia the better you are at focusing for long stretches of time- I can’t do math for more than an hour at a time, really.  My brain starts turning into how it feels right now.  In college when studying for a math final (or any final) I would study for an hour, then take a break and run a lap around the courtyard or read a comic or eat a banana.  Now it’s sitting on the internet for a few minutes.  Like with you guys right now!

OK that’s my wet noodle head post for ya!  Next one will be more lucid and have more content, I promise!

Hi from Israel!

3 Feb

Hi from Israel!

I’m at Young Geometric Group Theory II, the second international meeting of grad students, postdocs, and young faculty in GGT.  My new goals for the year, mathematically are:

a) Always ask a question in our small weekly GGT seminar with my advisor and a few grad students

b) Type up something related to each conference I attend

So here’s the first lecture from the four-lecture minicourse that Frederic Haglund is giving us on CAT(0) cube complexes.  Remember my blog post on special cube complexes and how that was not so great for non-mathematicians?  These are pure notes so they’re really aimed at someone like me: beginning-middle graduate students.