Return to Question

Let $d \gg 1$. Let $G:=(U, V, E)$ be some bipartite graph such that deg$(u) \le d$ for all $u\in U$ and deg$(v) \le 3$ for all $v \in V$.

Now, is it possible to color vertices in $U$ with 3 colors such that firstly, size of each color class is roughly $|U|/3$ and secondly, at most a fraction $\beta$ of vertices in $V$ have neighbours from all the 3 color classes?

Specially interesting is the case $d \sim 20000$, and $\beta \ll 1 /3$.

Motivation The motivation is from computational complexity. I am trying to simplify the proof or improve Thm. 5.1 of [1]. For d=3 (this is not our $d$), in the first paragraph you make instances of 3-SAT with $n$ variables, where each variable appears in at most 20000 clauses. So there are at most 7400 clauses with 3 variables.

Now, let $U$ be the set of variables, and $V$ be the set of clauses, and there be an edge between $u\in U$ and $v \in V$ iff $u \in v$.

If I have the desired coloring, then the second paragraph and its overhead can (by a trick) be avoided.

In the third paragraph each color class corresponds to a block of variables. Therefore, the size of each color class should be roughly $n/3$.

On the other hand, for each clause that has neighbours from all the color classes, (applying another trick) one variable should appear in two blocks, increasing the size of blocks by at most $\beta n$. Therefore we need $\beta \ll 1 /3$.

[1] M. Patrascu and R. Williams. On the Possibility of Faster SAT Algorithms. In SODA, pages 1065–1075, 2010.

Let $d \gg 1$. Let $G:=(U, V, E)$ be some bipartite graph such that deg$(u) \le d$ for all $u\in U$ and deg$(v) \le 3$ for all $v \in V$.

Now, is it possible to color vertices in $U$ with 3 colors such that firstly, size of each color class is roughly $|U|/3$ and secondly, at most a fraction $\beta$ of vertices in $V$ have neighbours from all the 3 color classes?

Specially interesting is the case $d \sim 20000$, and $\beta \ll 1 /3$.

Motivation The motivation is from computational complexity. I am trying to simplify the proof or improve Thm. 5.1 of [1]. For d=3 (this is not our $d$), in the first paragraph you make instances of 3-SAT with $n$ variables, where each variable appears in at most 20000 clauses. So there are at most $20000/3$ clauses with 3 variables.

Now, let $U$ be the set of variables, and $V$ be the set of clauses, and there be an edge between $u\in U$ and $v \in V$ iff $u \in v$.

If I have the desired coloring, then the second paragraph and its overhead can (by a trick) be avoided.

In the third paragraph each color class corresponds to a block of variables. Therefore, the size of each color class should be roughly $n/3$.

On the other hand, for each clause that has neighbours from all the color classes, (applying another trick) one variable should appear in two blocks, increasing the size of blocks by at most $\beta n$. Therefore we need $\beta \ll 1 /3$.

[1] M. Patrascu and R. Williams. On the Possibility of Faster SAT Algorithms. In SODA, pages 1065–1075, 2010.

Let $G:=(U, V, E)$ be a bipartite graph such that deg$(u) \le d$ for all $u\in U$ and deg$(v) \le 3$ for all $v \in V$.

Now, is it possible to color vertices in $U$ with 3 colors such that firstly, size of each color class is roughly $|U|/3$ and secondly, at most a fraction $\beta$ of vertices in $V$ have neighbours from all the 3 color classes?

Specially interesting is the case $d \sim 20000$, and $\beta \ll 1 /3$.

Motivation The motivation is from computational complexity. I am trying to simplify the proof or improve Thm. 5.1 of [1]. For d=3 (this is not our $d$), in the first paragraph you make instances of 3-SAT with $n$ variables, where each variable appears in at most 20000 clauses. So there are at most 7400 clauses with 3 variables.

Now, let $U$ be the set of variables, and $V$ be the set of clauses, and there be an edge between $u\in U$ and $v \in V$ iff $u \in v$.

If I have the desired coloring, then the second paragraph and its overhead can (by a trick) be avoided.

In the third paragraph each color class corresponds to a block of variables. Therefore, the size of each color class should be roughly $n/3$.

On the other hand, for each clause that has neighbours from all the color classes, (applying another trick) one variable should appear in two blocks, increasing the size of blocks by at most $\beta n$. Therefore we need $\beta \ll 1 /3$.

[1] M. Patrascu and R. Williams. On the Possibility of Faster SAT Algorithms. In SODA, pages 1065–1075, 2010.

Let $d \gg 1$. Let $G:=(U, V, E)$ be some bipartite graph such that deg$(u) \le d$ for all $u\in U$ and deg$(v) \le 3$ for all $v \in V$.

Now, is it possible to color vertices in $U$ with 3 colors such that firstly, size of each color class is roughly $|U|/3$ and secondly, at most a fraction $\beta$ of vertices in $V$ have neighbours from all the 3 color classes?

Specially interesting is the case $d \sim 20000$, and $\beta \ll 1 /3$.

Motivation The motivation is from computational complexity. I am trying to simplify the proof or improve Thm. 5.1 of [1]. For d=3 (this is not our $d$), in the first paragraph you make instances of 3-SAT with $n$ variables, where each variable appears in at most 20000 clauses. So there are at most 7400 clauses with 3 variables.

Now, let $U$ be the set of variables, and $V$ be the set of clauses, and there be an edge between $u\in U$ and $v \in V$ iff $u \in v$.

If I have the desired coloring, then the second paragraph and its overhead can (by a trick) be avoided.

In the third paragraph each color class corresponds to a block of variables. Therefore, the size of each color class should be roughly $n/3$.

On the other hand, for each clause that has neighbours from all the color classes, (applying another trick) one variable should appear in two blocks, increasing the size of blocks by at most $\beta n$. Therefore we need $\beta \ll 1 /3$.

[1] M. Patrascu and R. Williams. On the Possibility of Faster SAT Algorithms. In SODA, pages 1065–1075, 2010.