Graphs whose every transitive orientation contains almost every relation |
| |
Authors: | Béla Bollobás Graham Brightwell |
| |
Institution: | (1) Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, 16, Mill Lane, CB2 1SB Cambridge, England |
| |
Abstract: | Given a graphG onn vertices and a total ordering ≺ ofV(G), the transitive orientation ofG associated with ≺, denotedP(G; ≺), is the partial order onV(G) defined by settingx<y inP(G; ≺) if there is a pathx=x
1
x
2…x
r=y inG such thatx
1 ≺x
j for 1≦i<j≦r. We investigate graphsG such that every transitive orientation ofG contains
2
n
−o(n
2) relations. We prove that almost everyG
n,p satisfies this requirement if
, but almost noG
n,p satisfies the condition if (pn log log logn)/(logn log logn) is bounded. We also show that every graphG withn vertices and at mostcn logn edges has some transitive orientation with fewer than
2
n
−δ(c)n
2 relations.
Partially supported by MCS Grant 8104854. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|