高级算法 (Fall 2021)/Problem Set 1 and 高级算法 (Fall 2021)/Problem Set 4: Difference between pages
imported>TCSseminar (Created page with "*每道题目的解答都要有<font color="red" size=5>完整的解题过程</font>。中英文不限。 == Problem 1 == == Problem 2 ==") |
imported>TCSseminar |
||
| Line 4: | Line 4: | ||
== Problem 2 == | == Problem 2 == | ||
A ''<math>k</math>-uniform hypergraph'' is an ordered pair <math>G=(V,E)</math>, where <math>V</math> denotes the set of vertices and <math>E</math> denotes the set of edges. Moreover, each edge in <math>E</math> now contains <math>k</math> distinct vertices, instead of <math>2</math> (so a <math>2</math>-uniform hypergraph is just what we normally call a graph). | |||
A hypergraph is <math>k</math>-regular if all vertices have degree <math>k</math>; that is, each vertex is exactly contained within <math>k</math> hypergraph edges. | |||
Show that for sufficiently large <math>k</math>, the vertices of a <math>k</math>-uniform, <math>k</math>-regular hypergraph can be <math>2</math>-colored so that no edge is monochromatic. | |||
What's the smallest value of <math>k</math> you can achieve? | |||
== Problem 3 == | |||
Suppose we have graphs <math>G=(V,E)</math> and <math>H=(V,F)</math> on the same vertex set. | |||
We wish to partition <math>V</math> into clusters <math>V_1,V_2,\cdots</math> so as to maximise: | |||
:<math>(\#\text{ of edges in }E\text{ that lie within clusters})+(\#\text{ of edges in }F\text{ that lie between clusters}).</math> | |||
* Show that the following SDP is an upperbound on this. | |||
:::<math> | |||
\text{maximize} &&& \sum_{(u,v)\in E}\langle x_u,x_v\rangle+\sum_{(u,v)\in F}(1-\langle x_u,x_v\rangle) \\ | |||
\begin{align} | |||
\text{subject to} && \langle x_u,x_u\rangle & =1, & \forall u & \in V, \\ | |||
&& \langle x_u,x_v\rangle & \ge0, & \forall u,v & \in V, \\ | |||
&& x_u & \in R^n, & \forall u & \in V. | |||
\end{align} | |||
</math> | |||
Revision as of 08:10, 20 December 2021
- 每道题目的解答都要有完整的解题过程。中英文不限。
Problem 1
Problem 2
A [math]\displaystyle{ k }[/math]-uniform hypergraph is an ordered pair [math]\displaystyle{ G=(V,E) }[/math], where [math]\displaystyle{ V }[/math] denotes the set of vertices and [math]\displaystyle{ E }[/math] denotes the set of edges. Moreover, each edge in [math]\displaystyle{ E }[/math] now contains [math]\displaystyle{ k }[/math] distinct vertices, instead of [math]\displaystyle{ 2 }[/math] (so a [math]\displaystyle{ 2 }[/math]-uniform hypergraph is just what we normally call a graph). A hypergraph is [math]\displaystyle{ k }[/math]-regular if all vertices have degree [math]\displaystyle{ k }[/math]; that is, each vertex is exactly contained within [math]\displaystyle{ k }[/math] hypergraph edges.
Show that for sufficiently large [math]\displaystyle{ k }[/math], the vertices of a [math]\displaystyle{ k }[/math]-uniform, [math]\displaystyle{ k }[/math]-regular hypergraph can be [math]\displaystyle{ 2 }[/math]-colored so that no edge is monochromatic. What's the smallest value of [math]\displaystyle{ k }[/math] you can achieve?
Problem 3
Suppose we have graphs [math]\displaystyle{ G=(V,E) }[/math] and [math]\displaystyle{ H=(V,F) }[/math] on the same vertex set. We wish to partition [math]\displaystyle{ V }[/math] into clusters [math]\displaystyle{ V_1,V_2,\cdots }[/math] so as to maximise:
- [math]\displaystyle{ (\#\text{ of edges in }E\text{ that lie within clusters})+(\#\text{ of edges in }F\text{ that lie between clusters}). }[/math]
- Show that the following SDP is an upperbound on this.
- [math]\displaystyle{ \text{maximize} &&& \sum_{(u,v)\in E}\langle x_u,x_v\rangle+\sum_{(u,v)\in F}(1-\langle x_u,x_v\rangle) \\ \begin{align} \text{subject to} && \langle x_u,x_u\rangle & =1, & \forall u & \in V, \\ && \langle x_u,x_v\rangle & \ge0, & \forall u,v & \in V, \\ && x_u & \in R^n, & \forall u & \in V. \end{align} }[/math]