Matrimonial core

From InterSciWiki

On Mon, 4 Feb 2008, Michael Houseman wrote:

Date: Mon, 04 Feb 2008 16:25:20 +0100
From: Michael Houseman <houseman@attglobal.net>
To: Doug White <drwhite@uci.edu>
Subject: Riddle

Dear Douglas,
  I have a riddle to put to you. How would you rigorously describe (as in
graph theory) a matrimonial core and the largest matrimonial bicomponent for
an ore-graph (with 1 mariage arc and 2 descent arcs), or even better, for a
tip-graph (with 5 arcs: 1 mariage arc H-W and 4 descent arcs F-S, F-D, M-S,
M-D)? that is, the equivalent of what we called a "core" and the largest
bicomponent of the core for pgraphs? Any ideas?
Michael

A matrimonial core in an ore graph is the largest 2-connected graph formed by a contraction of each nuclear family into a single node with additional links between the nuclear family nodes of children and the single node of their parents.

In this graph there will be no direct links between the nuclear family nodes of siblings and no direct links between multiple marriages of the same person.

A 2-connected graph is one that cannot be disconnected with removal of 2 nodes, and a 2-connected subgraph of a graph is maximal if no additional node can be added to the subgraph and retain 2-connectity. A maximal 2-connected subgraph is equivilent to a maximal subgraph in which every pair of nodes is connected by two or more paths that have no intermediate nodes in common.

A contraction of a graph G into a graph g is a mapping of specified subsets of nodes in G into nodes in g retaining all and only the links between different nodes in different subsets. Individuals in G may belong to different nodes in g.

A nuclear family contraction of an Ore graph G (with individuals linked by marriage and by parent-child ties) defines the subsets in G to be contracted as uniquely defined by sets of children together with the same known parents. Siblings will be divided, then, into half-siblings by the mother (set 1), by the father (set 2), and full (set 3), with no overlaps and thus no links between them. The parents of the mother (set 4) and the father (set 5) are linked, respectively to sets 2,3 and 1,2, but these links do not form a 2-connected graph. Doug 13:20, 4 February 2008 (PST)

Dear Douglas,

  I was just writing below and, lo and behold, your answer came.

  I'm not sure how clear my question was, so I am trying again. In tip-graphs, where there are 5 different types of arcs (H-W,
F-S, F-D, M-S and M-D), to speak of a "bicomponent" seems a little strange. How should we formally define the equivalent to
pgraph bi-component in such graphs, what might be called a matrimonial bi-component? It seems to me that the cut-point business
is a little tricky because each individual often has two links to his/her parents which means that he/she forms a circuit with
them, and these circuits we do not want to include as providing the possible basis for inclusion within a (matrimonial)

bicomponent. HERE IS WHERE I WAS INTERRUPTED...

  So let me take it up again. Does this change with our Tip-graphs with 5 different types of arcs? And subsidiary question,
what of bridges, (between bicomponents), do they change? And finally, if I understand correctly, your answer relies on mapping
to a pgraph (basically). Do you think that there is any way to define it without the mapping-reduction?

Michael

Hmmm. No, it is the same for KinTip graphs with 5 different types of arcs: a nuclear family unit consists of either a single parent (no marriage H-W link) with his/her children, or a married pair (with a H-W link) and their children. It is the reduction or contraction that eliminates the circuits within each nuclear family.

In the contracted graph it is the bicomponents that form the matrimonial cores.

There is probably no way to do this contraction inside Pajek. Haifeng Du, Scott D. White, and myself, however, are now working with Matlab and R programs that import Pajek files and will do this sort of thing -- and more! -- and then send appropriate files back into Pajek. Proper p-graph generations, for example, as in the ancient FORTRAN program pgraph, and not done by Pajek. Permuting marriages within these generations, holding descent links constant in one gender, etcetera. Doug 14:13, 4 February 2008 (PST)