2
$\begingroup$

Take an $A \times B \times C$ cubic lattice graph $G$, and paint $k_1$ vertices with color $c_1$ & $k_2$ vertices with color $c_2$, where $(k_1 + k_2)$ is equal to the total vertex count. Let $s_1$ be the number of edges between vertices of identical coloration, and $s_2$ be the number of edges between vertices of distinct coloration. How many pairs $(s_1, s_2)$ exist?

Also, is it known how many distinct total colorations of $G$, with $k_1$ and $k_2$ colors of type $c_1$ and $c_2$, respectively, exist up to rotational & reflectional symmetry of the graph?

Edit: I need to specify that, in the above problem, $k_1$ and $k_2$ are exactly specified, and I am looking for an exact counting solution as a function of $A$, $B$, and $C$ (i.e. as a function of the edge lengths of the cubic lattice). I apologize for any confusion this may have caused.

Edit 2: Actually I would also be perfectly happy with an exact counting solution where $A$, $B$, and $C$ are exactly specified, and we have an exact counting solution as a function of $k_1$ and $k_2 = (A*B*C) - k_1$.

Improve this question
$\endgroup$
7
  • $\begingroup$ I believe the number of impossible pairs of s's is less than d^2, for d the maximal degree of the graph, which should be 6. Indeed, using an incremental checkerboard coloring allows us to add 3 or 4 or 5 or 6 edges to one of the totals, giving us something similar to a numerical semigroup of possibilities. Other colorings may take us to O(d) exceptions. As for distinct colorings, most are asymmetric, so there are about 2^(v-4) distinct colorings up to symmetry on the v many vertices. $\endgroup$
    – The Masked Avenger
    Commented Mar 5, 2014 at 0:24
  • $\begingroup$ Note that the above remarks extend to general bipartite graphs, although the v-4 term may need tweaking. $\endgroup$
    – The Masked Avenger
    Commented Mar 5, 2014 at 0:29
  • $\begingroup$ If the k's are fixed in advance, the number changes, but again starting with a partial checkerboard coloring, one arrives at a stamp or coin problem which has been studied. Similarly, most colorings with fixed k are assymetrical, so dividing by 8 or by 16 gets you in the ballpark. $\endgroup$
    – The Masked Avenger
    Commented Mar 5, 2014 at 0:34
  • $\begingroup$ @TheMaskedAvenger Terrific comments - I'm hoping an exact counting solution is possible though, at least for a class of cases, and I'm working on that. $\endgroup$
    – Mfms
    Commented Mar 5, 2014 at 0:39
  • $\begingroup$ Ok. It is unclear what are the parameters. Do you want a function of A B and C, or are the k's also given as input? Please edit the question to clarify. $\endgroup$
    – The Masked Avenger
    Commented Mar 5, 2014 at 0:53

1 Answer 1

Reset to default
1
$\begingroup$

This is more a collection of potentially useful ideas and intuitions, with no guarantee of correctness and no proof.

If you take a coloring and tweak it by switching the colors on two vertices of opposite color, you land in the same class of colorings $(k_1,k_2)$ while making an incremental change in the s values of any number from 0 up to twice the maximal degree D in the graph, since you have vertex degrees ranging over all values in [D/2,D]. I expect the s values to range over a large interval, missing at most D values near the ends of the interval, and only when $k_1$ or $k_2$ is smaller than D.

Using a checkerboard coloring, $s_2$ can be pushed toward $Dk_1$ until you run out of colors or edges. Using a compact coloring, one can push $s_2$ down to AB + A + 1 or slightly lower depending on $k_1$ being a large enough multiple of A or AB. When $k_1$ is smaller than A a different analysis will be needed. I assume A< B< C. (So it may be that A is the limiting factor more than D in the previous paragraph.)

I think that this can be reframed in terms of general bipartite graphs and can benefit from research on numerical semigroups and the Frobenius coin problem. In particular, I do not see constraints that indicate large exceptional values for $s_2$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ For large A, you can pack k^3 vertices to get s_2 to be 6k^2, so the problem of small k is of independent interest. $\endgroup$
    – The Masked Avenger
    Commented Mar 6, 2014 at 19:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .