  Chvátal's conjecture (1974)  
 Author  Message 

nick Euclid
Posts : 95 Join date : 20090915 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 103 A collection B of subsets of an nset 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 87 An ideal (downset, simplicial complex) is a collection D of subsets of an nset 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 
   nick Euclid
Posts : 95 Join date : 20090915 Age : 56 Location : Alexandria
 Subject: Re: Chvátal's conjecture (1974) Fri Sep 25, 2009 10:56 pm  
 I got an exercise A : 1 4 5 6 7 B : 1 8 9 10 11 C : 1 2 12 13 D : 2 4 8 14 15 E : 2 3 5 9 F : 3 6 10 12 14 G : 3 7 11 13 15
Let A, B, ... be gangs The above system of gangs is a shell : every two gangs have in common exactly one member.
there are 2connectors, like 4,5,6...15 and 3connectors, like 1, 2, and 3 let's note <2> the number of 2connectors <3> the number of 3connectors
Show that generally,
If a shell has only 2connectors and 3connectors then <2> + 3<3> = gangs(gangs1)/2
in the above example the relation becomes 12 + 3.3 = 7(71)/2
==== let me note exercise.nick.2 ( it is easier than the first) ====== more general,
<2> + 3 <3> + 6 <4> + ... + n(n1)/2 <n> = gangs(gangs1)/2 
   nick Euclid
Posts : 95 Join date : 20090915 Age : 56 Location : Alexandria
 Subject: Re: Chvátal's conjecture (1974) Sat Sep 26, 2009 12:21 pm  
 ======= so ========= Let's take a 1connected shell , within every two gangs have exactly one member in common.
A : 1 2 3 4 B : 1 5 6 7 C : 1 8 9 10 D : 1 11 12 13 E : 2 5 8 11 F : 2 6 9 12 G : 2 7 10 13 H : 3 5 9 13 I : 3 7 8 12 J : 4 5 10 12 K : 4 6 8 13 L : 4 7 9 11
the 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 + (k1) frA(1) because i) A is connected with the all other gangs ii) k is the maximum connectivity ( in above example, k=4)
On the other hand, the star of 1 ( in a 1connected 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 + (k1).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 in A : 1 2 B : 1 3 C : 1 4 D : 2 3 4 In all the other cases (formula 1) is true.
===== case f = 1, when there is a {1 2} gang ============== the shell looks like this A : 1 a b B : 1 c d C : 1 e f D : 1 2  E : 2 a b c F : 2 d e f
where 1 is a kconnector, 2 is a jconnector a,b,...f are (k1).(j1) 2connectors ( 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 + (j1).( 2^(k1) 1)
here, #gangs always <= Star(2) and I think it's done for 1connected shells.
I did not count the singular members (the 1connectors) because they not affect by registering the number of gangs, and they just could increase a maximal star. 
   nick Euclid
Posts : 95 Join date : 20090915 Age : 56 Location : Alexandria
 Subject: Re: Chvátal's conjecture (1974) Sat Oct 03, 2009 12:34 am  
 A PERFECT SHELL of twentyone gangs built on six members
ab bc ac ab1 bc1 ac1 ab2 bc2 ac2 ab3 bc3 ac3 ab12 bc12 ac12 ab23 bc13 ac23 ab13 bc23 ac13
the star of a is contained in: a12b a23b a13b a12c a13c a23c, so let's list:
a a1 a2 a3 a12 a23 a13 ab a1b a2b a3b a12b a23b a13b ac a1c a2c a3c a12c a23c a13c twentyone
the star of 1 is contained in 1ab2 1bc2 1ac2 1ab3 1bc3 1ac3 that is similar with the star of a. Twentyone.
Last edited by nick on Thu Oct 08, 2009 9:23 pm; edited 1 time in total 
   nick Euclid
Posts : 95 Join date : 20090915 Age : 56 Location : Alexandria
 Subject: Re: Chvátal's conjecture (1974) Thu Oct 08, 2009 8:07 am  
 A simple case
i) all gangs have exactly three members ii) there are exactly three types of gangs
{1, 2, x} type A {2, 3, x) type B {1, 3, x) type C
The 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 Atype gang (counted in for all Atype gangs) (they must be different since {1,2,x} = {1,2,y} => x=y b = ...............................................................................B type c = ................................................................................C type d = # of members in A type, in B type but not C e = # of members in B, C but not in A f = # of members in A, C but not in A g = # of members common in an Atype, A Btype and a Ctype gang.
(I use a Venn diagram)
The total number of gangs is #gangs = a + b + c + 2.d + 2.e + 2.f + 3.g
the 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 + e
The 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 gangs Star (1) = 1, 12, 13, 1a, 12a, 13a, 123  seven sets Star(a) = a, a1, a2, a3, a12, a23, a13> seven sets
Last edited by nick on Thu Oct 08, 2009 11:06 pm; edited 1 time in total 
   nick Euclid
Posts : 95 Join date : 20090915 Age : 56 Location : Alexandria
 Subject: Re: Chvátal's conjecture (1974) Thu Oct 08, 2009 10:53 pm  
 Before Next Generalization
Let' 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,...} one hood_B contains all individuals that belongs to a {2, 3, ...} gang and not to a {1, 2, ...} or to a {1, 3,...} one hood_C contains all individuals that belongs to a {1, 3,...} gang and not to a {1, 2, ...}or to a {2, 3,...} one hood_D contains all individuals that belongs to a {1, 2, ...} and a {2, 3, ...} and not to a {1, 3,...} one hood_E contains all individuals that belongs to a {2, 3, ...} and a {1, 3, ...} and not to a {1, 2,...} one hood_F contains all individuals that belongs to a {1, 2, ...} and a {1, 3, ...} and not to a {2, 3,...} one hood_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 contains Gang_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 generalization
i) there are no visiting members ii) there are exactly three types of gangs
{1, 2, x,....} type I {2, 3, x,...) type II {1, 3, x,...) type III
Let's take an example of hood_A. Hood_A could look like this
individuals : 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 
   nick Euclid
Posts : 95 Join date : 20090915 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 where gA = the number of gangs in the hood_A Proof : Induction by the members of Hood_A If 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, 12d 2d, 21d, 23d 3d, 32d at least seven For 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 >= 0 Therefore, one of the the parenthesis terms must be greater than zero. Question:How many relations "_>" defined in A x Parts(A) such that x_>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 nset 1, 5, 109, 32297, 2147321017, 9223372023970362989, 170141183460469231667123699502996689125, 57896044618658097711785492504343953925273862865136528166133547991141168899281 Of course, the second E.g.f. formula given in the sequences encyclopedia has a simple species explanation. Given a family of nonempty sets FAM, there are individuals covered that form a COVER and there are noncovered individuals, which form a set (ENS). FAM = COVER × ENS so Cover(x) = exp(x) * Sum(2^(2^n1)*x^n /n! 
   nick Euclid
Posts : 95 Join date : 20090915 Age : 56 Location : Alexandria
 Subject: Re: Chvátal's conjecture (1974) Sat Oct 10, 2009 3:52 pm  
 The issue of 2connectors and 3connectors revised ================== A : 1 2 a c B : 3 2 a b C : 3 4 a D : 1 4 b A shell table contains only the type of connectors below 1connectors like c 2connectors, like 1,2,3,4,b and 3connectors, like a Let's note <1> the number of 1connectors <2> the number of 2connectors <3> the number of 3connectors then count the (connector)(pair of gangs) objects where the connector connect the pair of gangs. i) counted from connectors : a 1connector do nothing, a 2connector connect a pair of gangs, and a 3connector 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(g1)/2 On the other hand, the number of entries in the shell table is #entries = <1> + 2<2> + 3<3> so #entries >= g(g1)/2Therefore, it is about distributing at least g(g1)/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 sets 21 to 7 .....at least one gang will have three members .... there is a star with 4 sets 28 to 8 .....at least one gang will have four members.... there is a star with 8 sets 36 to 9 .....at least one gang will have four members.... there is a star with 8 sets further, 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 + 4 worst case : there is a {1, 2, 3, 4} and a {1, 2, 3, 5} ; #Star(1) = 12 case at least 28 entries in 8 gangs This is not a "bad" case, but there are no perfect shields here worst distribution: 28 = 4 + 4 + 4 + 4 + 3 + 3 + 3 + 3 worst case : there is a {1, 2, 3, 4} and a {1, 2, 3, 5} ; #Star(1) = 12 case at least 21 entries in 7 gangs worst distribution: 21 = 3 + 3 + 3 + 3 + 3 + 3 + 3 (there are no 2connectors) 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) = 7 but 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) = 6 but 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 3
Last edited by nick on Fri Oct 16, 2009 1:35 pm; edited 1 time in total 
   nick Euclid
Posts : 95 Join date : 20090915 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 P ii) S( . , . , F) = S( . , . , G) = > F= G for all F and G in P
These are "setwise" ternary relations "  count the setwise relations  formulate the conjecture in terms of ternary relations
Note : 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 gangs
a 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. 
   nick Euclid
Posts : 95 Join date : 20090915 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 view
2. m.(m1) /2 = d.(d1) /2 .g
Counting MGG structures from GG and M points of view
g.(g1) /2 = m.k.(k1) /2  m.(m1) /2
Maple then says :
d = k2, g = k.(k1) /2 m = (k1).(k2) /2
or d = k g = (k.k  k + 2) /2 m = g
Taking the connectivity k := 5, some shells really exist :
For kdgm = 53106 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 kdgm = 551111 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^{n1} subsets of a set with n elements with the property that any three have nonempty intersection, prove that the intersection of all the sets is nonempty. (German Math Olympiad, 1971) 
   Bruno Admin
Posts : 184 Join date : 20090915 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^(n1) 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 (NA) is in F. Indeed, since it is impossible for F to contain both A and its complement NA, the map F > (P(N)F) which sends A to (NA) 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. 
   nick Euclid
Posts : 95 Join date : 20090915 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,..., k1, k} and I ask where is (1, 2, 3,..., k1}, in the family or in the complement ? I conclude my finite family of finite sets is closed to "subsetwithone" 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! 
   Sponsored content
 Subject: Re: Chvátal's conjecture (1974)  
 
    Chvátal's conjecture (1974)  

Similar topics  

 Permissions in this forum:  You cannot reply to topics in this forum
 
 
 