[seqfan] Re: New or old seq: The maximum number of shift-minimal winning coalitions, 'On Dedekind's problem for complete simple games'

[Sascha Kurz]

2) Directly determining some more values of the maximum number of
shift-minimal winning coalitions is not that easy. Without using any
further tricks cliquer (http://users.tkk.fi/pat/cliquer.html - a software
package for finding cliques) will take too long.

But, Krohn and Sudhoelter have shown in "Directed majority games" (on
pages 196-198, using a result from RP Stanley "Weyl groups, the hard
Lefschetz Theorem, and the Sperner property", 1980) that the maximum
number of shift-minimal winning coalitions equals is the maximal number of
subsets of {1,2,...,n} that share the same sum.

Checking numerically whether A025591 equals indeed the maximal number of
subsets of {1,2,...,n} that share the same sum (as the comment says)
should be easy. As I understand it, a proof for the latter equality is
contained in Theorem 2.1 of Dorin Andrica and Ioan Tomescu, On an Integer
Sequence Related to a Product..., Journal of Integer Sequences, Vol. 5
(2002), Article 02.2.4

Best wishes,
Sascha

Am Di, 19.01.2010, 06:03, schrieb franktaw at netscape.net:
> 1) The comment in A025591, "If k is allowed to approach infinity, this
> gives the partition numbers A000009. " is not correct.  The maximum of this
> sequence comes (after the first few values) from a power of x greater than
> n.  It would be appropriate to have a cross reference to A000009.
>
>
> 2) It would really help if two more values were calculated for the
> game-theoretic sequence (one would be useful, but less good).  If two more
> values match, I would just add a comment "It appears that this is the same
> as ...", and include the reference.  If they don't match, of course, you
> have your answer.
>
> Equally good, of course, would be a proof that the sequences are the
> same.  You might try emailing the authors and see if they can prove
> equality.  I'm sure they would love to be able to publish it.
>
> Failing either of the above, I would add it as a new sequence, with
> appropriate cross-refs to and from A025591.  If even one more value can be
> found to match, I would probably favor just adding a comment (as above).
>
> Neil might give different answers; this is not an authoritative
> response.
>
> Franklin T. Adams-Watters
>
>
> -----Original Message-----
> From: Jonathan Post <jvospost3 at gmail.com>
>
>
> 1, 1, 2, 2, 3, 5, 8, 14, 23, 40, 70, 124, 221, 397, 722
>
>
> Table 1. The maximum number of shift-minimal winning coalitions.
>
>
> p.5 of http://arxiv.org/abs/1001.3045 On Dedekind's problem for complete
> simple games Authors: Sascha Kurz, Nikolas Tautenhahn
> Comments: 13 pages, 1 figure, 6 tables, submitted to ISSAC 2010
> Subjects: Combinatorics (math.CO)
>
>
> We combine the parametric Barvinok algorithm with a generation
> algorithm for a finite list of suitably chosen discrete sub-cases on the
> enumeration of complete simple games, i.e. a special subclass of monotone
> Boolean functions. Recently, Freixas et al. have proven an
> enumeration formula for complete simple games with two types of voters. We
> will provide a shorter proof and an enumeration formula for complete
> simple games with two shift-minimal winning coalitions.
>
> I note that this (except for a-0) agrees with
> A025591         Maximal coefficient of Product_{k<=n} (x^k+1). Number of
> solutions to +- 1 +- 2 +- 3 +- ... +- n = 0 or 1.
>
> So is this a new seq, or a comment on an old one?
>
>
>
> _______________________________________________
>
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
>
>
>
>
> _______________________________________________
>
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
>