9th November 2004
Gregory Gutin, RHUL (Computer Science)

"Some applications of graph theory, combinatorics and number theory in logistics and quantum mechanics"

The purpose of the talk is to give brief reports on two recent papers:

1. Level of Repair Analysis (LORA) is a prescribed procedure for defence logistics support planning. For a complex engineering system containing perhaps thousands of assemblies, sub-assemblies, components, etc. organized into several levels indenture and with a number of possible repair decisions, LORA seeks to determine an optimal provision of repair and maintenance facilities to minimize overall life-cycle costs. We consider the LORA optimization problem (LORAP) introduced by Barros (1998) and Barros and Riley (2001) who solved LORAP using branch-and-bound heuristics. The surprising result of this paper is that LORAP is, in fact, polynomial-time solvable. We prove it by reducing LORAP to the maximum weight independent set problem on a bipartite graph.

Joint work with A. Rafiey, A. Yeo (both RHUL) and M. Tso (UMIST)

2. A digraph $D=(V,A)$ is mediated if for each pair $x,y$ of distinct vertices of $D$ either $xy\in A$ or $yx\in A$ or there is a vertex $z$ such that both $xz,yz\in A.$ For a digraph $D$, $\Delta^-(D)$ is maximum in-degree of a vertex in $D$. The $n$th mediation number $\mu (n)$ is the minimum of $\Delta^-(D)$ over all mediated digraphs on $n$ vertices. Mediated digraphs and $\mu(n)$ are of interest in quantum mechanics. We obtain a lower bound $f(n)$ for $\mu(n)$, determine an infinite sequence of values of $n$ for which $\mu(n)=f(n)$, and show that $\mu(n)>f(n)$ for some values of $n.$ We also prove that $\mu(n)=f(n)(1+o(1))$ and conjecture that there is a constant $c$ such that $\mu(n)=f(n)+c.$ We use methods and results of graph theory, extremal finite set theory and number theory.

Joint work with A. Rafiey, A. Yeo (both RHUL), N. Jones (Bristol) and S. Severini (York)