84:
74:
53:
22:
447:
by matrix multiplying). In the other direction, computing the transitive closure of a two-level DAG is exactly the same as multiplying matrices over the
Boolean semiring (not real numbers). So testing whether an orientation is transitive can easily be converted into testing whether a matrix product of this type has been computed correctly. —
232:
As far as I see incomparability graphs are just the complements of comparability graphs. On the article page such complements are called "string graphs". String graphs have their own article page, but there is no mention of incomparability graphs there either. Furthermore the (broken) link "Fox, J.;
446:
I think the equivalence between transitivity and matrix multiplication is in Aho, Garey, and Ullman (1972), "The transitive reduction of a directed graph", credited to earlier works by Ian Munro and some
Russian paper. But maybe that's only the forward direction (you can compute transitive closures
430:
I would expect the proof or a citation for the claimed equivalence. It is easy enough to see that one can verify a transitive orientation by considering the squared adjacency matrix of the directed graph and testing for each positive entry that the same entry is 1 in the original adjacency matrix.
208:
Gilmore and
Hoffman (1964) state and prove this theorem, but just prior to it they define a "cycle" to be a walk that returns to the starting vertex and uses each edge at most once in each direction; they don't require the cycle to be simple. So in your case, e.g., a-d-f-c-e-b-d-a is an odd cycle
423:"However, the algorithm for doing so will assign orientations to the edges of any graph, so to complete the task of testing whether a graph is a comparability graph, one must test whether the resulting orientation is transitive, a problem provably equivalent in complexity to
209:
with no triangular chords. I think probably a lot of subsequent authors quoted this result without paying attention to the strange definition. I'll see what can be done about clarifying this important point within the article. —
279:. There is no element whose neighborhood is a clique, in contrast to chordal graphs which can always be reduced to a smaller chordal graph by removing an element with a clique neighborhood. —
140:
252:
Are comparability graphs chordal? It seems to me that if you take any transitive directed graph and remove the directionality, the resulting graph must be chordal, but I may be wrong. --
275:(That is, there are two minimal elements, two maximal elements, and one element in the middle between all of them.) Its comparability graph is a five-vertex
476:
130:
229:
This concept is mentioned on the page about
Dilworth's theorem, it links here, but is not mentioned. I have just added a definition for completeness.
191:
Every cycle of odd length (i.e. length 5, since length 3 is trivial) has a triangular chord. However, the graph has no transitive orientation.
106:
471:
353:
182:
It seems to me that the property that every odd cycle has a triangular chord is not sufficient for a graph to be a comparability graph.
97:
58:
233:
Pach, J. (2009), String graphs and incomparability graphs." suggests that these are actually two different things. I am confused.
343:"That is, for a partially ordered set, take the directed acyclic graph, apply transitive closure, and remove orientation."
346:
Why do I need to apply transitive closure, I though the partial order over the set is already transitive by definition?
33:
238:
452:
408:
357:
324:
284:
214:
436:
393:
373:
267:
No. Consider the comparability graph of the five-element partial order with the Hasse diagram shown below.
432:
198:
424:
234:
168:
39:
305:
Now, 1-2-3-4 forms a cycle in the comparability graph, and that cycle has no chord. Is that right? --
83:
349:
194:
21:
448:
404:
320:
280:
210:
105:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
89:
73:
52:
389:
369:
310:
257:
419:
Citation or proof for equivalence of testing transitive orientation and matrix multiplication
164:
431:
However, I do not see why the reverse would hold and didn't find it in the literature.
465:
403:
It's clearly defined, in the article, two lines down from where it is first used. —
306:
253:
293:
Oh, ok. Thanks very much. Let me see if I understand by labeling your vertices:
276:
102:
456:
440:
412:
397:
377:
361:
328:
314:
288:
261:
242:
218:
202:
172:
79:
185:
Consider e.g. the following graph (which is the complement of a 6-cycle):
157:
Needs rework. The flow of the article does not help much to understand.
368:
Here here. I think the author means to start with the Hasse diagram?
15:
160:
I donot know why this is identified to Ordal theory.
101:, a collaborative effort to improve the coverage of
8:
347:
188:a - d /| |\ c ----- f \| |/ e - b
47:
49:
19:
7:
339:Partial order is already transitive?
95:This article is within the scope of
38:It is of interest to the following
14:
477:Low-priority mathematics articles
248:Are comparability graphs chordal?
115:Knowledge:WikiProject Mathematics
118:Template:WikiProject Mathematics
82:
72:
51:
20:
388:What is a generalized cycle??
135:This article has been rated as
1:
289:16:23, 25 February 2010 (UTC)
262:15:51, 25 February 2010 (UTC)
109:and see a list of open tasks.
472:B-Class mathematics articles
457:16:33, 9 November 2023 (UTC)
441:16:08, 9 November 2023 (UTC)
413:16:59, 2 December 2022 (UTC)
398:16:54, 2 December 2022 (UTC)
378:16:51, 2 December 2022 (UTC)
219:04:05, 17 October 2008 (UTC)
203:03:29, 17 October 2008 (UTC)
362:10:55, 3 January 2022 (UTC)
178:Incorrect characterization?
493:
299:1 3 \ / 5 / \ 2 4
271:o o \ / o / \ o o
329:07:05, 1 March 2010 (UTC)
315:06:57, 1 March 2010 (UTC)
243:14:33, 23 June 2012 (UTC)
173:01:47, 4 April 2008 (UTC)
134:
67:
46:
141:project's priority scale
98:WikiProject Mathematics
28:This article is rated
425:matrix multiplication
225:Incomparability graph
121:mathematics articles
90:Mathematics portal
34:content assessment
384:Generalized cycle
364:
352:comment added by
155:
154:
151:
150:
147:
146:
484:
235:Leen Droogendijk
123:
122:
119:
116:
113:
92:
87:
86:
76:
69:
68:
63:
55:
48:
31:
25:
24:
16:
492:
491:
487:
486:
485:
483:
482:
481:
462:
461:
421:
386:
354:193.175.238.249
341:
300:
272:
250:
227:
189:
180:
120:
117:
114:
111:
110:
88:
81:
61:
32:on Knowledge's
29:
12:
11:
5:
490:
488:
480:
479:
474:
464:
463:
460:
459:
449:David Eppstein
433:Paradoxonkatze
420:
417:
416:
415:
405:David Eppstein
385:
382:
381:
380:
340:
337:
336:
335:
334:
333:
332:
331:
321:David Eppstein
298:
297:
296:
295:
294:
281:David Eppstein
270:
269:
268:
249:
246:
226:
223:
222:
221:
211:David Eppstein
187:
179:
176:
153:
152:
149:
148:
145:
144:
133:
127:
126:
124:
107:the discussion
94:
93:
77:
65:
64:
56:
44:
43:
37:
26:
13:
10:
9:
6:
4:
3:
2:
489:
478:
475:
473:
470:
469:
467:
458:
454:
450:
445:
444:
443:
442:
438:
434:
428:
426:
418:
414:
410:
406:
402:
401:
400:
399:
395:
391:
383:
379:
375:
371:
367:
366:
365:
363:
359:
355:
351:
344:
338:
330:
326:
322:
318:
317:
316:
312:
308:
304:
303:
302:
301:
292:
291:
290:
286:
282:
278:
274:
273:
266:
265:
264:
263:
259:
255:
247:
245:
244:
240:
236:
230:
224:
220:
216:
212:
207:
206:
205:
204:
200:
196:
192:
186:
183:
177:
175:
174:
170:
166:
161:
158:
142:
138:
132:
129:
128:
125:
108:
104:
100:
99:
91:
85:
80:
78:
75:
71:
70:
66:
60:
57:
54:
50:
45:
41:
35:
27:
23:
18:
17:
429:
422:
390:DavidRideout
387:
370:DavidRideout
348:— Preceding
345:
342:
251:
231:
228:
193:
190:
184:
181:
162:
159:
156:
137:Low-priority
136:
96:
62:Low‑priority
40:WikiProjects
277:wheel graph
165:Tangi-tamma
112:Mathematics
103:mathematics
59:Mathematics
466:Categories
195:Yugu Thog
350:unsigned
307:Doradus
254:Doradus
139:on the
30:B-class
319:Yes. —
36:scale.
453:talk
437:talk
409:talk
394:talk
374:talk
358:talk
325:talk
311:talk
285:talk
258:talk
239:talk
215:talk
199:talk
169:talk
427:."
131:Low
468::
455:)
439:)
411:)
396:)
376:)
360:)
327:)
313:)
287:)
260:)
241:)
217:)
201:)
171:)
163:--
451:(
435:(
407:(
392:(
372:(
356:(
323:(
309:(
283:(
256:(
237:(
213:(
197:(
167:(
143:.
42::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
