0 votes 0 votes Consider the sets $A_1, A_2, A_3 \dots A_m$ each a subset of size $k$ of $\{1,2,3, \dots , n\}$. If in a 2-colouring of $\{1,2,3, \dots , n\}$ no set $A_i$ is monochromatic, then show that $ m < 2^{k-1}$. Set Theory & Algebra probability random-variable combinatorics-iitb + – dd asked Apr 27, 2018 dd 377 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply srestha commented Apr 28, 2018 reply Follow Share https://ktiml.mff.cuni.cz/~fink/teaching/data_structures_I/matousek-vondrak-prob-ln.pdf 0 votes 0 votes srestha commented Apr 28, 2018 reply Follow Share chk 2.2.4 proving is it right one? 0 votes 0 votes Kushagra Chatterjee commented Apr 28, 2018 reply Follow Share In the above problem assume m=3,n=5 and k=2 So, here the sets are A1,A2,A3 each is a subset of size 2 of {1,2,3,4,5} Now, we colour the nos. 1,2,3,4 and 5 1 → BLUE 2 → RED 3 → BLUE 4 → RED 5 → BLUE Now, we are forming the sets A1,A2,A3 A1 = { 1,2 } A2 = { 3,4} A3 = { 5,4 } Check that none of the above sets are monochromatic and each of them is a subset of { 1,2,3,4,5 } Now, here m= 3 and k= 2 Thus m> 2k-1 which does not satisfy the condition which we have to find in the question m< 2k-1 I think something is missing or the conditions given are wrong. Debashis can you please check the problem or tell me if I am wrong somewhere. 0 votes 0 votes Please log in or register to add a comment.