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)