TY - JOUR

T1 - On the compatibility between a graph and a simple order

AU - Roberts, Fred S.

N1 - Funding Information:
* The results appearing in this paper are contained in the author’s doctoral dissertation in Mathematics at Stanford University, written under the direction of Professor Dana Scott. The author would like to thank Professor Scott and the other members of his dissertation committee, Professors Halsey Royden and Patrick Suppes, for their helpful comments. The research was supported in part by grants from the National Science Foundation and the National Institute of Health. This paper was begun while the author was an NIH “Postdoctoral Fellow” in the Department of Psychology at the University of Pennsylvania, and completed at The RAND Corporation. 28

PY - 1971/8

Y1 - 1971/8

N2 - Following a definition of Goodman [2], we define a notion of compatibility between an (unoriented) graph and a simple (linear) order. The notion of indifference graph, introduced in [6] for finite graphs, is extended to graphs of arbitrary cardinalities; and the graphs compatible with some simple order are characterized as precisely the indifference graphs. The uniqueness of the compatible simple order is investigated, and it is shown that there is "essentially" only one such for each indifference graph. A definition of compatibility between oriented graphs and simple orders is also introduced and the oriented graphs compatible with some simple order are characterized as the semiorders of Luce [5] and Scott and Suppes [7]. It is proved that there is essentially only one simple order compatible with each semiorder. Finally, the compatibility results are applied to solve the psychologically-motivated problem of representing a graph (oriented graph) by "just noticeable difference" intervals on the real line. In the work on infinite graphs, the Axiom of Choice is freely (and tacitly) assumed.

AB - Following a definition of Goodman [2], we define a notion of compatibility between an (unoriented) graph and a simple (linear) order. The notion of indifference graph, introduced in [6] for finite graphs, is extended to graphs of arbitrary cardinalities; and the graphs compatible with some simple order are characterized as precisely the indifference graphs. The uniqueness of the compatible simple order is investigated, and it is shown that there is "essentially" only one such for each indifference graph. A definition of compatibility between oriented graphs and simple orders is also introduced and the oriented graphs compatible with some simple order are characterized as the semiorders of Luce [5] and Scott and Suppes [7]. It is proved that there is essentially only one simple order compatible with each semiorder. Finally, the compatibility results are applied to solve the psychologically-motivated problem of representing a graph (oriented graph) by "just noticeable difference" intervals on the real line. In the work on infinite graphs, the Axiom of Choice is freely (and tacitly) assumed.

UR - http://www.scopus.com/inward/record.url?scp=0002099236&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0002099236&partnerID=8YFLogxK

U2 - 10.1016/0095-8956(71)90010-4

DO - 10.1016/0095-8956(71)90010-4

M3 - Article

AN - SCOPUS:0002099236

VL - 11

SP - 28

EP - 38

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

SN - 0095-8956

IS - 1

ER -