Premium
Probabilistic construction of proportional graphs
Author(s) -
Janson Svante,
Spencer Joel
Publication year - 1992
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240030203
Subject(s) - probabilistic logic , random graph , mathematics , combinatorics , discrete mathematics , graph , random regular graph , pathwidth , statistics , line graph
Proportional graphs are constructed for any rational p ϵ (0, 1) by a probabilistic method: it is shown that a certain random graph may with positive probability be adjusted so as to become proportional. The construction uses a novel type of random graph, where the number of edges is fixed but, nevertheless, the edges appear independently in rather large sets of possible edges.