Primes and Squares

« first day (426 days earlier) ← previous day next day → last day (798 days later) »

4:23 AM

I've got a graph theory question

Kind of?

So, a round robin makes a complete graph

but the issue with a round robin is the number of games you have to play: With games of 2 teams, you have to play N^2 games

and if games involve more than 2 teams, it gets even worse

Is there some sort of "sparse round robin"?

I'm not sure of a formal definition, but I want teams to play a variety of other teams

but I don't want it to be random, and I don't want it to be based on their score

Nathan Merrill

4:41 AM

ok...maybe a more formal way of saying it:

I want the sparseness of every subgraph to be as similar to similarly sized subgraphs as possible

for example, let's say that I've got a graph of 10 nodes, and after my first "iteration", I've got a clique of 4 nodes, plus a couple of other connections

this is a problem, because if I iterate through every subgraph of size 5, most of them will either have a very high sparseness, or a very low sparseness

El'endia Starman

I'm on my way to bed, but one thing that comes to mind is ensuring that every node has the same degree. That will help with ensuring that subgraphs of the same size are similar on average.

Nathan Merrill

oooh, that's a simpler mechanic

hmmm...I'm not so sure a graph really works now that I think about it

like, lets say I have 4 teams: A,B,C,D, and games that involve 3 players

The full round robin is:
A,B,C
A,B,D
A,C,D,
B,C,D

if the "nodes" are the players, then what are the connections?

if each game is making 3 connections, then does A-B get two connections?

This is no longer a simple graph

if the "nodes" are the games, then once again, I have no idea what a connection is

furthermore, that changes the problem from "adding connections" to "adding nodes"

ooooh!

I think I know of an algorithm

I pick a number that does not share any factors with the number of teams (N)

the first game is the Nth team, the (2*N)th team, and the (3*N)th team (for games of 3 teams)

...hmmm, nevermind.

that doesn't work. If I had 9 teams, and games of size 3, I could end up with sets like:

(1,3,5), (7, 9, 2), (4, 6, 8), (1, 3, 5)

and even if the game size (3) didn't divide the number of teams (9), we'd still have a problem that certain numbers would never go together

(you'd never see a 1 and a 4 competing against each other)

Nathan Merrill

5:26 AM

Ok: Ignore everything above, I think I have a good definition:

Given a set of N elements, I need to iterate through all of the combinations of size M

however, if I stop partway through iteration, I need every smaller combinations to be equally represented (within 1)

So, as a concrete example, lets say I have 5 elements (A, B, C, D, E) and combinations of size 4.

the following iteration would be invalid:

1. A, B, C, D
2. A, B, C, E
3. A, B, D, E
4. A, C, D, E
6. B, C, D, E

lets say I stop after step #3

lets look at combinations of size 2

the combination "A, B" is represented 3 times

while the combination "D, E" is only represented once

the difference between any two smaller combination can be at most 1

...snap. I tried to come up with a good example of the iteration above, and it's impossible

bah, this is hard

5 hours later…

PhiNotPi

10:20 AM

@NathanMerrill I think this is impossible and I can probably prove it.

Although I think it depends on the exact size of the set you're using and how many are selected for each iteration.

Took me a moment to find an easily provable case. I actually don't think this proof works in the case of size 4 combinations from 5 elements, but rather it's easy if there's size 5 combinations from 6 elements.

If you have 6 elements, there's 6 possible size 1 combinations and 15 possible size 2 combinations. Each round is a subset of size 5, which contains 5 size 1 combos and 10 size 2 combos.

After 3 rounds, you've created 30 size 2 combos, which is divisible by the 15 possibilities. Therefore each combination must appear three times (otherwise, one would appear twice while another appears four times, which violates our requirement).

And given that each instance of each element contributes to the same number of size 2 combinations, the only way for all size 2 combinations to be present in equal number is if all elements (size 1 combos) are present in equal number.

But after only 3 rounds, you've only used 3*5 = 15 size 1 combos, which is not divisible by 6. So, not all elements can be present in equal number (there's 3 each of 3 elements and 2 each of 3 others).

So there's the proof that it's impossible to do this in the general case.

When it comes to size 4 combinations from 5 elements, the above argument doesn't apply because the numbers of smaller subsets happen to be divisible in the proper way.

     A B C D E AB AC AD AE BC BD BE CD CE DE
ABCD 1 1 1 1 0 1  1  1  0  1  1  0  1  0  0
BCDE 1 2 2 2 1 1  1  1  0  2  2  1  2  1  1

But it's easy to see that it's impossible with your example as well.

2 hours later…

Nathan Merrill

12:35 PM

@PhiNotPi Each combination must appear 2 times, no?

30/15 = 2

that doesn't invalidate your proof though :)

PhiNotPi

@NathanMerrill yeah, that's correct

Nathan Merrill

bah...I can logically accept your proof, but it doesn't feel intuitive at all

like, my brain is still trying to search for orderings that work

PhiNotPi

12:51 PM

Although your problem is still interesting... if it's impossible to be perfect, what's the best we can do?

Nathan Merrill

I posted it on Math.SE, and Peter Taylor brought up an interesting point: How do you minimize multiple things?

PhiNotPi

Either minimize the maximum, or figure out some priority order.

Nathan Merrill

hmmm...does minimizing the maximum inherently prioritize the smaller combinations?

because they have the biggest variance?

...I think I like that, even if that is true

because in my use-case (King of the hills), I care more about ensuring that each player plays an equal number of times than I care that each pair has played an equal number of times

2 hours later…