Montreal Math ClubMathematics students in Montreal - Étudiants de mathématiques à Montréal

 Montreal Math Club :: Mathematics :: Set theory and Topology Share

Chvátal's conjecture (1974)

AuthorMessage

Euclid

Posts : 95
Join date : 2009-09-15
Age : 56
Location : Alexandria

 Subject: Chvátal's conjecture (1974)   Fri Sep 18, 2009 1:05 pm It is about the problem that E. proposed and put ten dollars on it.Here is the writing taken from "Combinatorics of Finite Sets" by Ian Anderson.page 103A collection B of subsets of an n-set S is a star if there is an element x in S such that x is in B for all B in B. Chvátal conjectured that we are looking for as large an intersecting family as possible in an ideal, then we can restrict our search to the stars.page 54 An intersecting family is a collection of subsets of a set no two of which are disjoint.page 87An ideal (downset, simplicial complex) is a collection D of subsets of an n-set S with the property : if A belongs to D, then all subsets of A are also in D.======Is seems I missed the part with restriction to stars, so I started to search stars inside intersecting families.Last edited by nick on Sat Oct 17, 2009 4:16 pm; edited 1 time in total

Euclid

Posts : 95
Join date : 2009-09-15
Age : 56
Location : Alexandria

 Subject: Re: Chvátal's conjecture (1974)   Fri Sep 25, 2009 10:56 pm I got an exerciseA : 1 4 5 6 7B : 1 8 9 10 11C : 1 2 12 13 D : 2 4 8 14 15E : 2 3 5 9F : 3 6 10 12 14G : 3 7 11 13 15Let A, B, ... be gangsThe above system of gangs is a shell : every two gangs have in common exactly one member.there are 2-connectors, like 4,5,6...15 and 3-connectors, like 1, 2, and 3let's note <2> the number of 2-connectors <3> the number of 3-connectors Show that generally, If a shell has only 2-connectors and 3-connectors then<2> + 3<3> = gangs(gangs-1)/2in the above example the relation becomes12 + 3.3 = 7(7-1)/2==== let me note exercise.nick.2 ( it is easier than the first) ======more general, <2> + 3 <3> + 6 <4> + ... + n(n-1)/2 = gangs(gangs-1)/2

Euclid

Posts : 95
Join date : 2009-09-15
Age : 56
Location : Alexandria

 Subject: Re: Chvátal's conjecture (1974)   Sat Sep 26, 2009 12:21 pm ======= so =========Let's take a 1-connected shell , within every two gangs have exactly one member in common.A : 1 2 3 4B : 1 5 6 7 C : 1 8 9 10 D : 1 11 12 13E : 2 5 8 11F : 2 6 9 12G : 2 7 10 13H : 3 5 9 13I : 3 7 8 12J : 4 5 10 12K : 4 6 8 13L : 4 7 9 11the trail of the pivot 1 is 1, {1 2}, .., {1 12}, {1 2 3}, ... 1 12 13, {1 2 3 4}, ...,{1 11 12 13} having 1 + 12 +12 + 4 = 29 sets Let now say 1 is a maximal connector (it is a 4- connector here,like the others.)Then, looking at only one gang that it belongs (let A be the choosen) we can predict an upper bound for the number of gangs,#gangs<= k + (k-1) frA(1) because i) A is connected with the all other gangsii) k is the maximum connectivity ( in above example, k=4)On the other hand, the star of 1 ( in a 1-connected shell) (that means there are no friends of 1 to double it ) has to contain|Star(1)| = 1 + 2^frA(1)- 1 + 2 ^frB(1) -1 +....+ frK(1) -1 sets.By choosing a minimal gang that 1 belongs to, let's say A, we got to proof :k + (k-1).frA(1) <= 1 + k.2^frA(1) - k (formula 1)or, k (2^f - f -2) + f +1 >= 0 where f is frA(1). A bad case is when f = 1, like inA : 1 2B : 1 3C : 1 4D : 2 3 4In all the other cases (formula 1) is true.===== case f = 1, when there is a {1 2} gang ==============the shell looks like thisA : 1 a bB : 1 c dC : 1 e fD : ---------1 2 --------E : 2 a b cF : 2 d e fwhere 1 is a k-connector,2 is a j-connectora,b,...f are (k-1).(j-1) 2-connectors ( connecting some gang upside with some gang downside)Let 1 be the higher connector among {1, 2} and let's count#gangs = j + k - 1|Star(2)| = 1 + 1 + (j-1).( 2^(k-1) -1)here, #gangs always <= |Star(2)| and I think it's done for 1-connected shells.I did not count the singular members (the 1-connectors) because they not affect by registering the number of gangs, and they just could increase a maximal star.

Euclid

Posts : 95
Join date : 2009-09-15
Age : 56
Location : Alexandria

 Subject: Re: Chvátal's conjecture (1974)   Sat Oct 03, 2009 12:34 am A PERFECT SHELL of twenty-one gangs built on six membersab bc acab1 bc1 ac1ab2 bc2 ac2ab3 bc3 ac3ab12 bc12 ac12ab23 bc13 ac23ab13 bc23 ac13the star of a is contained in:a12ba23ba13ba12ca13ca23c, so let's list:a a1 a2 a3 a12 a23 a13ab a1b a2b a3b a12b a23b a13bac a1c a2c a3c a12c a23c a13c twenty-onethe star of 1 is contained in1ab21bc21ac21ab31bc31ac3 that is similar with the star of a. Twenty-one.Last edited by nick on Thu Oct 08, 2009 9:23 pm; edited 1 time in total

Euclid

Posts : 95
Join date : 2009-09-15
Age : 56
Location : Alexandria

 Subject: Re: Chvátal's conjecture (1974)   Thu Oct 08, 2009 8:07 am A simple casei) all gangs have exactly three membersii) there are exactly three types of gangs{1, 2, x} type A{2, 3, x) type B{1, 3, x) type CThe presence of {1,2,3} does not affect the calculus, since it increases the stars and the number of gangs with exactly one. Nevertheless it suggests to search a good pivot in {1,2,3} let a = number of members that belong only to an A-type gang (counted in for all A-type gangs) (they must be different since {1,2,x} = {1,2,y} => x=yb = ...............................................................................B typec = ................................................................................C typed = # of members in A type, in B type but not Ce = # of members in B, C but not in Af = # of members in A, C but not in Ag = # of members common in an A-type, A B-type and a C-type gang.(I use a Venn diagram)The total number of gangs is #gangs = a + b + c + 2.d + 2.e + 2.f + 3.gthe star of 1 has 3 + 2.a + 0.b + 2.c + 2.d + 2.e + 3.f + 3.g members so#Star(1) - #gangs = 3 + a - b + c + f; writing the similar equalities for 2 and 3 we get#Star(2) - #gangs = 3 + a + b - c + d#Star(3) - #gangs = 3 - a + b + c + eThe sum of the three equalities is 9 + a + b + c + d + e + f, which is a positive number, so one of #Star(x) - #gangs must be positive for some x in {1,2,3}.To obtain a perfect shell one must take a=b=c=d=e=f=0 and add the gangs {1,2}, {2, 3} and {1, 3}.Following the above guide line we obtained another perfect shell {1, 2} {2, 3} {1, 3} {1, 2, a} {1, 3, a} {2, 3, a} {1, 2, 3} seven gangsStar (1) = 1, 12, 13, 1a, 12a, 13a, 123 --- seven setsStar(a) = a, a1, a2, a3, a12, a23, a13----> seven setsLast edited by nick on Thu Oct 08, 2009 11:06 pm; edited 1 time in total

Euclid

Posts : 95
Join date : 2009-09-15
Age : 56
Location : Alexandria

 Subject: Re: Chvátal's conjecture (1974)   Thu Oct 08, 2009 10:53 pm Before Next GeneralizationLet' define a hood as a list of individuals and gangs.hood_A contains all individuals that belongs to a {1, 2, ...} gang and not to a {2, 3, ...} or to a {1, 3,...} onehood_B contains all individuals that belongs to a {2, 3, ...} gang and not to a {1, 2, ...} or to a {1, 3,...} onehood_C contains all individuals that belongs to a {1, 3,...} gang and not to a {1, 2, ...}or to a {2, 3,...} onehood_D contains all individuals that belongs to a {1, 2, ...} and a {2, 3, ...} and not to a {1, 3,...} onehood_E contains all individuals that belongs to a {2, 3, ...} and a {1, 3, ...} and not to a {1, 2,...} onehood_F contains all individuals that belongs to a {1, 2, ...} and a {1, 3, ...} and not to a {2, 3,...} onehood_G contains all individuals that belongs to a {1, 2, ...} a {2, 3, ...} and a {1, 3,...} gang Thus, we have induced a partition on the individuals' ensemble; each individual has its own hood.Visiting members - for example, a shell containsGang_1 : {1, 2, 4, 5}Gang_2 : {1, 2, 4, 5, 6 ....} and no other occurrences for '4'Gang_3 : {1, 3, 5, ...} and no other occurrences of '5'.- the hood of '4' is hood_A and - the hood of '5' is hood_F Therefore, Gang_1 and Gang_2 must be listed both in hood_A and in hood_F. I will say that '5' is a visiting member in the hood_A and '4' is a visiting member in the hood_F. Reversely, if there are no visiting members in the seven hoods, a gang can not be listed more than one time, because: Let' say Hood_A contains a gang Gang_X that is also in listed in another hood. Then I ask the "home" hood of each of its members. No visiting members in Gang_X means that Gang_X has no reason to be listed in other hood.Next generalizationi) there are no visiting membersii) there are exactly three types of gangs{1, 2, x,....} type I{2, 3, x,...) type II{1, 3, x,...) type IIILet's take an example of hood_A. Hood_A could look like thisindividuals : 4, 5, 6, 7 gangs :{ 1, 2, 4 }{ 1, 2, 4, 5 }{ 1, 2, 5, 6 }{ 1, 2, 4, 6, 7 }Last edited by nick on Fri Oct 09, 2009 12:25 am; edited 1 time in total

Euclid

Posts : 95
Join date : 2009-09-15
Age : 56
Location : Alexandria

 Subject: Re: Chvátal's conjecture (1974)   Fri Oct 09, 2009 12:21 am I will evaluate the contribution of hood_A to the three stars :#Star(1)/A +#Star(2)/A +#Star(3)/A >= 4.gA wheregA = the number of gangs in the hood_AProof : Induction by the members of Hood_AIf there is an {1, 2, a} we got {1, a} and {1,2,a} in the Star(1) and {2, a} and {2, 1, a} in the Star(2)If I add a new member in the hood, the stars increase with at least four but the number of gangs with at most one new gang.Similarly, #Star(1)/D +#Star(2)/D +#Star(3)/D >= 7/2.gDa new member d produces at most two new gangs, {1, 2, d} and {2, 3, d} and increases the D stars with 1d, 12d2d, 21d, 23d3d, 32d at least sevenFor the G stars we have#Star(1)/G +#Star(2)/G +#Star(3)/G >= 9/3.gDSumming for all partial stars, (#Star(1) - #gangs) +( #Star(2)- #gangs) +( #Star(3) - #gangs) >= gA + gB + gC + 1/2 gD + 1/2 gE + 1/2gF >= 0Therefore, one of the the parenthesis terms must be greater than zero.Question:How many relations "_>" defined in A x Parts(A) such thatx_>Y ifandonlyif x is in Yare ?I mean - '_>' to be surjective to left, or- the numbers of families that cover entire A, or- what are the next numbers in the sequence 1,5,109,... ======ok, I got an answer at www.research.att.com/~njas/sequences/Seis.htmlNumber of ways to cover an n-set 1, 5, 109, 32297, 2147321017, 9223372023970362989, 170141183460469231667123699502996689125, 57896044618658097711785492504343953925273862865136528166133547991141168899281Of course, the second E.g.f. formula given in the sequences encyclopedia has a simple species explanation.Given a family of non-empty sets FAM, there are individuals covered that form a COVER and there are non-covered individuals, which form a set (ENS). FAM = COVER × ENS soCover(x) = exp(-x) * Sum(2^(2^n-1)*x^n /n!

Euclid

Posts : 95
Join date : 2009-09-15
Age : 56
Location : Alexandria

 Subject: Re: Chvátal's conjecture (1974)   Sat Oct 10, 2009 3:52 pm The issue of 2-connectors and 3-connectors revised==================A : 1 2 a cB : 3 2 a bC : 3 4 aD : 1 4 bA shell table contains only the type of connectors below1-connectors like c2-connectors, like 1,2,3,4,b and3-connectors, like aLet's note<1> the number of 1-connectors<2> the number of 2-connectors<3> the number of 3-connectors then count the (connector)-(pair of gangs) objects where the connector connect the pair of gangs.i) counted from connectors : a 1-connector do nothing, a 2-connector connect a pair of gangs, and a 3-connector connect three pairs of gangs.ii) counted from pair of gangs : each pair of gang contains at least such an object, since we are inside a shell. <2> + 3<3> >= g(g-1)/2On the other hand, the number of entries in the shell table is #entries = <1> + 2<2> + 3<3> so#entries >= g(g-1)/2Therefore, it is about distributing at least g(g-1)/2 entries to g gangs.10 to 5 ......at least one gang will have two members 15 to 6 ......at least one gang will have three members .... there is a star with 4 sets21 to 7 .....at least one gang will have three members .... there is a star with 4 sets28 to 8 .....at least one gang will have four members.... there is a star with 8 sets36 to 9 .....at least one gang will have four members.... there is a star with 8 setsfurther, the star that lies in the gang assured by Dirichlet (pigeon) will overwhelm the number of gangs.case at least 36 entries in 9 gangs worst distribution: 36 = 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4worst case : there is a {1, 2, 3, 4} and a {1, 2, 3, 5} ; #Star(1) = 12case at least 28 entries in 8 gangs This is not a "bad" case, but there are no perfect shields hereworst distribution: 28 = 4 + 4 + 4 + 4 + 3 + 3 + 3 + 3worst case : there is a {1, 2, 3, 4} and a {1, 2, 3, 5} ; #Star(1) = 12case at least 21 entries in 7 gangs worst distribution: 21 = 3 + 3 + 3 + 3 + 3 + 3 + 3 (there are no 2-connectors)worst cases : - there is a {1, 2, 3}, {1, 2, 4}, {1, 2, 5} ; #Star(1) = 8- there is a {1, 2, 3}, {1, 2, 4}, {1, 3, 4} ; #Star(1) = 7but there are no perfect shells.case at least 15 entries in 6 gangs worst distribution: 15 = 3 + 3 + 3 + 2 + 2 + 2 3+3 means there is a there is a worst case {1, 2, 3}, {1, 2, 4} ; #Star(1) = 6but there are no perfect shells.case at least 10 entries in 5 gangs worst distributions: 10 = 2 + 2 + 2 + 2 + 2 ---->2+2+2+2 is no more connected. 12 = 3 + 3 + 2 + 2 + 2 If there is a 3+3 : see above; There are no perfect shells.case at least 6 entries in 4 gangs If there is a 3+3 see above. If there is a 2=2+2+2, see above.case 9 = 3 +2 +2 +2 gives another perfect shell 1 2 3 1 2 1 3 2 3.... star (1)= 1, 12, 13, 123 four case at least 3 entries in 3 gangs another perfect shell, the well known 1 2 1 3 2 3Last edited by nick on Fri Oct 16, 2009 1:35 pm; edited 1 time in total

Euclid

Posts : 95
Join date : 2009-09-15
Age : 56
Location : Alexandria

 Subject: Exercises   Thu Oct 15, 2009 9:17 pm The construction of the 4^N perfect shells suggests some exercises.Definition :let ( a )* := { A | a belongs to A }( a or b )* := { A | a belongs to A or b belongs to A }( a and b )* := { A | a belongs to A and b belongs to A }Then, there are exercises like :( a and b )* union ( a and c )* = ( a )* intersect ( b or c )*--------------------And another one : let S be a ternary relation ( a subset of MxNxP) such that i) S( . , A , F) = S( . , B, F) = > A = B for all F in Pii) S( . , . , F) = S( . , . , G) = > F= G for all F and G in PThese are "setwise" ternary relations "- count the setwise relations- formulate the conjecture in terms of ternary relationsNote :For a finite projective geometry of order n, where we have :- each member belongs to n+1 gangs,- each gang has n+1 members,- there are n^2 + n + 1 members- there are n^2 + n + 1 gangsa direct count gives #Star(any member) = 1 + (n+1).(2^n - 1) while#gangs = n^2 + n + 1, so the star of any member is larger than the shell.Note :It seems that in the most general situation, any gang contains a pivot.

Euclid

Posts : 95
Join date : 2009-09-15
Age : 56
Location : Alexandria

 Subject: Nice Shells   Sat Oct 31, 2009 10:09 pm Under the below conditions, there are nice shells :- all members have the same connectivity k- all gangs have the same number of members d (from depth)- any couple of members occurs exactly in two gangs (there are g gangs)- any two gangs have in common exactly two members (there are m members)Counting the entries in the shell table (MG structures) we get :k.m = d.g Counting MMG structures from MM and from G points of view2. m.(m-1) /2 = d.(d-1) /2 .g Counting MGG structures from GG and M points of viewg.(g-1) /2 = m.k.(k-1) /2 - m.(m-1) /2Maple then says :d = k-2,g = k.(k-1) /2m = (k-1).(k-2) /2or d = kg = (k.k - k + 2) /2m = gTaking the connectivity k := 5, some shells really exist :For k-d-g-m = 5-3-10-6 we have { 1, 2, 3 }, { 1, 3, 4 }, { 1, 4, 5 }, { 1, 5, 6 }, { 1, 6, 2 }, { 2, 3, 5 }, { 3, 4, 6 }, { 4, 5, 2 }, { 5, 6, 3 }, { 6, 2, 4 } For k-d-g-m = 5-5-11-11 we have{ 1, 2, 3, 4, 5 },{ 1, 2, 11, 12, 14 },{ 1, 3, 14, 15, 16 }, { 1, 4, 12, 13, 16 },{ 1, 5, 11, 13, 15 },{ 2, 3, 12, 13, 15 },{ 2, 4, 11, 15, 16 }, { 2, 5, 13, 14, 16 },{ 3, 4, 11, 13, 14 },{ 3, 5, 11, 12, 16 },{ 4, 5, 12, 14, 15 }The question here is if the four initial conditions are independent.Exercise : here is a linked exercise, taken from the Putnam 2009 training.Given 2^{n-1} subsets of a set with n elements with the property that anythree have nonempty intersection, prove that the intersection of all thesets is nonempty. (German Math Olympiad, 1971)

Posts : 184
Join date : 2009-09-15
Age : 31
Location : the infinite, frictionless plane of uniform density

 Subject: Re: Chvátal's conjecture (1974)   Fri Nov 06, 2009 12:10 am Hello Nick!Here is my solution to the problem you mentioned. I heard it this morning at the Putnam preparation; it took me quite a while to figure it out, but it's so simple! Is your solution similar?Let F be the family in question, containing 2^(n-1) subsets of N={1,2,...,n}. Let P(N) be the power set of N. First we notice that given a subset A of N, either A or its complement (N-A) is in F. Indeed, since it is impossible for F to contain both A and its complement N-A, the map F --> (P(N)-F) which sends A to (N-A) is a bijection of F to its complement P(N)-F.Now I show that F is closed under intersection, and the result follows. Suppose A, B are in F, but their intersection (A int B) is not. Then its complement (N-(A int B)) must be in F, by the above. But the intersection of (N-(A int B)) with A and B is empty, which contradicts that the intersection of any three elements of F is nonempty. Therefore F is closed under intersection, and so the intersection of all the elements of F lies in F; since F does not contain the empty set, the intersection of all the elements of F is nonempty, QED.

Euclid

Posts : 95
Join date : 2009-09-15
Age : 56
Location : Alexandria

 Subject: Re: Chvátal's conjecture (1974)   Fri Nov 06, 2009 4:13 pm hi Bruno,My solution demands things to be finite. I take a set {1, 2, 3,..., k-1, k} and I ask where is (1, 2, 3,..., k-1}, in the family or in the complement ?I conclude my finite family of finite sets is closed to "subset-with-one" rather than to intersection.This allows me to link the problem to the present topic : the family is intersecting, it is a downset and we finally get a star. you should publish your solution in the topology section!

 Subject: Re: Chvátal's conjecture (1974)

 Chvátal's conjecture (1974)
 Page 1 of 1
 Similar topics
» Cyprus
» St George's Barracks
» Osnabruck Garrison closing Down.

Permissions in this forum:You cannot reply to topics in this forum
 Jump to: Select a forum||--Math Club|   |--Mathematical Sundays|   |--Suggestions|   |--Introduce yourself|   |--Mathematics|   |--Problem Solving|   |   |--Solved problems|   |   |   |--Calculus and Analysis|   |--Combinatorics|   |--Geometry|   |--Number Theory|   |--Probabilities and statistics|   |--Set theory and Topology|   |--Online Resources|   |--Chit chat    |--The Water Cooler    |--Mathematical poems