Given two graphs and , where and , suppose that does not contain as a subgraph. Show that for , there is an

*edge*-coloring for such that contains no monochromatic .Prove that every -uniform hypergraph with vertices and edges contains an

*independent set*(i.e., a set of vertices containing no edges) of size at least .[Spencer 1990] Let be a -uniform hypergraph. Suppose that, in average, each vertex belongs to edges. Show that there exists an independent set of size at least .

Remark: Note that . When , this result is exactly the same as Problem .

[Alon 1986] An

*edge clique covering*of a graph is a family of complete subgraphs of such that every edge in belongs to at least one subgraph in the family. The minimum size of such a family is called the*edge clique covering number*, denoted by . Let be a graph on vertices such that every vertex has degree at least . Show that .*Hint*: (probably will be given next week)Let be a bipartite graph with vertices on each side. Suppose that the minimum degree of vertices is . Show that the edges of can be covered by at most complete bipartite subgraphs.

[

*Zarankiewicz’s problem*; Erdős--Spencer 1974] At most how many ’s can a - matrix contain if it has no submatrix whose entries are all ’s? Let denote the maximum number of 's in such a matrix. Show that for every there exists such that .(Bonus) Show that .