Random Graphs In A Neural Computation Model

We examine in this work the following graph theory problem that arises in neural computations that involve the learning of boolean expressions by studying the asymptotic connectivity properties of $G_{n\comma 1/\lpar kn\rpar ^{1/2}}$ random graphs, where k is a fixed positive integer. For an undirected graph $G = \lpar V\comma \; E\rpar $ let $N\lpar X\comma \; Y\rpar = \lcub v \in V - \lpar X \cup Y\rpar \!\mid$ $ \exists x \in X\ \hbox{with}\ \lpar v\comma \; x\rpar \in E\rcub $ . For fixed k construct an undirected graph $G = \lpar V\comma \; E\rpar $ such that for all disjoint sets $A\comma \; B \subseteq V$ such that $\vert A \vert = \vert B \vert = k$ , and $C = N\lpar A\comma \; B\rpar \cap N\lpar B\comma \; A\rpar $ , set C is such that $\vert C \vert$ is either exactly k or as close to k as possible. Asymptotic results for large values of k are also presented.

Keywords:

• Random Graphs
• Connectivity Properties
• Neural Networks