Chris Purcell @ccppurcell@mathstodon.xyz
Mathematician, computer scientist, bassist, knitter?
Joined Jan 2018
Pinned post
Another thread on a recent paper of mine "On exclusive sum labellings of hypergraphs". It's joint work with Joe Ryan at the University of Newcastle (Australia) and Zdeněk Ryjáček and Mária Skyvová at the University of West Bohemia (where I was while this work was being done).
I'm going to make the intuition toots public, but the rest unlisted to avoid timeline-pollution
Pinned post
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: https://doi.org/10.37236/10383
A paper we started working on in 2016 and first submitted somewhere in 2018 has finally been accepted! Don't give up I guess...
Here's a question that could be a high school mathematics project or something. A k-regular graph has the obvious property that the sum of the degrees of the neighbours of v is equal to k times the degree of v, for each vertex v. But what other graphs have this property? I don't think there's a general rule (maybe I'm wrong!) but start with k=1,2,3 for instance. Follow up questions: can you prove you've found them all? What about infinite graphs/multigraphs? etc.
Finally I can state the main result and end the thread!
A 3-uniform hypergraph of max degree 2 has a 1-ESL iff none of its induced subhypergraphs are the dual of a graph of Type 1-4 (as defined in the previous toot). A minimal example of each is given in the attached image.
This toot is public because it includes the main result and the diagram. This has been a long thread so I'll stop short of sketching the proof. If you've read this far, thanks!
I just noticed I said "2-regular"when I meant "maximum vertex degree 2". Sorry!
A 3-uniform hypergraph with max vertex degree 2 is the dual of a cubic graph (we allow half-edges). Let's define four types of cubic graphs with vertices partitioned into two sets R (red) and B (blue).
1:|R|=|B|, one half edge on each side, no monochromatic edges
2:|R|=|B|, one monochr. edge on each side, no half-edge
3:|B|=|R|+1, three half-edges on the blue side
4:|B|=|R|+2, three monochr. edges on the blue side
Our first mini result is that \(\mathcal{E}_k^{\sigma,\rho}\subseteq
\mathcal{E}_{(\sigma-\rho+1)k}\), and as a corollary for \(\rho=\sigma=r\) we have \(\mathcal{E}_k^r = \mathcal{E}_k\cap\Gamma^r\).
Since \(\mathcal{E}_1\) is already not well understood, the above justifies our interest in the uniform case.
Unfortunately, as I indicated earlier, we need to restrict further to the 2-regular case to make progress.
We're getting close to some results; we need terminology.
Let \(\Gamma^{\rho,\sigma}\) be the set of hypergraphs with edges of size at least \(\rho\) and at most \(\sigma\). Let \(\mathcal{E}_k^{\rho,\sigma}\) be the set of hypergraphs with a \(k\)-exclusive \((\rho,\sigma)\)-sum labelling.
If \(\rho=\sigma=r\) we write \(\Gamma^r\) and \(\mathcal{E}_k^r\); if \(\rho=2,\sigma=\infty\) we simply write \(\Gamma\) and \(\mathcal{E}_k\)
We define a \(k\)-exclusive \((\rho,\sigma)\)-sum labelling of a hypergraph \(G\) to be an isomorphism from \(G\cup kK_1\) to a (\rho,\sigma)-sum hypergraph.
For intuition, the attached image shows, on the left, a \(k\)-exclusive \((3,3)\)-labelling with the isolated vertices having values 8 and 9. It is not a \(2\)-exclusive \(2,\sigma)\)-labelling because \(1+2=3\). However, the hypergraph does have such a labelling, shown on the right (isolated vertices have values 23 and 24).
If you know about sum graphs already, you may be wondering about the restriction on edge size. Sum graphs are defined as having an edge \(x y\) if \(x{+}y\) is a vertex. To motivate our interest in the uniform case, let's define a \((\rho,\sigma)\)-sum hypergraph for \(\rho,\sigma\in[2,\infty]\) to be a hypergraph whose vertex set \(V\) is a subset of the positive integers, with an edge \(\{x_i,\dots,x_s\}\) iff \(\rho\leq s \leq \sigma\) and \(\sum_{i=1}^s x_i\in V\).
In the general case, the picture is much less clear. It is already non trivial to characterise the 3-uniform 2-regular hypergraphs with a 1-ESL. A characterisation of this class is the main result of our paper. We characterise the minimal forbidden induced subhypergraphs for this class.
On the other hand, we show that every hypertree has a 1-ESL and combinatorial designs (thought of as regular uniform hypergraphs) do not.
Allow me to reframe the concept.
Take your favourite hypergraph. I want to label its vertices with unique positive integers in such a way that there are at most \(k\) distinct values of \(s(e)\) where \(s\) assigns to each edge the sum of the labels of its vertices. When is this possible?
If we restrict our attention to graphs (i.e. 2-uniform hypergraphs), the answer is well understood by the work of my first two coauthors and Mirka Miller. https://doi.org/10.1016/j.endm.2017.06.012
In a sum hypergraph, if there is an edge \(\{x_1,x_2,\dots\}\) then the vertex \(\sum x_i\) is the /witness/ for that edge. A sum hypergraph in which all the witnesses are isolated is an exclusive sum hypergraph. An isomorphism from \(G\cup kK_1\) to an exclusive sum hypergraph is a \(k\)- exclusive sum labelling of \(G\).
Exclusive sum labellings are seemingly easier to find, better behaved under disjoint unions of graphs and affine transformations of the labels, and other nice properties.
Sum (hyper)graphs were introduced by Harary, apparently intended as a terse way of representing a graph. You can also define product graphs, etc.
This is an aside but a sum graph (2-uniform hypergraph) is clearly also a product graph (because \(2^a 2^b = 2^{a+b}\)). Interestingly, a product graph is also a sum graph (see https://doi.org/10.2307/2691455 )
The sum number doesn't behave very nicely under some sensible operations, which motivates exclusive sum numbers, defined in the next toot:
A sum hypergraph has set of vertices \(V\) which is a set of positive integers, and \(\{x_1,x_2,\dots\}\) an edge if and only if \(\sum x_i\) is in \(V\). Every hypergraph can be transformed into one isomorphic to a sum hypergraph via the addition of isolated vertices; if you used \(k\) isolated vertices, the isomorphism is a \(k\)-sum labelling of the hypergraph. The minimum number of isolated vertices necessary is called the sum number of the hypergraph.
Another thread on a recent paper of mine "On exclusive sum labellings of hypergraphs". It's joint work with Joe Ryan at the University of Newcastle (Australia) and Zdeněk Ryjáček and Mária Skyvová at the University of West Bohemia (where I was while this work was being done).
I'm going to make the intuition toots public, but the rest unlisted to avoid timeline-pollution
Chris Purcell
boosted
Opinions please!
I'm the lead developer for an open-source project, Numbas (https://www.numbas.org.uk/)
We have a mailing list on google groups for support and discussion, but I'd like something (1) not hosted by google, and (2) a bit more real-time.
It should have archives visible to the public, and ideally be indexed by search engines.
Zulip seems ideal, but public channels aren't search indexed. Other options ticking fewer boxes are Discord, Discourse, or Matrix.
Any other suggestions?
From Gross+Tucker's Topological Graph theory:
exercise: find two connected graphs with 6 vertices and 7 edges which have the same multiset of eigenvalues.
Presumably, two isomorphic graphs is not the intended solution. But otherwise it seems really tricky! Is there a trick to it beyond brute force? Loops and multiple edges are allowed here I think.
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.
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\).
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.
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.
Mathematician, computer scientist, bassist, knitter?
Joined Jan 2018
