组合数学 (Fall 2023)/Problem Set 3: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
Roundgod (talk | contribs)
Roundgod (talk | contribs)
 
(One intermediate revision by the same user not shown)
Line 5: Line 5:
* 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-i </math>)  
* 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-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 exists two '''nonempty''' subsets <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 ''subset'' by ''consecutive subsequence'', and the statement is still true. )
* 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''' subsets <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 ''subset'' by ''consecutive subsequence'', and the statement is still true. )


== Problem 2 ==
== Problem 2 ==
Line 17: Line 17:
== Problem 4 ==
== Problem 4 ==
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 <math>\lceil 2\mathrm{e}r\rceil</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>. 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

Latest revision as of 17:15, 14 May 2024

Problem 1

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=a_i-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 subsets [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 subset by consecutive subsequence, and the statement is still true. )

Problem 2

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 3

The girth of a graph is the length of its smallest cycle. Show that for any integer [math]\displaystyle{ k\geq 3 }[/math], for [math]\displaystyle{ n }[/math] sufficiently large there is a simple graph with [math]\displaystyle{ n }[/math] vertices, at least [math]\displaystyle{ \frac{1}{4}n^{1+1/k} }[/math] edges, and girth at least [math]\displaystyle{ k }[/math]. (Hint: Try to generate a random graph with [math]\displaystyle{ n }[/math] vertices and then fix things up!)

Problem 4

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]. 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 5

Prove the following theorem on extremal graph theory:

  • (Graham–Kleitman 1973). If the edges of a complete graph on [math]\displaystyle{ n }[/math] vertices are labeled arbitrarily with the integers [math]\displaystyle{ 1, 2,\dots, \frac{n(n-1)}{2} }[/math], each edge receiving its own integer, then there is a trail (i.e., a walk without repeated edges) of length at least [math]\displaystyle{ n − 1 }[/math] with an increasing sequence of edge-labels. (Hint: To each vertex [math]\displaystyle{ v }[/math], assign its weight [math]\displaystyle{ w_v }[/math] equal to the length of the longest increasing trail ending at [math]\displaystyle{ v }[/math]. Can you show that [math]\displaystyle{ \sum\limits_{i=1}^{n} w_i\geq n(n-1) }[/math]?)