[Prev][Next][Index][Thread]

proofnets/graph theory (retore)



Date: Thu, 4 Jun 92 13:57:18 -0700
To: linear@cs.stanford.edu

I have proved an abstract graph theoretical 
result which has the following straight forward corollaries: 

the splitting times property even with the mix-rule. 
(a la Girard sequentialization, even with mix)

the splitting par property 
(a la Danos sequentialization)

So this unifies some hitherto unrelated results. 

It says a bit more when working with mix.  
Assume all conclusion are times.  Then for any  of
this times conclusions there exists a splitting times and a 
feasible path leading to this splitting times.  
Also:  assume t is a splitting times, with other splitting times 
on his right; then there exists among them at least one which is 
connected by a feasible path to t. 

The combinatorial argument consist in studying agregates of 
complete bipartite graphs, ie edge coloured graph such that 
each colour is a complete bipartite graph, and direct paths, ie paths 
using at most one edge of each colour.  

A paper has been written,  and his to be submitted 
(when polished )to a  combinatorics journal.   

Christian Retore.  
Departement de Mathematiques. 
Faculte des Sciences. 
Universite d'Angers. 
2 Boulevard Lavoisier.
49045 ANGERS cedex 

deptang@cicb.fr (collective mailbox) 
retore@logique.jussieu.fr