I am looking for combinatorial characterizations of some algebraically defined families of sets, like the well-known Taylor and Zwicker theorem (see, for instance, here) stating that a voting system is weighted iff it is trade robust. In particular, this approach allows us to use SAT solvers to deal with the families satisfying the respective combinatorial conditions.
To formulate a more refined condition, for any vertex $v\in V$ put $V(v)=\{u\in V: vu\in \mathcal S\}$$\mathcal S^2_v=\{u\in V: vu\in \mathcal S\}$. For any distinct vertices $v,v'\in V$ we define an auxiliary graph $H=H(vv')$ with the vertex set $V(v)\cap V(v’)$$\mathcal S^2_v\cap \mathcal S^2_{v'}$ such that two vertices $u$ and $u'$ of $H$ are adjacent in $H$, if $\{v,v',u,u'\}\in\mathcal K$.
My last condition involves linear algebraSince the weight function $w:E\to \mathbb C$ directly determines members of $\mathcal K$ of size $2$, the next step is to describe members of $\mathcal K$ of size $4$. For this purpose, given any vertex $v\in V$ put $$\mathcal K^4_v=\{U\subset V\setminus\{v\}: |U|=3 \mbox{ and } \{v\}\cup U\in\mathcal K\}.$$
ForWe need some linear algebra for the next condition. For each settriple $F\subset E$$T\subset V$, $T=\{u,u',u''\}$, let $\overline{F}$$\widetilde T$ be its characteristic function, that an element ofa vector with the linear spaceentries indexed by $\mathbb R^{E}$$E$, such that for any $e\in F$$e\in E$, the $e$-th coordinateentry of $\overline{F}$$\widetilde T$ equals $1$, if $e\in F$$e\in \{uu',uu'',u'u''\}$, and equals $0$, otherwise. For each $v\in V$ let $\widetilde v$ be a vector with the entries indexed by $E$, such that for any $\{u,u'\}\in E$, the $\{u,u'\}$-th entry of $\widetilde v$ equals $\frac{w(uu')}{w(vu)w(vu')}$, if $\{u,u'\}\subset\mathcal S^2_v$, and equals $0$, otherwise. Then for any triple $T\subset \mathcal S^2_v$, $T=\{u,u',u''\}$, we have $\frac{w(\{v,u,u',u''\})}{w(vu)w(vu')w(vu'')}=(\widetilde T, \widetilde v)$. For each family $\mathcal T$ of triples of $V$, let $[\mathcal T]$ be the matrix with the entries indexed by $\mathcal T\times E$, such that for each $T\in\mathcal T$ the $T$-th column of the matrix is $\widetilde T$.
Condition 4. Let $v$ be any vertex of $V$,. Then $u_1,u_2,u_3$ be any distinct vertices$\operatorname{rank}\,[\mathcal K^4_v]<\operatorname{rank}\,[\mathcal T]$ for each subfamily $\mathcal T$ of triples of $V(v)$, and$\mathcal S^2_v$ such that $F=\{u_1u_2,u_1u_3,u_2u_3\}$. Then$\mathcal T$ properly contains $\{v,u_1,u_2,u_3\}\in\mathcal K$ provided there exist$\mathcal K^4_v$.
Proof. Suppose for a natural numbercontradiction that $m$$\operatorname{rank}\,[\mathcal K^4_v]=\operatorname{rank}\,[\mathcal T]$. Pick any triple $S\in\mathcal T\setminus\mathcal K^4_v$, distinct vertices $u_{1i}, u_{2i}, u_{3i}$$S=\{s,s',s''\}$. The equality of the ranks implies that there exist real numbers $V(v)$$\lambda_T, T\in\mathcal T$ such that $\widetilde S=\sum_{T\in\mathcal T}\lambda_T\widetilde T$. Then $$0=\sum_{\{u,u',u''\}\in\mathcal T}\lambda_{\{u,u',u''\}}\frac{w(\{v,u,u',u''\})}{w(vu)w(vu')w(vu'')}= \sum_{T\in\mathcal T}\lambda_{T}(\widetilde T, \widetilde v)=$$ $$\left(\sum_{T\in\mathcal T}\lambda_{T}\widetilde T, \widetilde v\right)=(\widetilde S,\widetilde v)= \frac{w(\{v,s,s',s''\})}{w(vs)w(vs')w(vu'')},$$ so $\{v, u_{1i}, u_{2i}, u_{3i}\}\in\mathcal K$$\{s,s',s''\}\in\mathcal K^4_v,$ a contradiction. $\square$
A special case of conditions is when we provide some even-sized subsets of $V$ to belong to $\mathcal K$, that is when some polylinear forms of the weights $F_i=\{u_{1i}u_{2i},u_{1i}u_{3i},u_{2i}u_{3i}\}$$w(e)$, $e\in E$ are zeroes. When we study the set of solutions of the respective system of equations, we can find that some weights (or other polylinear forms of them) are zeroes, for each positive integerinstance, as in the condition below.
Given a subset $i\le m$$U$ of $V$, let $G_\mathcal S[U]$ be the graph with the vertex set $U$ and real numbersthe edge set consisting of all pairs $\lambda_1,\dots,\lambda_m$$\{v,u\}$ of distinct elements of $U$ such that $\overline{F}=\sum_{i=1}^m \lambda_i\overline{F_i}$$\{v,u\}\in\mathcal S$, that is $w(\{v,u\})\ne 0$.
Condition 5. Let $U$ be a subset of $V$ such that each four-element subset of $U$ belongs to $\mathcal K$. Let $G$ be the graph $G_\mathcal S[U]$ with all isolated vertices removed. If $G$ has at least four vertices then $G$ is isomorphic to one of the following graphs: the star $K_{1,m}$ for some natural $m\ge 3$, the cycle $C_4$, the complete graph $K_4$, the complete graph $K_5$, and the complete graph $K_4$ without an edge.
Proof. For Let $\overline{G}$ be the complement of $G$. Then each positive integercomponent of $i\le m$$\overline{G}$ is a clique, because for any its distinct vertices $v$, $v'$, and $v''$ such that $v'$ is adjacent to $v$ and $v''$ is adjacent to $v'$, we have $v''$ is adjacent to $$0=w(\{v, u_{1i}, u_{2i}, u_{3i}\})=w(vu_{1i})w(u_{2i} u_{3i})+ w(vu_{2i})w(u_{1i} u_{3i})+ w(vu_{3i})w(u_{1i} u_{3i}).$$ Also$v$. To show the latter pick any vertex $$w(\{v,u_1,u_2,u_3\})=w(vu_1)w(u_2u_3)+ w(vu_2)w(u_1u_3)+w(vu_3)w(u_1u_2).$$ The$u$ adjacent in $G$ to its nonisolated vertex $v'$. Thus we have $w(vv')=w(v'v'')=0$ and $w(v'u)\ne 0$. Then the equality $$0=w(\{v,v',v'',u\})=w(vv')w(v''u)+w(vv'')w(v'u)+w(v'v'')w(vu)$$ implies that $\overline{F}=\sum_{i=1}^m \lambda_i\overline{F_i}$ implies$w(vv'')=0$, that $$0=\sum_{i=1}^m \lambda_i\frac{w(\{v, u_{1i}, u_{2i}, u_{3i}\})}{w(vu_{1i})w(vu_{2i})w(vu_{3i})}=$$ is $$\sum_{i=1}^m \lambda_i \left(\frac{w(u_{2i} u_{3i})}{w(vu_{2i})w(vu_{3i})}+\frac{w(u_{1i} u_{3i})}{w(vu_{1i})w(vu_{3i})}+\frac{w(u_{1i} u_{2i})}{w(vu_{1i})w(vu_{2i})}\right)=$$$v$ is adjacent to $$\frac{w(u_{2} u_{3})}{w(vu_{2})w(vu_{3})}+\frac{w(u_{1} u_{3})}{w(vu_{1})w(vu_{3})}+\frac{w(u_{1}u_{2})}{w(vu_{1})w(vu_{2})}=$$$v''$ in $\overline{G}$.
Let $n'$ be the order of $G$. If $n'=4$ then it is easy to check that the graph $G$ is isomorphic to one of the following graphs: the star $K_{1,3}$, the cycle $C_4$, the complete graph $K_4$ without an edge, and the complete graph $K_4$.
Suppose that $n'\ge 5$. No component of $\overline{G}$ consists of two vertices $v$ and $v'$, because otherwise the graph $H(vv')$ is $K_{n'-2}$, which contradicts the second part of Condition 3. On the other hand, by the first part of Condition 3, there is no component of $\overline{G}$ whose order is strictly between $2$ and $n'-1$. Thus either $\overline{G}$ is an empty graph or the edges of $\overline{G}$ form a clique or order $n'-1$. $$\frac{w(\{v,u_1,u_2,u_3\})}{w(vu_{1})w(vu_{2})w(vu_{3})}. \square$$Thus $G$ is either the complete graph or the star.
ThanksMoreover, if $n'\ge 6$ then $G$ is not a complete graph. Indeed, otherwise pick any set $U'$ of five vertices of $G$ and any vertex $v$ of $G$, which is not in $U'$. Then $U'\subset\mathcal S^2_v$. Let $\mathcal T$ be the family of all triples of $U'$. Then for any triple $T\in\mathcal T$, $T=\{u,u',u''\}$, we have $$0=\frac{w(\{v,u,u',u''\})}{w(vu)w(vu')w(vu'')}=(\widetilde T, \widetilde v),$$ so $[\mathcal T]\widetilde v=0$. It can be checked that the matrix $[\mathcal T]$ is nonsingular, so $\widetilde v=0$, a contradiction. $\square$