Follow

I'd like to tell you about a paper of mine that was published recently. It's called "Subgraph complementation and minimum rank" and it is joint work with Calum Buchanan and Puck Rombach at the University of Vermont (I was at the University of West Bohemia during the project, I am currently between institutions). It was published in Electronic Journal of Combinatorics a couple of months ago. Here's a link: doi.org/10.37236/10383

· · Web · 2 · 4 · 8

I will assume familiarity with basic graph theory and linear algebra.

A subgraph complementation at a set of vertices \(S\) in a graph \(G\) is an operation on \(G\) that replaces the edges between vertices in \(S\) with non-edges and vice versa.

Every graph \(G\) can be constructed by performing a sequence of subgraph complementations on the null graph on \(V(G)\), and we can define the minimum length of such a sequence \(c_2(G)\). I say sequence but the order doesn't matter.

Clearly \(c_2(G)\leq |E(G)|\). To build intuition let me show that \(c_2(C_n)\leq n-2\). I do this by giving a set of \(n-2\) subsets of the vertices of \(C_n\) (which I denote by \(0,\dots,n{-}1\)) so that complementing each subset in the null graph \(N_n\) produces \(C_n\). So: \(\{\{0,1,2\},\{0,2,3\},\dots,\{0,n{-2},n{-}1\}\}\).

This invariant turns out to have several equivalent formulations. For example, a subgraph complementation is like "adding" a clique somewhere in your graph "mod 2"

It's also closely related to a widely studied invariant called the minimum rank of a graph. Let's define it.

A matrix \(M\) *fits* a graph \(G\) if its off-diagonal zero entries are the same as those of the adjacency matrix \(A_G\). The *minimum rank* of \(G\) over a field \(\mathbb{F}\) is the minimum rank of a symmetric matrix over \(\mathbb{F}\) which fits \(G\); we denote this by \(mr(G,\mathbb{F})\)

We are interested in the case \(\mathbb{F}=GF(2)\) So we define \(mr_2(G)=mr(G,GF(2))\)

Now that the definitions are out of the way, let me outline the results. We show that \(mr_2(G)\leq c_2(G) \leq mr_2(G)+1\), and the two invariants coincide whenever \(mr_2(G)\) is odd. Furthermore we characterise the graphs on which they differ in two ways (one is a condition on \(mr_2\) the other on \(c_2\)).

By introducing tripartite complementations (which I will define but it's basically what it sounds like), we can completely characterise \(mr_2\) in terms of complementations.

The classes \(\mathcal{M}_k=\{G:mr_2(G)\leq k\}\) and \(\mathcal{C}_k=\{G:c_2(G)\leq k\}\) are closed under deleting vertices. It is known that \(\mathcal{M}_k\) is finitely defined and its minimal forbidden induced subgraphs (mfis) have size at most \((2^{k-1}+1)^2\) vertices.

The classes coincide for odd \(k\). We show that \(\mathcal{C}_k\) is finitely defined in general. We computed the set of mfis for \(k=2\) shown in the left circle in the attached image.

The final result I want to mention requires a new concept. A tripartite complementation at three sets \(S_0,S_1,S_2\) of vertices of \(G\) is an operation on \(G\) that replaces the edges between \(S_i\) and \(S_j\) (for \(i \not= j\)) with non-edges and vice versa. Worth emphasising that all other edges are left alone.

We allow the subsets in the previous definition to be empty, so complementing a single edge is a special case, and thus we can obtain any graph \(G\) from the null graph on \(V(G)\) by a sequence of tripartite complementations, and define the minimum length of such a sequence by \(t_2(G)\).

Our result then: \(mr_2(G)=\min \{c_2(G),2t_2(G)\}\).

For intuition consider the wheel \(W_5\) on five vertices. It is easy to convince yourself that \(mr_2(W_5)=2,c_2(W_5)=3,t_2(W_5)=1\).

That's the end of the thread. I'm so sorry if I flooded your feed with this: I noticed an unacceptable error in the second toot in the thread just as I got to the end!

I have another recent paper to write a thread about, but I will wait a couple of days. Thanks for reading.

@ColinTheMathmo

Your chart is ready, and can be found here:

solipsys.co.uk/Chartodon/10821

Things may have changed since I started compiling that, and some things may have been inaccessible.

The chart will eventually be deleted, so if you'd like to keep it, make sure you download a copy.

@ccppurcell finally, someone new is posting into #graphTheory 🎉
Nice work!

Btw, some tips about Mastodon:
- we try to use camelCase in hashtags here, for better readability and for screen-readers
- if you don't want to flood the local timeline, you can put all posts after the first one in "unlisted" mode (switch the 🌍 icon to 🔓 ) but know that only public (🌏 ) posts appear in hashtag searches, so all posts containing hashtags should be public, else the hashtag is useless (like mine above)

@tfardet well not exactly new, as I have been here since Jan 2018! But thanks :)

@ccppurcell fair enough, someone new since the past year that I've been desperately looking at that unchanging hashtag entry, let's say ^^

@ccppurcell and I just realized that I posted this as public, of course... -_-

@ColinTheMathmo Thanks for the boosts/likes Colin! I believe you must have met, and I will pass on your regards :)

@ccppurcell I think it was in Vancouver, and just the once, but I'd have to check, and I don't have time just now.

So yes, please do.

NRN

Cheers!

Sign in to participate in the conversation
Mathstodon

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!