[Humanist] 31.273 combinatorics

Humanist Discussion Group willard.mccarty at mccarty.org.uk
Thu Aug 31 07:29:45 CEST 2017


                 Humanist Discussion Group, Vol. 31, No. 273.
            Department of Digital Humanities, King's College London
                       www.digitalhumanities.org/humanist
                Submit to: humanist at lists.digitalhumanities.org

  [1]   From:    riddella at indiana.edu                                      (30)
        Subject: Re: [Humanist] 31.270 combinatorics?

  [2]   From:    Marinella Testori <testorimarinella at gmail.com>            (52)
        Subject: Re:  31.270 combinatorics?

  [3]   From:    Leonardo Impett <li222 at cam.ac.uk>                         (96)
        Subject: Re:  31.270 combinatorics?


--[1]------------------------------------------------------------------------
        Date: Wed, 30 Aug 2017 09:45:38 -0400
        From: riddella at indiana.edu
        Subject: Re: [Humanist] 31.270 combinatorics?
        In-Reply-To: <93e6d467b7664af99d941f035168083a at bl-cci-exch06.ads.iu.edu>

Text-reuse and paraphrase detection strike me as good examples. These
happen to be related to the task of sequence alignment in genomics --
which is another example worth mentioning outside the humanities and
interpretive social sciences.

Best wishes,

Allen Riddell

On 08/30/2017 09:31 AM, Humanist Discussion Group wrote:
>                  Humanist Discussion Group, Vol. 31, No. 270.
>             Department of Digital Humanities, King's College London
>                        www.digitalhumanities.org/humanist
>                 Submit to: humanist at lists.digitalhumanities.org
> 
> 
> 
>         Date: Wed, 30 Aug 2017 14:13:45 +0100
>         From: Willard McCarty <willard.mccarty at mccarty.org.uk>
>         Subject: combinatorics?
> 
> 
> I am looking for an explanation of the intellectual reach of 
> combinatorics with examples of the kinds of non-mathematical problems it 
> can deal with and what the outcomes are like. Chess and go are, I'd 
> suppose, obvious examples, but what about problems in the humanities and 
> interpretative social sciences?
> 
> Any help, references, suggestions would be most welcome.
> 
> Yours,
> WM
> 



--[2]------------------------------------------------------------------------
        Date: Wed, 30 Aug 2017 22:12:56 +0200
        From: Marinella Testori <testorimarinella at gmail.com>
        Subject: Re:  31.270 combinatorics?
        In-Reply-To: <20170830133140.DEAA67713 at digitalhumanities.org>


Dear Willard,

In the article 'The Changing Relations between Grammar, Rhetoric and Music
in the Early Modern Period' by David Cram (In 'The Making of the
Humanities', vol. 1 Early Modern Europe, edited by Rens Bod et al.,
Amsterdam University Press, 263-282 and particularly 271-272), you can find
a contribution about the *ars combinatoria *(combinatorics) in its relation
with theories of language and aesthetics.

The volume 'The Making of the Humanities' can be found on Google Books.

I hope this may be of your interest.

Kind regards,
Marinella



--[3]------------------------------------------------------------------------
        Date: Wed, 30 Aug 2017 20:28:45 +0000
        From: Leonardo Impett <li222 at cam.ac.uk>
        Subject: Re:  31.270 combinatorics?
        In-Reply-To: <20170830133140.DEAA67713 at digitalhumanities.org>


Dear Prof. McCarty,

I studied elements of combinatorics under Bernard Moret (recently retired,
but perfectly contactable), a professor of computational biology and
(especially graph-based) algorithm theory at the EPFL.

He would often use social or historical examples as instances of
combinatorics: (especially randomized) graph-theoretical and algorithmic
results. Computer-science textbooks also often do this, with social or
organisational-logistical networks serving as common examples (distributing
toys to children, and so on) - the difference to Moret's point of view was
that the combinatorial result could somehow inform our understanding of the
original example.

I can think of two or three examples - but surely the most memorable is the
'Stable Marriage' problem (a well-studied combinatorial problem, see here
<https://en.wikipedia.org/wiki/Stable_marriage_problem>).

The problem is to pair off a set of men and a set of women, such that there
are no 'unstable' pairs - that is to say, where woman A prefers man B to
man A, and man B prefers woman A to woman B (i.e. the A-A and B-B pairs
would be broken by some presumed philandering). Note that there doesn't
have to be a universal definition of 'desirability' here - each person
(male and female) has a list, ordered by preference, of the members of the
opposite sex, and their task is to end up with the highest-ranked place on
their own (personal) list.

In general, several such stable matchings exist. The classical algorithm to
solve this is for the men to do all the proposing, and the women to accept
and reject. If a woman were to get a better offer at a later time, she
ditches her previous suitor - men, on the other hand, all start by asking
the most desirable girls and work their way down as they get rejected.

*"Readers will recognize this algorithm as the prevailing social custom in
Western civilization for many centuries (up to the 19th century and even
later): women could not make a move of their own (although they could
certainly drop hints!), but had to wait on the pleasure of men to declare
themselves. Unsurprisingly, like much about human civilizations, this
proposal algorithm is optimal for men; it is also pessimal for women.*"
(from the typed lecture notes -
http://lcbb.epfl.ch/algs16/notes/notes-04-05.pdf ). In other words: there
are many possible stable matchings, but this classical algorithm (which to
us resembles a debutante's ball) gives the most male-optimal, and also the
most female-pessimal, matching from this set of possible solutions.

It's absolutely not intuitively obvious, from how the problem is set up
(men doing the proposing, women being able to accept a better offer later),
that the resulting outcome is skewed in favour of men - never mind that it
is also the best possible result for men and the worst possible result for
women. And yet the proof is mathematically quite simple, a very good
instance of combinatorial calculations on a bipartite graph, and tells us
something quite important about the situation itself.

Another one that comes to mind is whether a King should let his advisers
talk to each other for good advice, for instance. They shouldn't: even if
each of them makes a better decision because of the greater evidence,
overall the decision will be worse.

Kind regards, with apologies for the long email,

Leo

Leonardo Impett
PhD Candidate, Computer Science
Image and Visual Representation Lab
EPFL


More information about the Humanist mailing list