Chvátal's conjecture (1974)

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 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 87
An 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.

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
2-connectors, like 4,5,6...15 and
3-connectors, like 1, 2, and 3
let'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)/2

in the above example the relation becomes
12 + 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 <n> = gangs(gangs-1)/2

======= so =========
Let's take a 1-connected 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 + (k-1) 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 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 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 k-connector,
2 is a j-connector
a,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.

A PERFECT SHELL of twenty-one 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 twenty-one

the star of 1 is contained in
1ab2
1bc2
1ac2
1ab3
1bc3
1ac3 that is similar with the star of a. Twenty-one.

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 A-type gang (counted in for all A-type 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 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.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

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 }

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.gD

a 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.gD

Summing 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 Y
are ?

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.html


Number of ways to cover an n-set

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 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 so

Cover(x) = exp(-x) * Sum(2^(2^n-1)*x^n /n!

The issue of 2-connectors and 3-connectors 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
1-connectors like c
2-connectors, like 1,2,3,4,b and
3-connectors, like a

Let'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)/2
On the other hand, the number of entries in the shell table is
#entries = <1> + 2<2> + 3<3> so
#entries >= g(g-1)/2
Therefore, 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 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 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) = 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

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.

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.(m-1) /2 = d.(d-1) /2 .g

Counting MGG structures from GG and M points of view

g.(g-1) /2 = m.k.(k-1) /2 - m.(m-1) /2

Maple then says :

d = k-2,
g = k.(k-1) /2
m = (k-1).(k-2) /2

or
d = k
g = (k.k - k + 2) /2
m = g

Taking 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 any
three have nonempty intersection, prove that the intersection of all the
sets is nonempty.
(German Math Olympiad, 1971)

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.

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!