1
$\begingroup$

I have written this graph-theoretic proof about certain symmetric $k$-partite graphs, and a way to filter their edges so that all maximal cliques in the graph remain size $k$. The reason why I am not confident the proof is right is because it is a strong implication that $P=NP$ by way of $SAT$'s reduction to the clique problem. I can't find any errors in the proof, but the implication seems too strong for the proof to be correct so I'd appreciate any help pointing out a problem I may have missed. I've tried to use standard terminology as much as possible, but anything I've created is bold and italicized, so please let me know if there is a better term or definition out there

Definition: Given some graph $G$, $V(G)$ is its set of vertices and $E(G)$ is its set of edges. A vertex is an element $v \in V(G)$ and an edge is an element $vw \in E(G)$ with adjacent endpoints $v, w \in V(G)$. Two graphs $G$ and $H$ are called isomorphic if there is a bijection $f: V(G) \rightarrow V(H)$ such that any $vw \in E(G)$ implies $f(v)f(w) \in E(H)$, and are called non-isomorphic otherwise
Definition: A $k$-clique $\Delta$k is a graph on $k$ vertices where all vertices are pairwise adjacent. A clique which is not a proper subset of any other is called maximal
Definition: A $k$-partite graph $G$ is a graph whose vertex set has been partitioned into $k$ independent sets. An independent set is a set of vertices which are all pairwise non-adjacent. If $G$ is complete, then vertices are pairwise adjacent between all partitions. The restoration of $G$ is the set of edges needed to make $G$ complete under this definition. The complete $k$-partite graph formed by adding the restoration to $E(G)$ is defined as $*(G)$
Definition: The clique complex of a graph $G$ is the abstract simplicial complex whose faces are the vertex set of each clique in $G$. A face which is not a proper subset of any other face is called a facet. The dimension of a face $X$ is defined as $|X|-1$. The dimension of the clique complex is equal to the dimension of the largest face. A clique complex is said to be pure if each facet is the same dimension

Theorem 1: If $G$ is a $k$-partite graph with no edges and $\Gamma$k is some subset of all the possible $\Delta$k in $G$, then adding the edge set of each $\Delta$k$ \in \Gamma$k to $G$ will result in a graph which has a pure clique complex of dimension $k-1$

Proof: Assume that $\Delta$m is some maximal clique in $G$ where $m<k$. We know that each vertex in $V(\Delta$m$)$ belongs to at least one $\Delta$k$ \in \Gamma$k. However, since the vertex set can't be a subset due to the clique being maximal, they can't all belong to the same $\Delta$k. If we have some vertex $v \in V(\Delta$m$)$ and $v \notin V(\Delta$k$)$, we know that $v \in V(\Delta$k*$)$ for some $\Delta$k*$ \in \Gamma$k which is non-isomorphic to $\Delta$k. Since we know that $\{vw~|~w \in V(\Delta$k$)\} \subset E(\Delta$k*$)$, the definition of a clique tells us that those vertices $w \in V(\Delta$k$)$ which are connected to $v$ are all in $V(\Delta$k*$)$ as well. This means that $V(\Delta$m$) \subset V(\Delta$k*$)$, therefore it is not a maximal clique and we have arrived at a contradiction. Since no edges will be added between any of the vertices within a partition, we will have no cliques with more than $k$ vertices due to the Pigeon Hole Principle. Therefore, all maximal cliques must have exactly $k$ vertices and $G$ has a pure clique complex of dimension $k-1$

Definition: Given a graph $G$ and a subset of its edges $T \subset E(G)$, a subgraph on $T$ is a new graph whose edges are the set $T$
Definition: Given a graph $G$ and a subset of its vertices $S \subset V(G)$, an induced subgraph on $S$ is a subgraph of $G$ formed by the set of all edges $T \subset E(G)$ whose endpoints are both in $S$
Definition: Given a $k$-partite graph $G$, if for every $\Delta$m in $G$ where $1<m<k$, there exists a vertex $v$ such that the induced subgraph of $G$ on $V(\Delta$m$) \cup \{v\}$ forms a $\Delta$m+1, then $G$ is said to have the clique extension property

Theorem 2: If $G$ is a $k$-partite graph with a pure clique complex of dimension $k-1$, then $G$ has the clique extension property

Proof: If we have a $\Delta$m in $G$, where $1<m<k$, then by the definition of a pure clique complex, $\Delta$m is not a maximal clique as its vertex set does not form a face of dimension $k-1$. Since $\Delta$m is not a maximal clique, it must be a subset of a larger one. Therefore, there must be some vertex $v \notin V(\Delta$m$)$ such that the induced subgraph of $G$ on
$V(\Delta$m$) \cup \{v\}$ forms a $\Delta$m+1

Definition: Given a graph $G$ and its clique complex, as well as two edges $vw, xy \in E(G)$, the edge $vw$ is said to cover $xy$ if every facet containing $\{x, y\}$ also contains $\{v, w\}$. The coverage of an edge is the set of all edges which $vw$ covers
Definition: Given a graph $G$, the neighborhood of a vertex $v \in V(G)$, or $N(v)$, is the set of all vertices adjacent to $v$. The neighborhood of a clique, or $N(\Delta$m$)$, is the intersection of the neighborhoods of each vertex in $V(\Delta$m$)$. The use of square brackets means that the vertices used to define the neighborhood are included in the neighborhood or $N[v] = \{v\} \cup N(v)$
Definition: Given a $k$-partite graph $G$ with a pure clique complex of dimension $k-1$, the tangential of some clique, or $\tau(\Delta$m$)$, is defined as the set of edges in the induced subgraph of $G$ on $N[\Delta$m$]$

Theorem 3: If $G$ is a $k$-partite graph with a pure clique complex of dimension $k-1$ and $vw \in E(G)$, then $\tau(vw)$ is precisely the union of the edge set of each $\Delta$k which contains $vw$

Proof: From the definition of a clique, $V(\Delta$k$) \subset N[vw]$ if it contains some edge $vw$. Following this, the set of potential edges of any such maximal clique can be partitioned into three sets, $\{vw\}$, $\{vx, wx~|~x \in N(vw)\}$,
and $\{xy~|~x, y \in N(vw)\}$. The first partition is the edge which we are using to define the tangential. This is where we get the term tangential from, as all of the maximal cliques represented by the edge set will be "tangent" to this edge. The second partition is the set of all edges connecting $vw$ to any one of its neighbors $x$. We know every edge in this set is a part of some $\Delta$3 formed by the edges $\{vw, vx, wx\}$. Since $G$ has the clique extension property according to theorem 2, each $\Delta$3 can be extended to some $\Delta$$k$, meaning every edge between $vw$ and its neighbors will be in a maximal clique. The third partition is the set of edges which connect any two vertices $x, y \in N(vw)$. If $xy$ exists, we know that $\{vx, wx, vy, wy\} \subset E(G)$ from our definition of the neighborhood of a clique. Therefore, we also know that we can create a $\Delta$$4$ such that $E(\Delta$4$) = \{vw, vx, wx, vy, wy, xy\}$. If $\Delta$$4$ is not already maximal, we can again use theorem 2 to guarantee the clique can be extended to some $\Delta$$k$. Therefore, if $xy$ exists, it will be in a maximal clique. Taken together, the edge set of all maximal cliques which contain $vw$ is precisely all of the edges with both endpoints in $N[vw]$, or the induced subgraph of $G$ on $N[vw]$

Theorem 4: If $G$ is a $k$-partite graph with a pure clique complex of dimension $k-1$, for two edges $vw, xy \in E(G)$, if $vw$ covers $xy$ then $\tau(xy) \subset \tau(vw)$

Proof: According to theorem 3, the set of edges in $\tau(vw)$ are each part of some maximal clique containing $vw$. Therefore, for two edges $vw, xy \in E(G)$, if $\tau(xy) \subset \tau(vw)$, there are no maximal cliques that $xy$ is a part of that $vx$ isn't also a part of and $vw$ covers $xy$ according to our definition. We can also say $\tau(xy)$ represents the edge set of maximal cliques which happen to be tangent to both $vw$ and $xy$

Definition: Given a $k$-partite graph $G$ with a pure clique complex of dimension $k-1$ and an edge $vw \in E(G)$, a facet reduction, or $Red(G, vw)$ is the subgraph $H$ formed from $G$ by removing the edge $vw$ and each edge in its coverage. A facet reduction is also known as reducing $G$ by $vw$

Theorem 5: If $G$ is a $k$-partite graph with a pure clique complex of dimension $k-1$ and $H=Red(G, vw)$, then $H$ is either an independent set or it is a $k$-partite graph with a pure clique complex of dimension $k-1$ containing all of the $\Delta$k in $G$ which do not contain $vw$

Proof: Removing the edge $vw$ removes all $\Delta$k which contain $vw$. If we have some edge $xy$ covered by $vw$, then $xy$ can't be in any remaining $\Delta$k. Therefore, for any maximal clique $\Delta$m which contains $xy$, $m < k$. However, by removing $vw$ and its coverage, any remaining edge is contained in some $\Delta$k which does not contain $vw$. Alternatively, $H$ is formed from the edge set of all $\Delta$k in $G$ which did contain $vw$. Therefore, according to theorem 1, if $E(H) \neq \emptyset$, then $H$ has a pure clique complex of dimension $k-1$. If there are no $\Delta$k without $vw$, then $H$ is an independent set as no edges will remain

Theorem 6: If $G$ is a $k$-partite graph and $R$ is its restoration, then there is some induced $\Delta$k in $G$ if and only if $*(G)$ is not reduced to an independent set after being subjected to the facet reduction with each edge in $R$

Proof: If any $\Delta$k exists in $G$, then $E(\Delta$k$) \subset E(G)$, and as such, cannot contain any edge in $R$. Since $*(G)$ is $k$-partite and formed from the set of all possible $\Delta$k in $G$, it has a pure clique complex of dimension $k-1$ according to
theorem 1. Using theorem 5, reducing $*(G)$ by any $vw \in R$ will either produce another $k$-partite graph with a pure clique complex of dimension $k-1$ or it will produce an independent set. In the first case, we know that the new graph has no $\Delta$k which contain $vw$, but it does contain some other $\Delta$k. To find it, start with any $\Delta$2, add a vertex from its intersection to find a larger clique, then repeat until you have $k$ vertices. Since the new graph still has the clique extension property, we'll always end up with some $\Delta$k with the added property that it does not contain $vw$. Since the new graph also satisfies the conditions needed to perform a facet reduction, we can reduce it again by any remaining edges in $R$. If we reduce the graph by each of the edges in the restoration and it still has a non-empty edge set, then we know that $G$ contains some $\Delta$k which is able to be constructed from $E(G)$. Otherwise, at some point we reduce the graph to an independent set and we can determine that there are no $\Delta$k which can be formed using the edge set of $G$

$\endgroup$

1 Answer 1

0
$\begingroup$

So the errors in the proof are theorem 1 and theorem 5 and 6

Theorem 1 can be shown to be wrong through a counterexample. Take the 4-partite graph where the 4 blocks in the vertex partition are [1, 2, 3], [4, 5, 6], [7, 8, 9], and [10, 11, 12]. If we add the edge set for the $\Delta_4$ with vertices {1, 4, 8, 10}, {1, 5, 7, 11}, and {2, 4, 7, 12}, we get a maximal $\Delta_3$ with vertex set {1, 4, 7}

Theorem 5 is wrong because now it's not guaranteed that the subgraph we create will have a pure clique complex and theorem 6 is wrong because it relies on theorem 5

If we do have a $k$-partite graph with a pure clique complex of dimension $k-1$, theorems 2, 3, and 4 still stand. If we only use two cliques from the above counterexample, we have an example of such a graph

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.