Graph Orientations and Linear Extensions.
Given an underlying undirected simple graph, we consider the set of all acyclic orientations of its edges. Each of these orientations induces a partial order on the vertices of our graph, and therefore we can count the number of linear extensions of these posets. We want to know which choice of orie...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2014-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/2455/pdf |
| _version_ | 1797270278856769536 |
|---|---|
| author | Benjamin Iriarte |
| author_facet | Benjamin Iriarte |
| author_sort | Benjamin Iriarte |
| collection | DOAJ |
| description | Given an underlying undirected simple graph, we consider the set of all acyclic orientations of its edges. Each of these orientations induces a partial order on the vertices of our graph, and therefore we can count the number of linear extensions of these posets. We want to know which choice of orientation maximizes the number of linear extensions of the corresponding poset, and this problem is solved essentially for comparability graphs and odd cycles, presenting several proofs. We then provide an inequality for general graphs and discuss further techniques. |
| first_indexed | 2024-04-25T02:01:44Z |
| format | Article |
| id | doaj.art-565d3bc414bb48b7aa34d767ff1170bc |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:01:44Z |
| publishDate | 2014-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-565d3bc414bb48b7aa34d767ff1170bc2024-03-07T14:53:18ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502014-01-01DMTCS Proceedings vol. AT,...Proceedings10.46298/dmtcs.24552455Graph Orientations and Linear Extensions.Benjamin Iriarte0Department of Mathematics [MIT]Given an underlying undirected simple graph, we consider the set of all acyclic orientations of its edges. Each of these orientations induces a partial order on the vertices of our graph, and therefore we can count the number of linear extensions of these posets. We want to know which choice of orientation maximizes the number of linear extensions of the corresponding poset, and this problem is solved essentially for comparability graphs and odd cycles, presenting several proofs. We then provide an inequality for general graphs and discuss further techniques.https://dmtcs.episciences.org/2455/pdfgraph orientationlinear extensionposetcomparability graph.[info.info-dm] computer science [cs]/discrete mathematics [cs.dm][math.math-co] mathematics [math]/combinatorics [math.co] |
| spellingShingle | Benjamin Iriarte Graph Orientations and Linear Extensions. Discrete Mathematics & Theoretical Computer Science graph orientation linear extension poset comparability graph. [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co] |
| title | Graph Orientations and Linear Extensions. |
| title_full | Graph Orientations and Linear Extensions. |
| title_fullStr | Graph Orientations and Linear Extensions. |
| title_full_unstemmed | Graph Orientations and Linear Extensions. |
| title_short | Graph Orientations and Linear Extensions. |
| title_sort | graph orientations and linear extensions |
| topic | graph orientation linear extension poset comparability graph. [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co] |
| url | https://dmtcs.episciences.org/2455/pdf |
| work_keys_str_mv | AT benjaminiriarte graphorientationsandlinearextensions |