imported>Etone |
imported>Etone |
Line 1: |
Line 1: |
| == Groups == | | == Problem 1== |
| A group <math>(G,\cdot)</math> is set <math>G</math> along with a binary operator <math>\cdot</math> which satisfies the following axioms:
| |
| * closure: <math>\forall g,h\in G, g\cdot h \in G</math>;
| |
| * associativity: <math>\forall f,g,h\in G, f\cdot(g\cdot h)=(f\cdot g)\cdot h</math>;
| |
| * identity: there exists a special element <math>e\in G</math>, called the '''identity''', such that <math>e\cdot g=g</math> for any <math>g\in G</math>;
| |
| * inverse: <math>\forall g\in G</math>, there exists an <math>h\in G</math> such that <math>g\cdot h=e</math>, and we denote that <math>h=g^{-1}</math>.
| |
|
| |
|
| === Permutation groups=== | | ==Problem 2== |
| | 一个图 <math>G(V,E)</math> 的切 (cut) 是一个边集 <math>C\subseteq E</math>,使得去掉这些边之后 <math>G</math> 不再连通。 |
|
| |
|
| ==== Cycle decomposition ====
| | 证明:任意一个有 <math>m</math> 条边的无向图都存在一个大小为 <math>\frac{m}{2}</math> 的切。 |
|
| |
|
| === Group action === | | ==Problem 3 == |
| {{Theorem|Definition (group action)|
| | 令 <math>\mathcal{F}\subseteq{[n]\choose k}</math> 为一个 <math>k</math>-regular family,即 <math>\forall i\in[n]</math>,刚好有 <math>k</math> 个不同的 <math>S\in\mathcal{F}</math> 满足 <math>i\in S</math>。 |
| :A '''group action''' of a group <math>G</math> on a set <math>X</math> is a binary operator:
| |
| ::<math>\circ:G\times X\rightarrow X</math>
| |
| :satisfying:
| |
| :* Associativity: <math>(g\cdot h)\circ x=g\circ (h\circ x)</math> for all <math>g,h\in G</math> and <math>x\in X</math>;
| |
| :* Identity: <math>e\circ x=x</math> for all <math>x\in X</math>.
| |
| }}
| |
|
| |
|
| == Burnside's Lemma ==
| | 假设 <math>k\ge 10</math>。证明:存在一个对 <math>[n]</math> 的 2着色 <math>f:[n]\rightarrow\{0,1\}</math> 使得 <math>\mathcal{F}</math> 中不存在单色的集合 <math>S\in\mathcal{F}</math>。 |
| | |
| === Orbits ===
| |
| | |
| === Counting orbits===
| |
| {{Theorem|Burnside's Lemma|
| |
| :Let <math>G</math> be a permutation group acting on a set <math>X</math>. For each <math>\pi\in G</math>, let <math>X_\pi=\{x\in X\mid \pi\circ x=x\}</math> be the set of elements invariant under action by <math>\pi</math>. The number of orbits, denoted <math>|X/G|</math>, is
| |
| ::<math>|X/G|=\frac{1}{|G|}\sum_{\pi\in G}|X_{\pi}|.</math> | |
| }}
| |
| {{Proof|
| |
| Let
| |
| :<math>A(\pi,x)=\begin{cases}1 & \pi\circ x=x,\\ 0 & \text{otherwise.}\end{cases}</math>
| |
| Basically <math>A(\pi,x)</math> indicates whether <math>x</math> is invariant under action of <math>\pi</math>. We can think of <math>A</math> as a matrix indexed by <math>G\times X</math>. An important observation is that the row sums and column sums of <math>A</math> are <math>|X_\pi|</math> and <math>|G_x|</math> respectively, namely,
| |
| :<math>|X_\pi|=\sum_{x\in X}A(\pi,x)</math> and <math>|G_x|=\sum_{\pi\in G}A(\pi,x)</math>.
| |
| Then a double counting gives that
| |
| :<math>\sum_{\pi\in G}|X_\pi|=\sum_{\pi\in G}\sum_{x\in X}A(\pi,x)=\sum_{x\in X}\sum_{\pi\in G}A(\pi,x)=\sum_{x\in X}|G_x|</math>.
| |
| | |
| }}
| |
| | |
| ==Pólya's Theory of Counting ==
| |
| === The cycle index ===
| |
| | |
| === Pólya's enumeration formula ===
| |
| | |
| === de Bruijn's generalization===
| |
Problem 1
Problem 2
一个图 [math]\displaystyle{ G(V,E) }[/math] 的切 (cut) 是一个边集 [math]\displaystyle{ C\subseteq E }[/math],使得去掉这些边之后 [math]\displaystyle{ G }[/math] 不再连通。
证明:任意一个有 [math]\displaystyle{ m }[/math] 条边的无向图都存在一个大小为 [math]\displaystyle{ \frac{m}{2} }[/math] 的切。
Problem 3
令 [math]\displaystyle{ \mathcal{F}\subseteq{[n]\choose k} }[/math] 为一个 [math]\displaystyle{ k }[/math]-regular family,即 [math]\displaystyle{ \forall i\in[n] }[/math],刚好有 [math]\displaystyle{ k }[/math] 个不同的 [math]\displaystyle{ S\in\mathcal{F} }[/math] 满足 [math]\displaystyle{ i\in S }[/math]。
假设 [math]\displaystyle{ k\ge 10 }[/math]。证明:存在一个对 [math]\displaystyle{ [n] }[/math] 的 2着色 [math]\displaystyle{ f:[n]\rightarrow\{0,1\} }[/math] 使得 [math]\displaystyle{ \mathcal{F} }[/math] 中不存在单色的集合 [math]\displaystyle{ S\in\mathcal{F} }[/math]。