Random graphs in a neural computation model

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


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 Gn,1/(kn)1/2 random graphs, where k is a fixed positive integer. For an undirected graph G = (V, E) let N(X, Y) = {v ∈ V - (X ∪ Y)| ∃x ∈ X with (v, x) ∈ E}. For fixed k construct an undirected graph G = (V, E) such that for all disjoint sets A, B ⊆ V such that |A| = |B| = k, and C = N(A, B) ∩ N(B, A), set C is such that |C| is either exactly k or as close to k as possible. Asymptotic results for large values of k are also presented.

Original languageEnglish (US)
Pages (from-to)689-707
Number of pages19
JournalInternational Journal of Computer Mathematics
Issue number6
StatePublished - Jun 2003

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Computational Theory and Mathematics
  • Applied Mathematics


  • Connectivity properties
  • Neural networks
  • Random graphs


Dive into the research topics of 'Random graphs in a neural computation model'. Together they form a unique fingerprint.

Cite this