On Erdős conjecture for multiplicities

Antoine Deza, Frantisek Franek, and Min Jing Liu
Advanced Optimization Laboratory
Department of Computing and Software
McMaster University, Hamilton, Ontario, Canada

---

Table 1 The combination case used for produce 7-cliques

i	combination of set
1	{7}
2	{1,6} {2,5} {3, 4}
3	{1,1,5} {1,2,4} {1, 3, 3} {2,2,3}
4	{1,1,1,4}{1,1,2,3}{1,2,2,2}
5	{1,1,1,1,3}{1,1,1,2,2}
6	{1,1,1,1,1,2}
7	{1,1,1,1,1,1,1}

Table 2 The coefficient of Si(X; F).

t	s1	s2	s3	s4	s5	s6	s7
4	7	6	1
5	15	25	10	1
6	31	90	65	15	1
7	63	301	350	140	21	1
8	127	966	1701	1050	266	28	1

Table 3 The coefficient of ki(X; F)

t	k1	k2	k3	k4	k5	k6	k7	k8
4	1	14	36	24
5	1	30	150	240	120
6	1	62	540	1560	1800	720
7	1	126	1806	8400	16800	15120	5040
8	1	254	5796	40824	126000	191520	141120	40320

 The relationship between x_i and corresponding coefficient in S_i

0 means “>”, and 1 means “=”; eg x0 > x1 = x2 > x3 then “010”

S_2			S_5
coe1	0	2	coe4	0000	120
	1	1		0001	60
S_3				0010	60
coe2	00	6		0011	20
	01	3		0100	60
	10	3		0101	30
	11	1		0110	20
S_4				0111	5
coe3	000	24		1000	60
	001	12		1001	30
	010	12		1010	30
	011	4		1011	10
	100	12		1100	20
	101	6		1101	10
	110	4		1110	5
	111	1		1111	1

Testing Result:

Table 1: Using a full family, The number of i - tuples by using two approaches:

S_i is the number of i-tuples by using the newest approaches; s_i(old) is the number of i-tuples by using the old approaches[1].

j	3	4	5	6
S1	7	15	31	63
S1(old)	7	15	31	63
S2	42	210	930	3,906
S2(old)	42	210	930	3,906
S3	210	2,730	26,970	238,266
S3(old)	210	2,730	26,970	238,266
S4	840	32,760	755,160	14,295,960
S4(old)	840	32,760	755,160	14,295,960
S5	2520	360,360	20,389,320	843,461,640
S5(old)	2520	360,360	20,389,320	843,461,640
S6	5040	3,603,600	530,122,320	48,920,775,120
S6(old)	5040	3,603,600	530,122,320	48,920,775,120
S7	5040	32,432,400	13,253,058,000	2,788,484,181,840
S7(old)	5040	32,432,400	13,253,058,000	2,788,484,181,840

c5 = 0.885833698 * 2 ^ (-9); @(10,{1,3,4,7,8,10})

	1	2	3	4
S_T	517	134970	17273850	1009617840
S’_T	506	125730	14734170	742203000

c6 = 0.744442503 * 2 ^(-14) @ (10,{1,3,4,7,8})

	1	2	3	4	5
S_T	505	125010	14562090	726780600	13191935400
S’_T	518	135726	17463606	1028265840	26106252480

c7 =0.686897717 * 2 ^ (-20) @(11,{3,4,7,8,10,11})

	1	2	3	4	5	6
S_T	1002	490050	113148090	11590147800	5.06501E+11	1.46774E+13
S’_T	1045	556842	146860362	17896958640	9.50437E+11	2.13599E+13

c8 =0.70014091 * 2 ^ (-27) @ (12,{1,3,4,7,8,11,12}) (No blue search) (Link to the select testing seed)

[1] Franek, F.: A note on Erdős conjecture on multiplicities of complete subgraphs { lower upper bound for cliques of size 6. Combinatorica, No. 3, Vol. 22, 451-454 (2002)