imported>Etone |
imported>Etone |
| Line 1: |
Line 1: |
| =Field= | | == Problem 1 == |
| Let <math>S</math> be a set, '''closed''' under binary operations <math>+</math> (addition) and <math>\cdot</math> (multiplication). It gives us the following algebraic structures if the corresponding set of axioms are satisfied.
| | (Matching vs. Star) |
| {|class="wikitable"
| |
| !colspan="7"|Structures
| |
| !Axioms
| |
| !Operations
| |
| |-
| |
| |rowspan="9" style="background-color:#ffffcc;text-align:center;"|'''''field'''''
| |
| |rowspan="8" style="background-color:#ffffcc;text-align:center;"|'''''commutative<br>ring'''''
| |
| |rowspan="7" style="background-color:#ffffcc;text-align:center;"|'''''ring'''''
| |
| |rowspan="4" style="background-color:#ffffcc;text-align:center;"|'''''abelian<br>group'''''
| |
| |rowspan="3" style="background-color:#ffffcc;text-align:center;"|'''''group'''''
| |
| | rowspan="2" style="background-color:#ffffcc;text-align:center;"|'''''monoid'''''
| |
| |style="background-color:#ffffcc;text-align:center;"|'''''semigroup'''''
| |
| |1. '''Addition''' is '''associative''': <math>\forall x,y,z\in S, (x+y)+z= x+(y+z).</math>
| |
| |rowspan="4" style="text-align:center;"|<math>+</math>
| |
| |-
| |
| |
| |
| |2. Existence of '''additive identity 0''': <math>\forall x\in S, x+0= 0+x=x.</math>
| |
| |-
| |
| |colspan="2"|
| |
| |3. Everyone has an '''additive inverse''': <math>\forall x\in S, \exists -x\in S, \text{ s.t. } x+(-x)= (-x)+x=0.</math>
| |
| |-
| |
| |colspan="3"|
| |
| |4. '''Addition''' is '''commutative''': <math>\forall x,y\in S, x+y= y+x.</math>
| |
| |-
| |
| |colspan="4" rowspan="3"|
| |
| |5. Multiplication '''distributes''' over addition: <math>\forall x,y,z\in S, x\cdot(y+z)= x\cdot y+x\cdot z</math> and <math>(y+z)\cdot x= y\cdot x+z\cdot x.</math>
| |
| |style="text-align:center;"|<math>+,\cdot</math>
| |
| |-
| |
| |6. '''Multiplication''' is '''associative''': <math>\forall x,y,z\in S, (x\cdot y)\cdot z= x\cdot (y\cdot z).</math>
| |
| |rowspan="4" style="text-align:center;"|<math>\cdot</math>
| |
| |-
| |
| |7. Existence of '''multiplicative identity 1''': <math>\forall x\in S, x\cdot 1= 1\cdot x=x.</math>
| |
| |-
| |
| |colspan="5"|
| |
| |8. '''Multiplication''' is '''commutative''': <math>\forall x,y\in S, x\cdot y= y\cdot x.</math>
| |
| |-
| |
| |colspan="6"|
| |
| |9. Every non-zero element has a '''multiplicative inverse''': <math>\forall x\in S\setminus\{0\}, \exists x^{-1}\in S, \text{ s.t. } x\cdot x^{-1}= x^{-1}\cdot x=1.</math>
| |
| |}
| |
| The semigroup, monoid, group and abelian group are given by <math>(S,+)</math>, and the ring, commutative ring, and field are given by <math>(S,+,\cdot)</math>.
| |
|
| |
|
| Examples:
| | Given a graph <math>G(V,E)</math>, a ''matching'' is a subset <math>M\subseteq E</math> of edges such that there are no two edges in <math>M</math> sharing a vertex, and a ''star'' is a subset <math>S\subseteq E</math> of edges such that every pair <math>e_1,e_2\in S</math> of distinct edges in <math>S</math> share the same vertex <math>v</math>. |
| * '''Infinite fields''': <math>\mathbb{Q}</math>, <math>\mathbb{R}</math>, <math>\mathbb{C}</math> are fields. The integer set <math>\mathbb{Z}</math> is a commutative ring but is not a field.
| |
| * '''Finite fields''': Finite fields are called '''Galois fields'''. The number of elements of a finite field is called its '''order'''. A finite field of order <math>q</math>, is usually denoted as <math>\mathsf{GF}(q)</math> or <math>\mathbb{F}_q</math>.
| |
| ** '''Prime field''' <math>{\mathbb{Z}_p}</math>: For any integer <math>n>1</math>, <math>\mathbb{Z}_n=\{0,1,\ldots,n-1\}</math> under modulo-<math>p</math> addition <math>+</math> and multiplication <math>\cdot</math> forms a commutative ring. It is called '''quotient ring''', and is sometimes denoted as <math>\mathbb{Z}/n\mathbb{Z}</math>. In particular, for '''prime''' <math>p</math>, <math>\mathbb{Z}_p</math> is a field. This can be verified by [http://en.wikipedia.org/wiki/Fermat%27s_little_theorem Fermat's little theorem].
| |
| ** '''Boolean arithmetics''' <math>\mathsf{GF}(2)</math>: The finite field of order 2 <math>\mathsf{GF}(2)</math> contains only two elements 0 and 1, with bit-wise XOR as addition and bit-wise AND as multiplication. <math>\mathsf{GF}(2^n)</math>
| |
| ** Other examples: There are other examples of finite fields, for instance <math>\{a+bi\mid a,b\in \mathbb{Z}_3\}</math> where <math>i=\sqrt{-1}</math>. This field is isomorphic to <math>\mathsf{GF}(9)</math>. In fact, the following theorem holds for finite fields of given order.
| |
|
| |
|
| {{Theorem|Theorem|
| | Prove that any graph <math>G</math> containing more than <math>2(k-1)^2</math> edges either contains a matching of size <math>k</math> or a star of size <math>k</math>. |
| :A finite field of order <math>q</math> exists if and only if <math>q=p^k</math> for some prime number <math>p</math> and positive integer <math>k</math>. Moreover, all fields of a given order are isomorphic.
| |
| }}
| |
|
| |
|
| =Polynomial over a field=
| | (Hint: Learn from the proof of Erdos-Rado's sunflower lemma.) |
| Given a field <math>\mathbb{F}</math>, the '''polynomial ring''' <math>\mathbb{F}[x]</math> consists of all polynomials in the variable <math>x</math> with coefficients in <math>\mathbb{F}</math>. Addition and multiplication of polynomials are naturally defined by applying the distributive law and combining like terms.
| |
|
| |
|
| {{Theorem|Proposition (polynomial ring)|
| | == Problem 2 == |
| :<math>\mathbb{F}[x]</math> is a ring.
| | (Frankl 1986) |
| }}
| |
| The '''degree''' <math>\mathrm{deg}(f)</math> of a polynomial <math>f\in \mathbb{F}[x]</math> is the exponent on the '''leading term''', the term with a nonzero coefficient that has the largest exponent.
| |
|
| |
|
| Because <math>\mathbb{F}[x]</math> is a ring, we cannot do division the way we do it in a field like <math>\mathbb{R}</math>, but we can do division the way we do it in a ring like <math>\mathbb{Z}</math>, leaving a '''remainder'''. The equivalent of the '''integer division''' for <math>\mathbb{Z}</math> is as follows.
| | Let <math>\mathcal{F}\subseteq {[n]\choose k}</math> be a <math>k</math>-uniform family, and suppose that it satisfies that <math>A\cap B \not\subset C</math> for any <math>A,B,C\in\mathcal{F}</math>. |
| {{Theorem|Proposition (division for polynomials)|
| | * Fix any <math>B\in\mathcal{F}</math>. Show that the family <math>\{A\cap B\mid A\in\mathcal{F}, A\neq B\}</math> is an anti chain. |
| :Given a polynomial <math>f</math> and a nonzero polynomial <math>g</math> in <math>\mathbb{F}[x]</math>, there are unique polynomials <math>q</math> and <math>r</math> such that <math>f =q\cdot g+r</math> and <math>\mathrm{deg}(r)<\mathrm{deg}(g)</math>.
| | * Show that <math>|\mathcal{F}|\le 1+{k\choose \lfloor k/2\rfloor}</math>. |
| }}
| |
| The proof of this is by induction on <math>\mathrm{deg}(f)</math>, with the basis <math>\mathrm{deg}(f)<\mathrm{deg}(g)</math>, in which case the theorem holds trivially by letting <math>q=0</math> and <math>r=f</math>.
| |
|
| |
|
| As we turn <math>\mathbb{Z}</math> (a ring) into a finite field <math>\mathbb{Z}_p</math> by taking quotients <math>\bmod p</math>, we can turn a polynomial ring <math>\mathbb{F}[x]</math> into a finite field by taking <math>\mathbb{F}[x]</math> modulo a "prime-like" polynomial, using the division of polynomials above.
| | ==Problem 3 == |
| | An <math>n</math>-player tournament (竞赛图) <math>T([n],E)</math> is said to be '''transitive''', if there exists a permutation <math>\pi</math> of <math>[n]</math> such that <math>\pi_i<\pi_j</math> for every <math>(i,j)\in E</math>. |
|
| |
|
| {{Theorem|Definition (irreducible polynomial)|
| | Show that for any <math>k\ge 3</math>, there exists a finite <math>N(k)</math> such that every tournament of <math>n\ge N(k)</math> players contains a transitive sub-tournament of <math>k</math> players. Express <math>N(k)</math> in terms of Ramsey number. |
| :An '''irreducible polynomial''', or a '''prime polynomial''', is a non-constant polynomial <math>f</math> that ''cannot'' be factored as <math>f=g\cdot h</math> for any non-constant polynomials <math>g</math> and <math>h</math>.
| | |
| }}
| | ==Problem 4== |
| | We color each non-empty subset of <math>[n]=\{1,2,\ldots,n\}</math> with one of the <math>r</math> colors in <math>[r]</math>. Show that for any finite <math>r</math> there is a finite <math>N</math> such that for all <math>n\ge </math>$, for any <math>r</math>-coloring of all non-empty subsets of <math>[n]</math>, there always exist <math>1\le i<j<k\le n</math> such that the intervals <math>[i,j)=\{i,i+1,\ldots, j-1\}</math>, <math>[j,k)=\{j,j+1,\ldots, k-1\}</math> and <math>[i,k)=\{i,i+1,\ldots, k-1\}</math> are all assigned with the same color by the <math>r</math>-coloring. |
Problem 1
(Matching vs. Star)
Given a graph [math]\displaystyle{ G(V,E) }[/math], a matching is a subset [math]\displaystyle{ M\subseteq E }[/math] of edges such that there are no two edges in [math]\displaystyle{ M }[/math] sharing a vertex, and a star is a subset [math]\displaystyle{ S\subseteq E }[/math] of edges such that every pair [math]\displaystyle{ e_1,e_2\in S }[/math] of distinct edges in [math]\displaystyle{ S }[/math] share the same vertex [math]\displaystyle{ v }[/math].
Prove that any graph [math]\displaystyle{ G }[/math] containing more than [math]\displaystyle{ 2(k-1)^2 }[/math] edges either contains a matching of size [math]\displaystyle{ k }[/math] or a star of size [math]\displaystyle{ k }[/math].
(Hint: Learn from the proof of Erdos-Rado's sunflower lemma.)
Problem 2
(Frankl 1986)
Let [math]\displaystyle{ \mathcal{F}\subseteq {[n]\choose k} }[/math] be a [math]\displaystyle{ k }[/math]-uniform family, and suppose that it satisfies that [math]\displaystyle{ A\cap B \not\subset C }[/math] for any [math]\displaystyle{ A,B,C\in\mathcal{F} }[/math].
- Fix any [math]\displaystyle{ B\in\mathcal{F} }[/math]. Show that the family [math]\displaystyle{ \{A\cap B\mid A\in\mathcal{F}, A\neq B\} }[/math] is an anti chain.
- Show that [math]\displaystyle{ |\mathcal{F}|\le 1+{k\choose \lfloor k/2\rfloor} }[/math].
Problem 3
An [math]\displaystyle{ n }[/math]-player tournament (竞赛图) [math]\displaystyle{ T([n],E) }[/math] is said to be transitive, if there exists a permutation [math]\displaystyle{ \pi }[/math] of [math]\displaystyle{ [n] }[/math] such that [math]\displaystyle{ \pi_i\lt \pi_j }[/math] for every [math]\displaystyle{ (i,j)\in E }[/math].
Show that for any [math]\displaystyle{ k\ge 3 }[/math], there exists a finite [math]\displaystyle{ N(k) }[/math] such that every tournament of [math]\displaystyle{ n\ge N(k) }[/math] players contains a transitive sub-tournament of [math]\displaystyle{ k }[/math] players. Express [math]\displaystyle{ N(k) }[/math] in terms of Ramsey number.
Problem 4
We color each non-empty subset of [math]\displaystyle{ [n]=\{1,2,\ldots,n\} }[/math] with one of the [math]\displaystyle{ r }[/math] colors in [math]\displaystyle{ [r] }[/math]. Show that for any finite [math]\displaystyle{ r }[/math] there is a finite [math]\displaystyle{ N }[/math] such that for all [math]\displaystyle{ n\ge }[/math]$, for any [math]\displaystyle{ r }[/math]-coloring of all non-empty subsets of [math]\displaystyle{ [n] }[/math], there always exist [math]\displaystyle{ 1\le i\lt j\lt k\le n }[/math] such that the intervals [math]\displaystyle{ [i,j)=\{i,i+1,\ldots, j-1\} }[/math], [math]\displaystyle{ [j,k)=\{j,j+1,\ldots, k-1\} }[/math] and [math]\displaystyle{ [i,k)=\{i,i+1,\ldots, k-1\} }[/math] are all assigned with the same color by the [math]\displaystyle{ r }[/math]-coloring.