Skip to main content
MathOverflow

Return to Answer

Notation and grammar.
Source Link
M. Vinay
M. Vinay
  • 178
  • 1
  • 1
  • 8

Suppose $G$ has order [number of vertices] $n$, and contains $m$ copies of $H$ as subgraphs (in the special case $H = K_2$, $m$ will be the size of $G$), and label them $H_1, H_2, \ldots, H_m$. (Some of them may share common vertices, which is not an issue). Let $r$ be the order of $H$.

Fix $t$, the number of colours available.

Let $N(H_i)$ be the number of colourings of $G$ in which $H_i$ is monochromatic. More generally, let $N(H_{i_1}, \ldots, H_{i_k})$ be the number of colourings in which each of $H_{i_1}, \ldots, H_{i_k}$ is monochromatic (not necessarily of the same colour). This will always be a power of $t$, and the power depends only on the structure of $G$ and $H$ (not on the value of $t$ itself), as shown below.

By the Inclusion-Exclusion Principle, the number of ways of colouring $G$ with $t$ colours such that none of the $H_i$s areis monochromatic is \begin{equation*} t^n - \sum_{i} N(H_i) + \sum_{i < j} N(H_i, H_j) - \cdots + (-1)^k \sum_{i_1 < \cdots < i_k} N(H_{i_1}, \ldots, H_{i_k}) + \cdots + (-1)^m N(H_1, \ldots, H_m) \end{equation*}\begin{equation*} P_H(G, t) = t^n - \sum_{i} N(H_i) + \sum_{i < j} N(H_i, H_j) - \cdots + (-1)^k \sum_{i_1 < \cdots < i_k} N(H_{i_1}, \ldots, H_{i_k}) + \cdots + (-1)^m N(H_1, \ldots, H_m) \end{equation*}

which is a polynomial in $t$ since each term is a power of $t$ (in terms of $n$ and $r$).

Proof that the powers depend only the graph structure

First, observe that $N(H_i) = t^{n - r + 1}$. That is, as $H_i$ is monochromatic, all its vertices must be assigned any one of the $t$ colours, which can be done in $t$ ways. The remaining $n - r$ vertices of $G$ must each be assigned a colour as well, which can be done in a total of $t^{n - r}$ ways. Thus, there are $t^{n - r + 1}$ colours in total, with $H_i$ monochromatic.

Now, consider $N(H_i, H_j)$. If $H_i$ and $H_j$ have no common vertices, then whatever be the value of $t$, $N(H_i, H_j) = t^{n - 2r + 2}$. If $H_i$ and $H_j$ have at least one common vertex, then both of them must be assigned the same colour, and hence $N(H_i, H_j) = t^{n - 2r + 1}$. Note that the power is independent of $t$ and is determined solely by the graph structure.

Generalising, consider $N(H_{i_1}, \ldots, H_{i_k})$. Again, depending (only) on the distribution of shared vertices among these subgraphs, the set $\{H_{i_1}, \ldots, H_{i_k}\}$ can be partitioned into some $p$ number of parts, and then $N(H_{i_1}, \ldots, H_{i_k}) = t^{n - kr + p}$ (all the subgraphs in each of the $p$ parts receive the same colour, so there $t^p$ independent ways of colouring these $H_i$s monochromatically; then the remaining $n - kr$ vertices can be coloured in $t^{n - kr}$ ways).

Note: I think Fedor Petrov's answer is the simplest one so far, but to my mind, my answer is also intuitively quite simple and occurred to me immediately because I have thought about the usual graph colouring problem along the same lines before. But writing down the formal argument does take time.

Suppose $G$ has order [number of vertices] $n$, and contains $m$ copies of $H$ as subgraphs (in the special case $H = K_2$, $m$ will be the size of $G$), and label them $H_1, H_2, \ldots, H_m$. (Some of them may share common vertices, which is not an issue). Let $r$ be the order of $H$.

Fix $t$, the number of colours available.

Let $N(H_i)$ be the number of colourings of $G$ in which $H_i$ is monochromatic. More generally, let $N(H_{i_1}, \ldots, H_{i_k})$ be the number of colourings in which each of $H_{i_1}, \ldots, H_{i_k}$ is monochromatic (not necessarily of the same colour). This will always be a power of $t$, and the power depends only on the structure of $G$ and $H$ (not on the value of $t$ itself), as shown below.

By the Inclusion-Exclusion Principle, the number of ways of colouring $G$ with $t$ colours such that none of the $H_i$s are monochromatic is \begin{equation*} t^n - \sum_{i} N(H_i) + \sum_{i < j} N(H_i, H_j) - \cdots + (-1)^k \sum_{i_1 < \cdots < i_k} N(H_{i_1}, \ldots, H_{i_k}) + \cdots + (-1)^m N(H_1, \ldots, H_m) \end{equation*}

which is a polynomial in $t$ since each term is a power of $t$ (in terms of $n$ and $r$).

Proof that the powers depend only the graph structure

First, observe that $N(H_i) = t^{n - r + 1}$. That is, as $H_i$ is monochromatic, all its vertices must be assigned any one of the $t$ colours, which can be done in $t$ ways. The remaining $n - r$ vertices of $G$ must each be assigned a colour as well, which can be done in a total of $t^{n - r}$ ways. Thus, there are $t^{n - r + 1}$ colours in total, with $H_i$ monochromatic.

Now, consider $N(H_i, H_j)$. If $H_i$ and $H_j$ have no common vertices, then whatever be the value of $t$, $N(H_i, H_j) = t^{n - 2r + 2}$. If $H_i$ and $H_j$ have at least one common vertex, then both of them must be assigned the same colour, and hence $N(H_i, H_j) = t^{n - 2r + 1}$. Note that the power is independent of $t$ and is determined solely by the graph structure.

Generalising, consider $N(H_{i_1}, \ldots, H_{i_k})$. Again, depending (only) on the distribution of shared vertices among these subgraphs, the set $\{H_{i_1}, \ldots, H_{i_k}\}$ can be partitioned into some $p$ number of parts, and then $N(H_{i_1}, \ldots, H_{i_k}) = t^{n - kr + p}$ (all the subgraphs in each of the $p$ parts receive the same colour, so there $t^p$ independent ways of colouring these $H_i$s monochromatically; then the remaining $n - kr$ vertices can be coloured in $t^{n - kr}$ ways).

Note: I think Fedor Petrov's answer is the simplest one so far, but to my mind, my answer is also intuitively quite simple and occurred to me immediately because I have thought about the usual graph colouring problem along the same lines before. But writing down the formal argument does take time.

Suppose $G$ has order [number of vertices] $n$, and contains $m$ copies of $H$ as subgraphs (in the special case $H = K_2$, $m$ will be the size of $G$), and label them $H_1, H_2, \ldots, H_m$. (Some of them may share common vertices, which is not an issue). Let $r$ be the order of $H$.

Fix $t$, the number of colours available.

Let $N(H_i)$ be the number of colourings of $G$ in which $H_i$ is monochromatic. More generally, let $N(H_{i_1}, \ldots, H_{i_k})$ be the number of colourings in which each of $H_{i_1}, \ldots, H_{i_k}$ is monochromatic (not necessarily of the same colour). This will always be a power of $t$, and the power depends only on the structure of $G$ and $H$ (not on the value of $t$ itself), as shown below.

By the Inclusion-Exclusion Principle, the number of ways of colouring $G$ with $t$ colours such that none of the $H_i$s is monochromatic is \begin{equation*} P_H(G, t) = t^n - \sum_{i} N(H_i) + \sum_{i < j} N(H_i, H_j) - \cdots + (-1)^k \sum_{i_1 < \cdots < i_k} N(H_{i_1}, \ldots, H_{i_k}) + \cdots + (-1)^m N(H_1, \ldots, H_m) \end{equation*}

which is a polynomial in $t$ since each term is a power of $t$ (in terms of $n$ and $r$).

Proof that the powers depend only the graph structure

First, observe that $N(H_i) = t^{n - r + 1}$. That is, as $H_i$ is monochromatic, all its vertices must be assigned any one of the $t$ colours, which can be done in $t$ ways. The remaining $n - r$ vertices of $G$ must each be assigned a colour as well, which can be done in a total of $t^{n - r}$ ways. Thus, there are $t^{n - r + 1}$ colours in total, with $H_i$ monochromatic.

Now, consider $N(H_i, H_j)$. If $H_i$ and $H_j$ have no common vertices, then whatever be the value of $t$, $N(H_i, H_j) = t^{n - 2r + 2}$. If $H_i$ and $H_j$ have at least one common vertex, then both of them must be assigned the same colour, and hence $N(H_i, H_j) = t^{n - 2r + 1}$. Note that the power is independent of $t$ and is determined solely by the graph structure.

Generalising, consider $N(H_{i_1}, \ldots, H_{i_k})$. Again, depending (only) on the distribution of shared vertices among these subgraphs, the set $\{H_{i_1}, \ldots, H_{i_k}\}$ can be partitioned into some $p$ number of parts, and then $N(H_{i_1}, \ldots, H_{i_k}) = t^{n - kr + p}$ (all the subgraphs in each of the $p$ parts receive the same colour, so there $t^p$ independent ways of colouring these $H_i$s monochromatically; then the remaining $n - kr$ vertices can be coloured in $t^{n - kr}$ ways).

Note: I think Fedor Petrov's answer is the simplest one so far, but to my mind, my answer is also intuitively quite simple and occurred to me immediately because I have thought about the usual graph colouring problem along the same lines before. But writing down the formal argument does take time.

Source Link
M. Vinay
M. Vinay
  • 178
  • 1
  • 1
  • 8

Suppose $G$ has order [number of vertices] $n$, and contains $m$ copies of $H$ as subgraphs (in the special case $H = K_2$, $m$ will be the size of $G$), and label them $H_1, H_2, \ldots, H_m$. (Some of them may share common vertices, which is not an issue). Let $r$ be the order of $H$.

Fix $t$, the number of colours available.

Let $N(H_i)$ be the number of colourings of $G$ in which $H_i$ is monochromatic. More generally, let $N(H_{i_1}, \ldots, H_{i_k})$ be the number of colourings in which each of $H_{i_1}, \ldots, H_{i_k}$ is monochromatic (not necessarily of the same colour). This will always be a power of $t$, and the power depends only on the structure of $G$ and $H$ (not on the value of $t$ itself), as shown below.

By the Inclusion-Exclusion Principle, the number of ways of colouring $G$ with $t$ colours such that none of the $H_i$s are monochromatic is \begin{equation*} t^n - \sum_{i} N(H_i) + \sum_{i < j} N(H_i, H_j) - \cdots + (-1)^k \sum_{i_1 < \cdots < i_k} N(H_{i_1}, \ldots, H_{i_k}) + \cdots + (-1)^m N(H_1, \ldots, H_m) \end{equation*}

which is a polynomial in $t$ since each term is a power of $t$ (in terms of $n$ and $r$).

Proof that the powers depend only the graph structure

First, observe that $N(H_i) = t^{n - r + 1}$. That is, as $H_i$ is monochromatic, all its vertices must be assigned any one of the $t$ colours, which can be done in $t$ ways. The remaining $n - r$ vertices of $G$ must each be assigned a colour as well, which can be done in a total of $t^{n - r}$ ways. Thus, there are $t^{n - r + 1}$ colours in total, with $H_i$ monochromatic.

Now, consider $N(H_i, H_j)$. If $H_i$ and $H_j$ have no common vertices, then whatever be the value of $t$, $N(H_i, H_j) = t^{n - 2r + 2}$. If $H_i$ and $H_j$ have at least one common vertex, then both of them must be assigned the same colour, and hence $N(H_i, H_j) = t^{n - 2r + 1}$. Note that the power is independent of $t$ and is determined solely by the graph structure.

Generalising, consider $N(H_{i_1}, \ldots, H_{i_k})$. Again, depending (only) on the distribution of shared vertices among these subgraphs, the set $\{H_{i_1}, \ldots, H_{i_k}\}$ can be partitioned into some $p$ number of parts, and then $N(H_{i_1}, \ldots, H_{i_k}) = t^{n - kr + p}$ (all the subgraphs in each of the $p$ parts receive the same colour, so there $t^p$ independent ways of colouring these $H_i$s monochromatically; then the remaining $n - kr$ vertices can be coloured in $t^{n - kr}$ ways).

Note: I think Fedor Petrov's answer is the simplest one so far, but to my mind, my answer is also intuitively quite simple and occurred to me immediately because I have thought about the usual graph colouring problem along the same lines before. But writing down the formal argument does take time.