Skip to main content
typo
Source Link
Fiktor
  • 1.3k
  • 8
  • 22

I don't know the answer, just some thoughts.

Suppose you have $n$ vertices of the first type and $l$ of the second. Of course, you know the answer if there is no restriction on the number of edges (you want it to be odd). Therefore equivalently I can calculate cases, when it is odd with coefficient (-1) and cases, when it is even with coefficient 1 (I denote this amount by $N$). Let $y_1,\dots,y_n,z_1,\dots,z_l$ be elements of $\mathbb{Z}\_2=\mathbb{Z}/(2\mathbb{Z})$, corresponding to the vertices of the graph. Edges are given by $n\times l$ matrix $A$. Then $N$ is the coefficient of $h^m$ in $S(h,h)$, where $S$ is defined by $$S(h,g)=\sum_{y\in\mathbb{Z}\_2^n,\;z\in\mathbb{Z}\_2^l} h^{|y|} g^{|z|} (-1)^{\sum_{i,j}y_i A_{ij} z_j}.\tag{1}$$ Here $|y|$ is amount of components in $y\in \mathbb{Z}\_2^n$ which are equal to $1$. One can get rid of the sum over $y\in\mathbb{Z}\_2^n$ in the following way: $$S(h,g)=\sum_{z\in\mathbb{Z}\_2^l} g^{|z|}\prod_{i=1}^{n} (1+h(-1)^{\sum_j A_{ij} z_j}).\tag{2}$$ This for example solves the problem in two cases:

  1. we fix the number of vertices only in one part of a bipartite graph and the map $\mathbb{Z}_2^l\to\mathbb{Z}_2^n\colon z\mapsto x$ with $x_i=\sum_j A_{ij} z_j$ is surjective (in this case we can omit $g^{|z|}$ in $(2)$, make described change of coordinates and apply again the trick we used to get (2) from (1));
  2. amount of vertices in one part of a bipartite graph is small enough (in this case the sum (2) has small enough number of terms and each of them can be calculated in a polynomial time);

I don't know the answer, just some thoughts.

Suppose you have $n$ vertices of the first type and $l$ of the second. Of course, you know the answer if there is no restriction on the number of edges (you want it to be odd). Therefore equivalently I can calculate cases, when it is odd with coefficient (-1) and cases, when it is even with coefficient 1 (I denote this amount by $N$). Let $y_1,\dots,y_n,z_1,\dots,z_l$ be elements of $\mathbb{Z}\_2=\mathbb{Z}/(2\mathbb{Z})$, corresponding to the vertices of the graph. Edges are given by $n\times l$ matrix $A$. Then $N$ is the coefficient of $h^m$ in $S(h,h)$, where $S$ is defined by $$S(h,g)=\sum_{y\in\mathbb{Z}\_2^n,\;z\in\mathbb{Z}\_2^l} h^{|y|} g^{|z|} (-1)^{\sum_{i,j}y_i A_{ij} z_j}.\tag{1}$$ Here $|y|$ is amount of components in $y\in \mathbb{Z}\_2^n$ which are equal to $1$. One can get rid of the sum over $y\in\mathbb{Z}\_2^n$ in the following way: $$S(h,g)=\sum_{z\in\mathbb{Z}\_2^l} g^{|z|}\prod_{i=1}^{n} (1+h(-1)^{\sum_j A_{ij} z_j}).\tag{2}$$ This for example solves the problem in two cases:

  1. we fix the number of vertices only in one part of a bipartite graph and the map $\mathbb{Z}_2^l\to\mathbb{Z}_2^n\colon z\mapsto x$ with $x_i=\sum_j A_{ij} z_j$ is surjective (in this case we can omit $g^{|z|}$ in $(2)$, make described change of coordinates and apply again the trick we used to get (2) from (1));
  2. amount of vertices in one part of a bipartite graph is small enough (in this case the sum (2) has small enough number of terms and each of them can be calculated in polynomial time);

I don't know the answer, just some thoughts.

Suppose you have $n$ vertices of the first type and $l$ of the second. Of course, you know the answer if there is no restriction on the number of edges (you want it to be odd). Therefore equivalently I can calculate cases, when it is odd with coefficient (-1) and cases, when it is even with coefficient 1 (I denote this amount by $N$). Let $y_1,\dots,y_n,z_1,\dots,z_l$ be elements of $\mathbb{Z}\_2=\mathbb{Z}/(2\mathbb{Z})$, corresponding to the vertices of the graph. Edges are given by $n\times l$ matrix $A$. Then $N$ is the coefficient of $h^m$ in $S(h,h)$, where $S$ is defined by $$S(h,g)=\sum_{y\in\mathbb{Z}\_2^n,\;z\in\mathbb{Z}\_2^l} h^{|y|} g^{|z|} (-1)^{\sum_{i,j}y_i A_{ij} z_j}.\tag{1}$$ Here $|y|$ is amount of components in $y\in \mathbb{Z}\_2^n$ which are equal to $1$. One can get rid of the sum over $y\in\mathbb{Z}\_2^n$ in the following way: $$S(h,g)=\sum_{z\in\mathbb{Z}\_2^l} g^{|z|}\prod_{i=1}^{n} (1+h(-1)^{\sum_j A_{ij} z_j}).\tag{2}$$ This for example solves the problem in two cases:

  1. we fix the number of vertices only in one part of a bipartite graph and the map $\mathbb{Z}_2^l\to\mathbb{Z}_2^n\colon z\mapsto x$ with $x_i=\sum_j A_{ij} z_j$ is surjective (in this case we can omit $g^{|z|}$ in $(2)$, make described change of coordinates and apply again the trick we used to get (2) from (1));
  2. amount of vertices in one part of a bipartite graph is small enough (in this case the sum (2) has small enough number of terms and each of them can be calculated in a polynomial time);
Improving notation
Source Link
Fiktor
  • 1.3k
  • 8
  • 22

I don't know the answer, just some thoughts.

Suppose you have $n$ vertices of the first type and $l$ of the second. Of course, you know the answer if there is no restriction on the number of edges (you want it to be odd). Therefore equivalently I can calculate cases, when it is odd with coefficient (-1) and cases, when it is even with coefficient 1 (I denote this amount by $N$). Let $y_1,\dots,y_n,z_1,\dots,z_l$ be elements of $\mathbb{Z}\_2=\mathbb{Z}/(2\mathbb{Z})$, corresponding to the vertices of the graph. Edges are given by $n\times l$ matrix $A$. Then $N$ is the coefficient of $h^m$ in $S(h,h)$, where $S$ is defined by $$S(h,g)=\sum_{y\in\mathbb{Z}\_2^n,\;z\in\mathbb{Z}\_2^l} h^{\sum_i y_i} g^{\sum_j z_j} (-1)^{\sum_{i,j}y_i A_{ij} z_j}.\tag{1}$$$$S(h,g)=\sum_{y\in\mathbb{Z}\_2^n,\;z\in\mathbb{Z}\_2^l} h^{|y|} g^{|z|} (-1)^{\sum_{i,j}y_i A_{ij} z_j}.\tag{1}$$ OneHere $|y|$ is amount of components in $y\in \mathbb{Z}\_2^n$ which are equal to $1$. One can get rid of the sum over $y\in\{0,1\}^n$$y\in\mathbb{Z}\_2^n$ in the following way: $$S(h,g)=\sum_{z\in\mathbb{Z}\_2^l} g^{\sum_j z_j}\prod_{i=1}^{n} (1+h(-1)^{\sum_j A_{ij} z_j}).\tag{2}$$$$S(h,g)=\sum_{z\in\mathbb{Z}\_2^l} g^{|z|}\prod_{i=1}^{n} (1+h(-1)^{\sum_j A_{ij} z_j}).\tag{2}$$ This for example solves the problem in two cases:

  1. we fix the number of vertices only in one part of a bipartite graph and the map $\mathbb{Z}_2^l\to\mathbb{Z}_2^n\colon z\mapsto x$ with $x_i=\sum_j A_{ij} z_j$ is surjective (in this case we can omit $g^{\sum_j z_j}$$g^{|z|}$ in $(2)$, make described change of coordinates and apply again the trick we used to get (2) from (1));
  2. amount of vertices in one part of a bipartite graph is small enough (in this case the sum (2) has small enough number of terms and each of them can be calculated in polynomial time);

I don't know the answer, just some thoughts.

Suppose you have $n$ vertices of the first type and $l$ of the second. Of course, you know the answer if there is no restriction on the number of edges (you want it to be odd). Therefore equivalently I can calculate cases, when it is odd with coefficient (-1) and cases, when it is even with coefficient 1 (I denote this amount by $N$). Let $y_1,\dots,y_n,z_1,\dots,z_l$ be elements of $\mathbb{Z}\_2=\mathbb{Z}/(2\mathbb{Z})$, corresponding to the vertices of the graph. Edges are given by $n\times l$ matrix $A$. Then $N$ is the coefficient of $h^m$ in $S(h,h)$, where $S$ is defined by $$S(h,g)=\sum_{y\in\mathbb{Z}\_2^n,\;z\in\mathbb{Z}\_2^l} h^{\sum_i y_i} g^{\sum_j z_j} (-1)^{\sum_{i,j}y_i A_{ij} z_j}.\tag{1}$$ One can get rid of the sum over $y\in\{0,1\}^n$ in the following way: $$S(h,g)=\sum_{z\in\mathbb{Z}\_2^l} g^{\sum_j z_j}\prod_{i=1}^{n} (1+h(-1)^{\sum_j A_{ij} z_j}).\tag{2}$$ This for example solves the problem in two cases:

  1. we fix the number of vertices only in one part of a bipartite graph and the map $\mathbb{Z}_2^l\to\mathbb{Z}_2^n\colon z\mapsto x$ with $x_i=\sum_j A_{ij} z_j$ is surjective (in this case we can omit $g^{\sum_j z_j}$ in $(2)$, make described change of coordinates and apply again the trick we used to get (2) from (1));
  2. amount of vertices in one part of a bipartite graph is small enough (in this case the sum (2) has small enough number of terms and each of them can be calculated in polynomial time);

I don't know the answer, just some thoughts.

Suppose you have $n$ vertices of the first type and $l$ of the second. Of course, you know the answer if there is no restriction on the number of edges (you want it to be odd). Therefore equivalently I can calculate cases, when it is odd with coefficient (-1) and cases, when it is even with coefficient 1 (I denote this amount by $N$). Let $y_1,\dots,y_n,z_1,\dots,z_l$ be elements of $\mathbb{Z}\_2=\mathbb{Z}/(2\mathbb{Z})$, corresponding to the vertices of the graph. Edges are given by $n\times l$ matrix $A$. Then $N$ is the coefficient of $h^m$ in $S(h,h)$, where $S$ is defined by $$S(h,g)=\sum_{y\in\mathbb{Z}\_2^n,\;z\in\mathbb{Z}\_2^l} h^{|y|} g^{|z|} (-1)^{\sum_{i,j}y_i A_{ij} z_j}.\tag{1}$$ Here $|y|$ is amount of components in $y\in \mathbb{Z}\_2^n$ which are equal to $1$. One can get rid of the sum over $y\in\mathbb{Z}\_2^n$ in the following way: $$S(h,g)=\sum_{z\in\mathbb{Z}\_2^l} g^{|z|}\prod_{i=1}^{n} (1+h(-1)^{\sum_j A_{ij} z_j}).\tag{2}$$ This for example solves the problem in two cases:

  1. we fix the number of vertices only in one part of a bipartite graph and the map $\mathbb{Z}_2^l\to\mathbb{Z}_2^n\colon z\mapsto x$ with $x_i=\sum_j A_{ij} z_j$ is surjective (in this case we can omit $g^{|z|}$ in $(2)$, make described change of coordinates and apply again the trick we used to get (2) from (1));
  2. amount of vertices in one part of a bipartite graph is small enough (in this case the sum (2) has small enough number of terms and each of them can be calculated in polynomial time);
Source Link
Fiktor
  • 1.3k
  • 8
  • 22

I don't know the answer, just some thoughts.

Suppose you have $n$ vertices of the first type and $l$ of the second. Of course, you know the answer if there is no restriction on the number of edges (you want it to be odd). Therefore equivalently I can calculate cases, when it is odd with coefficient (-1) and cases, when it is even with coefficient 1 (I denote this amount by $N$). Let $y_1,\dots,y_n,z_1,\dots,z_l$ be elements of $\mathbb{Z}\_2=\mathbb{Z}/(2\mathbb{Z})$, corresponding to the vertices of the graph. Edges are given by $n\times l$ matrix $A$. Then $N$ is the coefficient of $h^m$ in $S(h,h)$, where $S$ is defined by $$S(h,g)=\sum_{y\in\mathbb{Z}\_2^n,\;z\in\mathbb{Z}\_2^l} h^{\sum_i y_i} g^{\sum_j z_j} (-1)^{\sum_{i,j}y_i A_{ij} z_j}.\tag{1}$$ One can get rid of the sum over $y\in\{0,1\}^n$ in the following way: $$S(h,g)=\sum_{z\in\mathbb{Z}\_2^l} g^{\sum_j z_j}\prod_{i=1}^{n} (1+h(-1)^{\sum_j A_{ij} z_j}).\tag{2}$$ This for example solves the problem in two cases:

  1. we fix the number of vertices only in one part of a bipartite graph and the map $\mathbb{Z}_2^l\to\mathbb{Z}_2^n\colon z\mapsto x$ with $x_i=\sum_j A_{ij} z_j$ is surjective (in this case we can omit $g^{\sum_j z_j}$ in $(2)$, make described change of coordinates and apply again the trick we used to get (2) from (1));
  2. amount of vertices in one part of a bipartite graph is small enough (in this case the sum (2) has small enough number of terms and each of them can be calculated in polynomial time);