OKlibrary  0.2.1.6
Measures.hpp File Reference

Investigations regarding measurements for pigeonhole clause-sets. More...

Go to the source code of this file.

## Detailed Description

Investigations regarding measurements for pigeonhole clause-sets.

Todo:
Basic statistics
• Implemented formulas:
```for n : 0 thru 10 do block([m:n+1], print(n,nvar_php(m,n),ncl_list_weak_php(m,n),ncl_weak_php(m,n),deficiency_weak_php(m,n)));
0 0 [[0,1]] 1 1
1 2 [[1,2],[2,1]] 3 1
2 6 [[2,9]] 9 3
3 12 [[2,18],[3,4]] 22 10
4 20 [[2,40],[4,5]] 45 25
5 30 [[2,75],[5,6]] 81 51
6 42 [[2,126],[6,7]] 133 91
7 56 [[2,196],[7,8]] 204 148
8 72 [[2,288],[8,9]] 297 225
9 90 [[2,405],[9,10]] 415 325
10 110 [[2,550],[10,11]] 561 451
```
• The numbers of satisfying assignments for satisfiable instances:
```for m : 0 thru 4 do print(m,satprob_weak_php(m,m)*2^(m*m));
0 1
1 1
2 2
3 6
4 24
```
Todo:
Conflict-independence number
• Computed via
```for n : 0 thru 6 do print(n,independence_number_m_cs(weak_php_cs(n+1,n)));
0 1
1 2
2 6
3 18
4 40
5 75
6 126
```
• We should be able to figure this out; see below.
Todo:
Conflict-partition_number
• The conflict-partition_number as upper-bounded by the length of hitting_decomposition_m_cs(weak_php_cs(n+1,n)) seems to be the same as the conflict-independence number:
```for n : 0 thru 6 do print(n,partition_number_m_cs(weak_php_cs(n+1,n)));
0 1
1 2
2 6
3 18
4 40
5 75
6 126
```
• Perhaps the conflict-graph is even perfect?!
• In general: Is the hermitian deficiency actually an upper bound on the conflict-partition-number ?!?
Todo:
Hermitian rank
• Data on hermitian rank and deficiency:
```for n : 0 thru 6 do block([F:weak_php_cs(n+1,n),h],h:hermitian_rank_cs(F),print(n,h,ncl_cs(F)-h));
0 0 1
1 1 2
2 3 6
3 4 18
4 5 40
5 6 75
6 7 126
```
• We should be able to figure this out:
1. hermitian_rank(weak_php_fcs(m+1,m)) = m+1
2. hermitian_deficiency and conflict_independence_number follow suit.
• Analogously to "eigensharp", we can create a notion for clause-sets where the conflict-indepence-number equals the hermitian defect, and show that weak_php is an instance (while not being eigensharp).
Todo:
Characteristic polynomial
• Data:
```for n : 0 thru 6 do print(n, ":",charpoly_cs(weak_php_cs(n+1,n)));
0 : -x
1 : -x^3 + 2*x
2 : -x^9 + 12*x^7 - 36*x^5 + 32*x^3
3 : x^22 - 36*x^20 + 432*x^18 - 2160*x^16 + 3888*x^14
4 : -x^45 + 80*x^43 - 2400*x^41 + 34560*x^39 - 241920*x^37 + 663552*x^35
5 : -x^81 + 150*x^79 - 9000*x^77 + 280000*x^75 - 4800000*x^73 + 43200000*x^71 - 160000000*x^69
6 : -x^133 + 252*x^131 - 26460*x^129 + 1512000*x^127 - 51030000*x^125 + 1020600000*x^123 - 11226600000*x^121 + 52488000000*x^119
```
• For n >= 2 there seem to be n+2 monomials, with the powers forming an arithmetic progression with distance 2, and coefficients alternating in sign.
• These clause-sets seem to have non-zero eigenvalues of the form +- a, +- b, so that we altogether get 4 different values here?

Definition in file Measures.hpp.