✦ LIBER ✦

The intersection graph of random sets

✍ Scribed by Hiroshi Maehara

Publisher: Elsevier Science
Year: 1991
Tongue: English
Weight: 369 KB
Volume: 87
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(91)90077-f

No coin nor oath required. For personal study only.

✦ Synopsis

Maehara, H., The intersection graph of random sets, Discrete Mathematics 87 (1991) 97-104.

Let X,, i=l,..., n, be n = n(N) independent random subsets of {1,2,. . , N}, each selected at random out of the 2N subsets. We present some asymptotic (N-tm) properties of {Xi}, e.g. if r~/2~'~--+ m then {Xi} contains mutually disjoint three sets, while if n/2N's+0 then {Xi} contains no such three sets, almost surely. This graph is denoted by G".

In this note we investigate the asymptotic behavior of this random graph G" as N tends to infinity. For general reference on random graphs, see, e.g. [l]. And for the intersection graphs of random intervals, random arcs on a circle, random subtrees of a tree, see, e.g. [2-41.

📜 SIMILAR VOLUMES

On set intersection representations of g

On set intersection representations of graphs

✍ Stasys Jukna 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 193 KB 👁 1 views

## Abstract The intersection dimension of a bipartite graph with respect to a type __L__ is the smallest number __t__ for which it is possible to assign sets __A__~__x__~⊆{1, …, __t__} of labels to vertices __x__ so that any two vertices __x__ and __y__ from different parts are adjacent if and only

Set intersection representations for alm

Set intersection representations for almost all graphs

✍ Eaton, Nancy; Grable, David A. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 581 KB

Two variations of set intersection representation are investigated and upper and lower bounds on the minimum number of labels with which a graph may be represented are found that hold for almost all graphs. Specifically, if &(G) is defined to be the minimum number of labels with which G may be repre

Some intersection theorems for ordered s

Some intersection theorems for ordered sets and graphs

✍ F.R.K Chung; R.L Graham; P Frankl; J.B Shearer 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 642 KB

Independent sets in random sparse graphs

✍ Pedro G. Gazmuri 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 418 KB

Intersections of graphs

✍ Béla Bollobás; Alex Scott 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 193 KB

Let G and H be two graphs of order n. If we place copies of G and H on a common vertex set, how much or little can they be made to overlap? The aim of this article is to provide some answers to this question, and to pose a number of related problems. Along the way, we solve a conjecture of Erd" os,

On the intersection rank of a graph

✍ James A. Wiseman 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 748 KB

Wiseman, J.A., On the intersection rank of a graph, Discrete Mathematics 104 293-305.