Graph theory question
Jan. 20th, 2024 11:05 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
jackQuestion 1
You have a graph on an even number P people where each node has E=3 edges connected to it. You colour in one edge. Then you colour in another edge such that each person has at most one coloured edge, aka not touching a previous coloured edge (without planning ahead). You keep doing this as long as you can.
I think for some graphs (e.g. 4 people, or 6 people each connected to the adjacent people and the opposite person) you are guaranteed to be able to colour P/2 edges so that each person touches exactly one coloured edge, whatever your early choices were. Whereas for other graphs (e.g. the corners of a triangular prism?) you can end up in a "dead end" where you've coloured two edges and then the two people left over with no coloured edge have no edge between them to colour.
Is there a description of which graphs guarantee and which don't? What about if E=2 (probably usually not guaranteed?). Or E=4?
Question 2
You have a graph with even P nodes each with E=3 edges. There are A=3 acts. In the first, you colour P/2 non-touching edges. In the second you colour P/2 non-touching edges, not colouring edges that were coloured in act 1 (without planning ahead to act 3). In the third act, you also try to colour P/2 non-touching edges that weren't coloured in acts 1 or 2. Are there graphs where if you colour the edges one at a time you're guaranteed to fill in all the edges without discovering you need to backtrack?
What about for different values of E and A? If E is greater than A? If E is ALL the possible edges then it's always possible, but for values less than that?
Question 3
You have a graph with even P nodes each with E=3 edges. There are A=3 acts. In the first, you colour P/2 non-touching edges with +1, 0 or -1. In the second you colour P/2 non-touching edges, not colouring edges that were coloured in act 1, with +1, 0 or -1 (without planning ahead to act 3). In the third act, you also try to colour P/2 non-touching edges that weren't coloured in acts 1 or 2, also with +1, 0 or -1, but try to ensure that three values each node touches sum to 0. Are there graphs that guarantee that's possible in act 3, regardless of what you did in acts 1 and 2?
What if you had E=4 and coloured +1 or -1?
You have a graph on an even number P people where each node has E=3 edges connected to it. You colour in one edge. Then you colour in another edge such that each person has at most one coloured edge, aka not touching a previous coloured edge (without planning ahead). You keep doing this as long as you can.
I think for some graphs (e.g. 4 people, or 6 people each connected to the adjacent people and the opposite person) you are guaranteed to be able to colour P/2 edges so that each person touches exactly one coloured edge, whatever your early choices were. Whereas for other graphs (e.g. the corners of a triangular prism?) you can end up in a "dead end" where you've coloured two edges and then the two people left over with no coloured edge have no edge between them to colour.
Is there a description of which graphs guarantee and which don't? What about if E=2 (probably usually not guaranteed?). Or E=4?
Question 2
You have a graph with even P nodes each with E=3 edges. There are A=3 acts. In the first, you colour P/2 non-touching edges. In the second you colour P/2 non-touching edges, not colouring edges that were coloured in act 1 (without planning ahead to act 3). In the third act, you also try to colour P/2 non-touching edges that weren't coloured in acts 1 or 2. Are there graphs where if you colour the edges one at a time you're guaranteed to fill in all the edges without discovering you need to backtrack?
What about for different values of E and A? If E is greater than A? If E is ALL the possible edges then it's always possible, but for values less than that?
Question 3
You have a graph with even P nodes each with E=3 edges. There are A=3 acts. In the first, you colour P/2 non-touching edges with +1, 0 or -1. In the second you colour P/2 non-touching edges, not colouring edges that were coloured in act 1, with +1, 0 or -1 (without planning ahead to act 3). In the third act, you also try to colour P/2 non-touching edges that weren't coloured in acts 1 or 2, also with +1, 0 or -1, but try to ensure that three values each node touches sum to 0. Are there graphs that guarantee that's possible in act 3, regardless of what you did in acts 1 and 2?
What if you had E=4 and coloured +1 or -1?
no subject
Date: 2024-01-21 11:05 am (UTC)If you were defining a sequence of integers instead of a property of graphs, then my invariable advice would be to generate the first few terms of the sequence and look it up on OEIS. I don't know if there's a similar library of graph properties, but I wouldn't be entirely surprised.
If there is, then perhaps some alternative phrasings of the problem might help as search terms.
I think an equivalent version of your question 1 is obtained by, instead of considering "colouring in" an edge, consider deleting the edge, both its end vertices, and all other edges incident to those two vertices. Then we define a subset of graphs to be reducible (a made-up name for this comment, not standard as far as I know) by inductively defining them in order of edge count as follows: the empty graph is reducible, and otherwise, a graph is reducible if and only if deleting both end vertices of an edge results in a reducible graph, regardless of which edge you choose.
(I doubt there's any point defining this for only regular graphs; it seems to me that it's a meaningful property that any graph might or might not have. In particular, after you delete one edge from your initial regular graph, the intermediate graphs you pass through on your way to the empty graph are not regular, so we need to define it more generally anyway, even if you end up only interested in the graphs that are both reducible and regular.)
One could use that inductive definition to exhaustively generate the reducible graphs of small size, simply by iterating over every possible graph with sufficiently few vertices, test-removing each edge in turn, and consulting a table of all the smaller graphs you've already checked. You could surely find all the ones up to 6 vertices this way, and maybe 8 if you waited a bit. That might be enough to think of a plausible conjecture and try to prove it – or to look it up on an index site, if anyone knows of one!
no subject
Date: 2024-02-21 10:06 am (UTC)no subject
Date: 2024-02-21 10:44 am (UTC)Looking at the proof there, it looks as if the prover has understood Q1 as saying something different from what I thought it was. They seem to be answering the question "is there a pairing that works?", because their proof is going through cases and saying which choice you should make in each case.
But I thought you were asking for a much stronger condition on the graph: not just "at least one pairing exists", but "we can reliably find a pairing via the trivial algorithm of picking any old thing, committing to it, and repeating, regardless of how the arbitrary choices are made".
no subject
Date: 2024-02-21 12:17 pm (UTC)no subject
Date: 2024-02-21 12:20 pm (UTC)no subject
Date: 2024-02-21 01:28 pm (UTC)matchings
Date: 2024-02-02 08:27 pm (UTC)For the second question, we can consider the standard algorithm for finding a maximal/perfect matching in a general graph. Edmonds' blossom algorithm, when it gets stuck, contracts an odd-length-loop into a point, and then tries swapping (coloured<->uncoloured) the edges around it.
Obviously, this is only possible if there's an odd number of edges to swap, and they're not themselves just a loop. If you consider the 4-person graph, if I squash three points into a dot, I'm going to be left with two points, connected in a triangle. I can't do any swapping, so the matching I had must have already been the best I can do.
So, we can say that the guarantee fails if a graph can be squashed in this way, i.e. if Edmonds' blossom algorithm would successfully backtrack/augment.
Is there a more general description of when a graph would be squashable? Firstly, there must exist odd-length loops in the graph. In the case of E=2, P=2n, this is never true, is it? Isn't such a graph just one big loop with P edges?
But I think for most more general graphs, there will be odd-length loops. Secondly, there must be at least four vertices after the squashing, so that you have three edges you can do a swap on. So you need at least 6 people.
... not sure if those ideas help at all?
Re: matchings
Date: 2024-02-03 10:25 am (UTC)My hunch is that if it has < 4*E (i.e. 2*E people on each "half"), you're golden, and otherwise you need some very careful structuring, but that's mostly a hunch.
After that you could move on to more general graphs by considering the bipartite graph that you get when you squash down all the odd-length circuits. Unlike the bipartite graphs we were considering above, this one won't necessarily have a fixed number of edges per vertex. Also, I think I'm wrong about needing four vertices after squashing. If I have (odd-length circuit) - P - (odd-length circuit), I could have coloured the "wrong" edges in both of the odd-length circuits, such that I can't colour either of the edges adjacent to P, but squashing allows me to pick one of them to colour.
(... really suspect I'm not helping at all here... )
here's an example though of a general graph with 3 edges per vertex that doesn't have a perfect matching: http://mair.cloud.mech.cx/graph.pdf -- you have 16 (and I think that's the minimum to achieve this) people (assume the ... are the same as the blob on the right) but the best you can do is colour 7 edges. You can also do the colouring "wrong" so that you get stuck after 6 (and have to do exactly the squash and recolour I mention above)
Re: matchings
Date: 2024-02-21 10:06 am (UTC)Re: matchings
Date: 2024-02-21 10:23 am (UTC)no subject
Date: 2024-03-08 11:04 am (UTC)(* probably not very, really...)