Algebraic Techniques in Combinatorics - Yufei Zhao

1 MOP 2007 Black GroupAlgebraic Techniques in CombinatoricsYufei ZhaoAlgebraic Techniques in CombinatoricsJune 26, 2007 Yufei algebraUseful facts in linear algebra Any set ofn+ 1 vectors in ann-dimensional vector space is linearly dependent. That is, we canfind scalarsa1,..,an+1, not all zero, such thata1v1+ +an+1vn+1= 0. Almost all linear algebra results (especially the ones related to rank) are true over any field. Forinstance, the fieldF2is often useful for working with parity or incidence. However, note that wemight not be able to use eigenvalues. Suppose thatAis anm nmatrix, then the subspace spanned by its columns has the samedimension as the subspace spanned by its rows. This common dimension number is called therank ofA. In particular, we have rankA min(m,n). Rank-nullity theorem: rankA+ nullityA=n. rank(AB) min(rankA,rankB) rank(A+B) rankA+ rankB Ais invertible if and only ifm=n= rankA. IfAis a square matrix, then it is invertible if andonly if there does not exist a nonzero vectorvsuch thatAv= 0.

2 Or equivalently, none of theeigenvalues ofAis zero. The determinant of a square matrixAcan be evaluated by taking a sum over all permutationsof{1,2,..,n}detA= Sn( 1)sgn a1 (1)a2 (2) an (n).A matrix is invertible if an only if its determinant is nonzero. InF2, we no longer have to worryabout the sign in front of the product. IfWis a subspace ofV, denoteW ={v V|vtw= 0 w W}, thendimW+ dimW = , it s not necessarily true thatW W =V! , takeW={(0,0),(1,1)}inF22, thenW =W. Suppose that we have a set of mapsfi:V R, and pointsvi V, 1 i n. Iffi(vi)6= 0 andfi(vj) = 0 wheneveri6=j, thenf1,f2,..,fnare linearly 2007 Black GroupAlgebraic Techniques in CombinatoricsYufei ZhaoProblem:(St. Petersburg) Students in a school go for ice cream in groups of at least two. Afterk >1 groups have gone, every two students have gone together exactly once. Prove that the numberof students in the school is at is a combinatorial solution which is somewhat long and non-intuitive.

3 However, amuch quicker (and more intuitive) solution is available using the tools of linear there benstudents. Note if some student went for ice cream only once, then everyone else hasto have gone with that student, due to the constraint that every pair of student have gone togetherexactly once. Furthermore, since each group consists of two students, no other groups can be ,k >1, so this situation cannot occur. Therefore, every student went for ice cream at us constructincidence vectors vi Rk,1 1 n, representing the students. That is, thej-th component ofviis 1 if studentiwent with thej-th group, and 0 condition that every two students have gone together exactly once translates into the dotproductvi vj= 1 fori6=j. The condition that every student went for ice cream at least twicetranslates into|vi|2 want to prove thatn k. Suppose otherwise. Then{v1,..,vn}consists of at leastk+ 1vectors inRk, so they must be linearly dependent.

4 It follows that there are real numbers 1,.., n,not all zero, such that 1v1+ + nvn= us square the above expression ( , taking the dot product with itself. We get0 =n i=1 2i|vi|2+ 2 i<j i jvi vj=n i=1 2i|vi|2+ 2 i<j i j=n i=1 2i(|vi|2 1)+(n i=1 i) , the RHS expression is positive, since|vi|2 2 and some iis nonzero. , we can use anincidence matrixto obtain a somewhat faster (albeit more tech-nically involved) solution. The incidence matrixMis ak nmatrix, whereMijis 1 if thei-th groupincludes studentj. Using the notation in the previous solution, we can write this asM= | | |v1v2 vn| | | Consider the productMtM. Sincevi vj= 1 fori6=jand|vi|2 2 for alli, we see thatMtM=J+A,whereJis then nmatrix with all entries 1, andAis a diagonal matrix with positive diagonal thatJis positive semidefinite (meaning thatxtJx 0 for all vectorsx) andMis positive definite(meaning thatxtJx>0 for allx6= 0). Therefore, their sumJ+A=MtMis positive definite.)

5 Inparticular, this means thatMtMis invertible, so its rank isn. SinceMis ak nmatrix, we concludethatk 2007 Black GroupAlgebraic Techniques in CombinatoricsYufei ZhaoPartially ordered sets (posets) ordered set(orposetfor short)Pis a set, also denotedP, together with abinary relation denoted satisfying the following axioms: (reflexivity)x xfor allx P (antisymmetry) Ifx yandy x, thenx=y. (transitivity) Ifx yandy z, thenx example of a poset is the set of all subsets of{1,2,..,n}under the relation . This poset issometimes called theBoolean algebra of rankn, and diagramis a simple way of representing (small) posets. We say thatxcoversyifx > y( ,x yandx6=y) and there is noz Psuch thatx > z > y. Ifxcoversy, then wedrawxaboveyand connect them using a line segment. Note that in general,x > yif and only ifxis aboveyand we trace a downward path fromxtoyin the Hasse diagram. The Hasse diagram forB3is depicted below.

6 {1,2,3}{1,2}{1,3}{2,3}{1}{2}{3} There is one result about posets that has proven useful for olympiad problems. Before we statethis result, let us go over some more elementsx,yof a poset are calledcomparableifx yorx y, otherwise they are calledincomparable. Achainis a sequence of elementsa1< a2< < ak, and anantichainis a setof pairwise incomparable elements. Thelengthor a chain or antichain is the number of elementscontained in we are ready to stateDilworth s 1.(Dilworth)LetPbe a finite poset. Then the smallest set of chains whose union isPhas the same cardinality as the longest is also a dual version of this theorem that s much easier to a finite poset. Then the smallest set of antichains whose union isPhas thesame cardinality as the longest length of the longest chain and the length of the longest antichain are often referred to as theheightandwidthof a poset, respectively.

7 Another way of stating the two theorems is that if a posetPhas heighthand widthw, thenPcan be covered withhantichains andwchains. One simpleconsequence is that|P| h 2007 Black GroupAlgebraic Techniques in CombinatoricsYufei ZhaoInstead of proving the the above two theorems, which you can do yourself1, let s see how we canapply :(Romania TST 2005) Letnbe a positive integer andSa set ofn2+ 1 positive integerswith the property that every (n+ 1)-element subset ofScontains two numbers one of which is divisibleby the other. Show thatScontainsn+ 1 different numbersa1,a2,..,an+1such thatai|ai+1foreachi= 1,2,.., the divisibility relation to obtain a poset onS(that is,x yiffx|y. Check thatthis makes a poset). The condition that there does not exist ann+ 1 element subset ofSthat noelement divides another translates into the condition that there does not exist an antichain of lengthn+ 1 inS. So the longest antichain inSat length at mostn, and thus by Dilworth s theorem,Scanbe written as the union of at mostnchains.

8 SinceShasn2+ 1 elements, this implies that one ofthese chains has a length of at leastn+ 1. This implies the very similar result is theErd os Szekeres Theorem, which states that within any sequenceofab+ 1 real numbers, there is either a nondecreasing subsequence ofa+ 1 terms, or a nonincreasingsubsequence ofb+ 1 terms. This result is also a simple consequence of Dilworth s examples are given in the problems related to linear algebra1. (Nonuniform Fisher inequality) LetA1,..,Ambe distinct subsets of{1,2,..,n}. Suppose thatthere is an integer 1 < nsuch that|Ai Aj|= for alli6=j. Prove thatm (a) (China West 2002) LetA1,A2,..,An+1be non-empty subsets of{1,2,..,n}. Prove thatthere exists nonempty disjoint subsetsI,J {1,2,..,n+ 1}such that k IAk= k JAk.(b) (Lindstrom) LetA1,A2,..,An+2be non-empty subsets of{1,2,..,n}. Prove that thereexists nonempty disjoint subsetsI,J {1,2,..,n+ 2}such that k IAk= k JAk,and k IAk= k (Russia 2001) A contest withnquestion was taken bymcontestants.

9 Each question was worth acertain (positive) number of points, and no partial credits were given. After all the papers havebeen graded, it was noticed that by reassigning the scores of the questions, any desired rankingof the contestants could be achieved. What is the largest possible value ofm? and Eventown. In a certain town withncitizens, a number of clubs are set up. Notwo clubs have exactly the set of members. Determine the maximum number of clubs that canbe formed under each of the following constraints:(a) The size of every club is odd, and every pair of clubs share an even number of you are really stuck, then you may consult the proof at, for example, 2007 Black GroupAlgebraic Techniques in CombinatoricsYufei Zhao(b) The size of every club is even, and every pair of clubs share an odd number of members.(c) The size of every club is even, and every pair of clubs share an even number of members.

10 (d) The size of every club is odd and every pair of clubs share an odd number of (Moldova TST 2005) Does there exist a configuration of 22 distinct circles and 22 distinct pointson the plane, such that every circle contains at least 7 points and every point belongs at leastto 7 circles?6. (Iran TST 1996, Germany TST 2004) LetGbe a finite simple graph, and there is a light bulbat each vertex ofG. Initially, all the lights are off. Each step we are allowed to chose a vertexand toggle the light at that vertex as well as all its neighbors . Show that we can get all thelights to be on at the same Leta1,a2,..,anbe integers. Show that 1 i<j nai aji jis an integer. (Hint: use the Vandermonde determinant.)8. (a) LetGbe a graph withvvertices. Letf(n) denote the number of closed walks inGoflengthn. Show that there exists complex numbers 1,.., vsuch thatf(n) = n1+ n2+ + nvfor all positive integersn.