Oct. 22 2007 2:00PM

Oct. 22 2007 3:30PM

A semi-graphoid is a combinatorial concept introduced in the 1980's in connection with probabilistic conditional independence. The final aim of this informal seminar (no transparencies, just a whiteboard) will be to refer about some results of the paper "Geometry of rank tests" by J. Morton et.al. presented at PGM'06. This will be done by detailed recalling and reinterpreting the mathematical theory behind those results.The seminar should consist of two talks; these together are aimed to be "self-contained".
In the first talk, the plan is to recall some basic facts about graded lattices and about the lattice of faces of a polytope. Then the concept of a permutohedron, which is a special polytope, will be recalled and the lattice of its faces characterized. After introducing a special (undirected) graph corresponding to the permutohedron, a one-to-one relation between semi-graphoids and certain subgraphs of that graph will be established. This is one of the results from the above mentioned paper.
In the second talk, the concept of a complete fan (of polyhedral cones) will be recalled, including basic observations about that concept. Then the concept of permutation equivalence of vectors in n-dimensional Euclidean space will be introduced. This allows one to introduce a special 'permutation fan' (of polyhedral cones). The main result is that semi-graphoids are in one-to-one correspondence with fans that coarsen the permutation fan. Note that these fans the can be interpreted as certain statistical order-tests. If time allows, the concept of the normal fan (of a polytope) will be recalled. Then a result will be recalled saying that so-called structural semi-graphoids, which were introduced in connection with the method of structural imsets, are in a one-to-one correspondence with normal fans coarsening the permutation fan.

Pravidelný seminář Inteligentní systémy (Contact person: Tomáš Kroupa)