组合数学 (Spring 2026)/Problem Set 2: Difference between revisions
652024330006 (talk | contribs) |
652024330006 (talk | contribs) |
||
| (5 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
== Problem 1 == | == Problem 1 == | ||
Suppose <math> n \geq 4 </math>, and let <math> H </math> be an <math>n</math>-uniform hypergraph with at most <math> \frac{4^{ | Suppose <math> n \geq 4 </math>, and let <math> H </math> be an <math>n</math>-uniform hypergraph with at most <math> \frac{4^{n-1}}{3^n} </math> | ||
(hyper)edges. Prove that there is a coloring of the vertices of <math> H </math> by four colors so that in every (hyper)edge all four colors are represented. | (hyper)edges. Prove that there is a coloring of the vertices of <math> H </math> by four colors so that in every (hyper)edge all four colors are represented. | ||
== Problem 2 == | == Problem 2 == | ||
Use the Lovász Local Lemma to show that, if <math> 4\binom{k}{2}\binom{n}{k-2}2^{1-\binom{k}{2}} \leq 1 </math>, then it is possible to color the edges of <math>K_n</math> with two colors so that it has no monochromatic <math>K_k</math> subgraph. | Use the Lovász Local Lemma to show that, for <math> n \geq k \geq 3 </math>, if <math> 4\binom{k}{2}\binom{n}{k-2}2^{1-\binom{k}{2}} \leq 1 </math>, then it is possible to color the edges of <math>K_n</math> with two colors so that it has no monochromatic <math>K_k</math> subgraph. | ||
== Problem 3 == | == Problem 3 == | ||
Let <math>G = (V, E)</math> be an undirected graph and suppose each <math>v \in V</math> is | Let <math>G = (V, E)</math> be an undirected graph and suppose each <math>v \in V</math> is | ||
associated with a set <math>S(v)</math> of at least <math>2\mathrm{e}r</math> colors, where <math>r \geq 1 </math>. Suppose, in addition, that for each | associated with a set <math>S(v)</math> of at least <math>2\mathrm{e}r</math> colors, where <math>r \geq 1 </math> is an integer. Suppose, in addition, that for each | ||
<math>v \in V</math> and <math>c \in S(v)</math> there are at most <math>r</math> neighbors <math>u</math> of <math>v</math> such that <math>c</math> lies in <math>S(u)</math>. Prove | <math>v \in V</math> and <math>c \in S(v)</math> there are at most <math>r</math> neighbors <math>u</math> of <math>v</math> such that <math>c</math> lies in <math>S(u)</math>. Prove | ||
that there is a proper coloring of <math>G</math> assigning to each vertex <math>v</math> a color from its class | that there is a proper coloring of <math>G</math> assigning to each vertex <math>v</math> a color from its class | ||
<math>S(v)</math> such that, for any edge <math>(u, v) \in E</math>, the colors assigned to <math>u</math> and <math>v</math> are different. | <math>S(v)</math> such that, for any edge <math>(u, v) \in E</math>, the colors assigned to <math>u</math> and <math>v</math> are different. | ||
== Problem 4 == | == Problem 4 == | ||
| Line 24: | Line 20: | ||
Solve the following two existence problems: | Solve the following two existence problems: | ||
* You are given <math>n</math> integers <math>a_1,a_2,\dots,a_n</math>, such that for each <math> 1\leq i\leq n</math> it holds that <math>i-n\leq a_i\leq i-1</math>. Show that there exists a '''nonempty''' subsequence (not necessarily consecutive) of these integers, whose sum is equal to <math> 0 </math>. (Hint: Consider <math> b_i=a_i | * You are given <math>n</math> integers <math>a_1,a_2,\dots,a_n</math>, such that for each <math> 1\leq i\leq n</math> it holds that <math>i-n\leq a_i\leq i-1</math>. Show that there exists a '''nonempty''' subsequence (not necessarily consecutive) of these integers, whose sum is equal to <math> 0 </math>. (Hint: Consider <math> b_i=i-a_i </math>) | ||
* You are given two '''multisets''' <math> A </math> and <math> B </math>, both with <math> n </math> integers from <math> 1 </math> to <math> n </math>. Show that there exist two '''nonempty''' | * You are given two '''multisets''' <math> A </math> and <math> B </math>, both with <math> n </math> integers from <math> 1 </math> to <math> n </math>. Show that there exist two '''nonempty''' submultisets <math> A'\subseteq A </math> and <math> B'\subseteq B </math> with equal sum, i.e. <math>\sum\limits_{x\in A'}x=\sum\limits_{y\in B'}y </math> (Hint: Replace the term ''multiset'' by ''sequence'', the term ''submultiset'' by ''consecutive subsequence'', and the statement is still true. ) | ||
== Problem 5 == | == Problem 5 == | ||
| Line 37: | Line 33: | ||
== Problem 6 == | == Problem 6 == | ||
For | For an integer <math>n \geq 2</math>, write <math>[n]=\{1,2,\ldots,n\}.</math> | ||
A set <math>A\subseteq [n]</math> is called subset-sum-distinct if the <math>2^{|A|}</math> sums <math>\sum_{a\in S}a, S\subseteq A,</math> are pairwise distinct, where the empty sum is understood to be <math>0</math>. | A set <math>A\subseteq [n]</math> is called subset-sum-distinct if the <math>2^{|A|}</math> sums <math>\sum_{a\in S}a, S\subseteq A,</math> are pairwise distinct, where the empty sum is understood to be <math>0</math>. | ||
Latest revision as of 11:55, 21 April 2026
Problem 1
Suppose [math]\displaystyle{ n \geq 4 }[/math], and let [math]\displaystyle{ H }[/math] be an [math]\displaystyle{ n }[/math]-uniform hypergraph with at most [math]\displaystyle{ \frac{4^{n-1}}{3^n} }[/math] (hyper)edges. Prove that there is a coloring of the vertices of [math]\displaystyle{ H }[/math] by four colors so that in every (hyper)edge all four colors are represented.
Problem 2
Use the Lovász Local Lemma to show that, for [math]\displaystyle{ n \geq k \geq 3 }[/math], if [math]\displaystyle{ 4\binom{k}{2}\binom{n}{k-2}2^{1-\binom{k}{2}} \leq 1 }[/math], then it is possible to color the edges of [math]\displaystyle{ K_n }[/math] with two colors so that it has no monochromatic [math]\displaystyle{ K_k }[/math] subgraph.
Problem 3
Let [math]\displaystyle{ G = (V, E) }[/math] be an undirected graph and suppose each [math]\displaystyle{ v \in V }[/math] is associated with a set [math]\displaystyle{ S(v) }[/math] of at least [math]\displaystyle{ 2\mathrm{e}r }[/math] colors, where [math]\displaystyle{ r \geq 1 }[/math] is an integer. Suppose, in addition, that for each [math]\displaystyle{ v \in V }[/math] and [math]\displaystyle{ c \in S(v) }[/math] there are at most [math]\displaystyle{ r }[/math] neighbors [math]\displaystyle{ u }[/math] of [math]\displaystyle{ v }[/math] such that [math]\displaystyle{ c }[/math] lies in [math]\displaystyle{ S(u) }[/math]. Prove that there is a proper coloring of [math]\displaystyle{ G }[/math] assigning to each vertex [math]\displaystyle{ v }[/math] a color from its class [math]\displaystyle{ S(v) }[/math] such that, for any edge [math]\displaystyle{ (u, v) \in E }[/math], the colors assigned to [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] are different.
Problem 4
Solve the following two existence problems:
- You are given [math]\displaystyle{ n }[/math] integers [math]\displaystyle{ a_1,a_2,\dots,a_n }[/math], such that for each [math]\displaystyle{ 1\leq i\leq n }[/math] it holds that [math]\displaystyle{ i-n\leq a_i\leq i-1 }[/math]. Show that there exists a nonempty subsequence (not necessarily consecutive) of these integers, whose sum is equal to [math]\displaystyle{ 0 }[/math]. (Hint: Consider [math]\displaystyle{ b_i=i-a_i }[/math])
- You are given two multisets [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math], both with [math]\displaystyle{ n }[/math] integers from [math]\displaystyle{ 1 }[/math] to [math]\displaystyle{ n }[/math]. Show that there exist two nonempty submultisets [math]\displaystyle{ A'\subseteq A }[/math] and [math]\displaystyle{ B'\subseteq B }[/math] with equal sum, i.e. [math]\displaystyle{ \sum\limits_{x\in A'}x=\sum\limits_{y\in B'}y }[/math] (Hint: Replace the term multiset by sequence, the term submultiset by consecutive subsequence, and the statement is still true. )
Problem 5
Let [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] be positive integers, and let [math]\displaystyle{ (A_1,B_1),(A_2,B_2),\ldots,(A_m,B_m) }[/math] be [math]\displaystyle{ m }[/math] ordered pairs of finite subsets of the positive integers. Suppose that for every [math]\displaystyle{ i=1,2,\ldots,m }[/math], [math]\displaystyle{ |A_i|=a, |B_i|=b, A_i\cap B_i=\varnothing. }[/math]
Prove that if [math]\displaystyle{ m\gt \binom{a+b}{a}, }[/math] then there exist two distinct indices [math]\displaystyle{ i\neq j }[/math] such that [math]\displaystyle{ A_i\cap B_j=\varnothing. }[/math]
Problem 6
For an integer [math]\displaystyle{ n \geq 2 }[/math], write [math]\displaystyle{ [n]=\{1,2,\ldots,n\}. }[/math]
A set [math]\displaystyle{ A\subseteq [n] }[/math] is called subset-sum-distinct if the [math]\displaystyle{ 2^{|A|} }[/math] sums [math]\displaystyle{ \sum_{a\in S}a, S\subseteq A, }[/math] are pairwise distinct, where the empty sum is understood to be [math]\displaystyle{ 0 }[/math].
Define [math]\displaystyle{ f(n) }[/math] to be the largest integer [math]\displaystyle{ k }[/math] for which there exists a subset-sum-distinct set [math]\displaystyle{ A\subseteq [n] }[/math] with [math]\displaystyle{ |A|=k }[/math].
Prove the following two upper bounds.
- Prove that there is an absolute constant [math]\displaystyle{ c }[/math] with the following property: [math]\displaystyle{ f(n)\leq \log_2 n+\log_2\log_2 n+c. }[/math]
- Prove that there is an absolute constant [math]\displaystyle{ c }[/math] with the following property: [math]\displaystyle{ f(n)\leq \log_2 n+\frac12\log_2\log_2 n+c. }[/math]