Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
The problem of identifying ''good'' n-tuples is weakly NP-complete ( en.wikipedia.org/wiki/Partition_problem ), so there are some limitations on the simplicity of equivalent conditions.
There appears to be an implementation of an integer programming formulation that has worked on graphs of roughly the same size as yours: sciencedirect.com/science/article/pii/S1572528607000497#sec5 . You could try that to see if your conjecture is true. (The approach of Noam Elkies in the previous question only seems to yield that the crossing number is at least 36, unless I made a calculation error.)
@Ethan Yeah, but that doesn't contradict what I'm saying. I mean that a unicycle gives an example of a graph with your property that is not 2-edge connected. (Maybe your 'iff' is meant to be an 'if'? Actually I'm not sure about that either, e.g. consider the wedge of 2 circuits at a single point. It's 2 edge connected, but the circuit graph consists of two isolated points.)
@Ethan Is that condition about the graphic matroid right? For instance, a unicycle graph has a single circuit, so the intersection graph is connected, but it is not 2-edge connected.
@LSpice While I agree in general with that sentiment, these particular graphs were constructed precisely for the mentioned application. The idea of associating such kind of interaction graphs to computational problems is very old -- aspects go back to at least the 70s, and one of the key theorems was proved in 1990: en.wikipedia.org/wiki/Courcelle%27s_theorem . My understanding is that the reason that the commutative algebra paper I linked is so recent is that making the same strategy work in that context is harder; for instance, one needs a geometric condition as well.
@Math_Freak This is an answer to : "Can someone show me by giving an example of a problem in group theory or ring theory which can be solved by associating a suitable graph structure?"
This got bumped again, so let me add a few more tools you can look into: 1) Binary decision diagrams / ZDDs ( there is a python library for this tool link.springer.com/article/10.1007/s10009-014-0352-z ) ... if you can construc the ZDD you can count, sample , optimize... this tends to work for 'medium' sized problems 2) You can sample if you can compute the marginal probabilities. All of these can be encoded as SAT problems, and you can feed it to a #SAT solver. 3) If the underlying graph has small treewidth, you can use (complicated) a dynamic program.
