组合数学 (Spring 2024)/Problem Set 3: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
Gispzjz (talk | contribs)
Created page with "== Problem 1 == 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-i </math>) * You are given two '''multisets''' <math> A </math> and <ma..."
 
Roundgod (talk | contribs)
 
(One intermediate revision by one other 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 24: Line 24:


== Problem 5 ==
== Problem 5 ==
Let <math>G=(V,E)</math>be a graph on <math> n </math> vertices and <math> t(G) </math> the number of triangles in it. Show that <math> t(G)\geq \frac{|E|}{3n}\left(4|E|-n^2\right) </math>.
Let <math>G=(V,E)</math> be a graph on <math> n </math> vertices and <math> t(G) </math> the number of triangles in it. Show that <math> t(G)\geq \frac{|E|}{3n}\left(4|E|-n^2\right) </math>.




'''Hint''': For an edge <math> e=(u,v)\in E </math>, let <math> t(e) </math> be the number of triangles containing <math> e </math>. Try to obtain that <math> t(e) \geq d(u)+d(v)-n </math> and use Cauchy–Schwarz inequality to esitimate the sum <math> \sum_{e=(u,v)\in E} (d(u)+d(v))</math>.
'''Hint''': For an edge <math> e=(u,v)\in E </math>, let <math> t(e) </math> be the number of triangles containing <math> e </math>. Try to obtain that <math> t(e) \geq d(u)+d(v)-n </math> and use Cauchy–Schwarz inequality to esitimate the sum <math> \sum_{e=(u,v)\in E} (d(u)+d(v))</math>.

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

Prove that there is an absolute constant [math]\displaystyle{ c\gt 0 }[/math] with the following property: let [math]\displaystyle{ A }[/math] be an [math]\displaystyle{ n\times n }[/math] matrix with pairwise distinct entries. Then there is a permutation of the rows of [math]\displaystyle{ A }[/math] so that no column in the permuted matrix contains an increasing subsequence of length at least [math]\displaystyle{ c\sqrt{n} }[/math].

Problem 3

A [math]\displaystyle{ 3 }[/math]-uniform hypergraph [math]\displaystyle{ H=(V,E) }[/math] consists of a set of vertices [math]\displaystyle{ V }[/math] and a set of edges [math]\displaystyle{ E }[/math], where each edge [math]\displaystyle{ e\in E }[/math] is a set of exactly three vertices from [math]\displaystyle{ V }[/math]. Prove:

Every [math]\displaystyle{ 3 }[/math]-uniform hypergraph with [math]\displaystyle{ n }[/math] vertices and [math]\displaystyle{ m\geq n/3 }[/math] edges contains an independent set (i.e., a set of vertices containing no edges) of size at least [math]\displaystyle{ \frac{2n^{1.5}}{3\sqrt{3m}} }[/math].

Problem 4

Let [math]\displaystyle{ D=(V,E) }[/math] be a simple directed graph with minimum outdegree [math]\displaystyle{ \delta }[/math] and maximum indegree [math]\displaystyle{ \Delta }[/math]. Prove:

For any positive integer [math]\displaystyle{ k }[/math], if [math]\displaystyle{ \mathrm{e}(\Delta \delta+1)(1-\frac{1}{k})^{\delta}\lt 1 }[/math], then [math]\displaystyle{ D }[/math] contains a (directed,simple) cycle of length [math]\displaystyle{ 0\pmod k. }[/math]


Hint: Let [math]\displaystyle{ f:V\rightarrow \{0,1,\dots,k-1\} }[/math] be a random coloring of [math]\displaystyle{ V }[/math] obtained by choosing uniformly and independently at random for each [math]\displaystyle{ v\in V }[/math]. Try to use Lovász Local Lemma to show something interesting!

Problem 5

Let [math]\displaystyle{ G=(V,E) }[/math] be a graph on [math]\displaystyle{ n }[/math] vertices and [math]\displaystyle{ t(G) }[/math] the number of triangles in it. Show that [math]\displaystyle{ t(G)\geq \frac{|E|}{3n}\left(4|E|-n^2\right) }[/math].


Hint: For an edge [math]\displaystyle{ e=(u,v)\in E }[/math], let [math]\displaystyle{ t(e) }[/math] be the number of triangles containing [math]\displaystyle{ e }[/math]. Try to obtain that [math]\displaystyle{ t(e) \geq d(u)+d(v)-n }[/math] and use Cauchy–Schwarz inequality to esitimate the sum [math]\displaystyle{ \sum_{e=(u,v)\in E} (d(u)+d(v)) }[/math].