Hostname: page-component-745bb68f8f-b6zl4 Total loading time: 0 Render date: 2025-02-11T00:00:35.542Z Has data issue: false hasContentIssue false
  • English
  • Français

On Random Intersection Graphs: The Subgraph Problem

Published online by Cambridge University Press:  01 January 1999

MICHAŁ KAROŃSKI ,
EDWARD R. SCHEINERMAN  and
KAREN B. SINGER-COHEN
MICHAŁ KAROŃSKI
Affiliation:
Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznán, Poland and Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA (e-mail: karonski@math.amu.edu.pl and michal@mathcs.emory.edu)
EDWARD R. SCHEINERMAN
Affiliation:
Department of Mathematical Sciences, The Johns Hopkins University, Baltimore, MD 21218–2689, USA (e-mail: ers@cs.jhu.edu)
KAREN B. SINGER-COHEN
Affiliation:
Department of Mathematical Sciences, The Johns Hopkins University, Baltimore, MD 21218–2689, USA and School of Mathematics, University of Minnesota, Minneapolis, MN 55455, USA (e-mail: singer@math.umn.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A new model of random graphs – random intersection graphs – is introduced. In this model, vertices are assigned random subsets of a given set. Two vertices are adjacent provided their assigned sets intersect. We explore the evolution of random intersection graphs by studying thresholds for the appearance and disappearance of small induced subgraphs. An application to gate matrix circuit design is presented.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 8 , Issue 1-2 , January 1999 , pp. 131 - 159
Copyright
© 1999 Cambridge University Press