An Associative Memory Model with Minimum Connectivity

In this paper a binary associative network model with minimal number of connections is examined and its microscopic dynamics exactly studied. The knowledge of its time behavior allows us to determine a learning rule which realizes a one-step recalling associative memory. Its storage capacity is also analyzed with randomly distributed patterns and is proved to be O(log n) in the worst case, n being the number of neurons and connections, but to increase considerably when the patterns to be memorized are correlated. Spurious states are also investigated.