Premium
Almost all rooted maps have large representativity
Author(s) -
Bender Edward A.,
Gao Zhicheng,
Richmond L. Bruce
Publication year - 1994
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190180603
Subject(s) - mathematics , combinatorics , embedding , enhanced data rates for gsm evolution , valency , planar graph , face (sociological concept) , surface (topology) , infinity , planar , geometry , discrete mathematics , mathematical analysis , graph , computer science , telecommunications , linguistics , social science , computer graphics (images) , philosophy , artificial intelligence , sociology
Let M be a map on a surface S . The edge‐width of M is the length of a shortest noncontractible cycle of M . The face‐width (or, representativity) of M is the smallest number of intersections a noncontractible curve in S has with M . (The edge‐width and face‐width of a planar map may be defined to be infinity.) A map is a large‐edge‐width embedding (LEW‐embedding) if its maximum face valency is less than its edge‐width. For several families of rooted maps on a given surface, we prove that there are positive constants C 1 and C 2 , depending on the family and the surface, such that1 almost all maps with n edges have face‐width and edge‐width greater than c 1 log n , and 2 the fraction of such maps that are LEW‐embeddings and the fraction that are not LEW‐embeddings both exceed n − >C2 .