All Questions
Tagged with order-theory graph-theory
103
questions
2
votes
0
answers
50
views
Converting "improper" partial order to total order
I suspect that if I knew what to search for, this would be easy to find an answer to, but I don't know what the proper name is for the input portion of the problem statement.
I have a set and a ...
- 663
2
votes
0
answers
63
views
Necessary and sufficient conditions for finding graphs based on posets
Let $\Gamma$ be any graph (say finite, simple, undirected), then denote by $P(\Gamma)$ the set of all non-isomorphic subgraphs of $\Gamma$. Let $\gamma$ be another graph, then denote $\gamma \subseteq ...
- 967
0
votes
0
answers
34
views
Definition for orders corresponding to directed acyclic graphs (DAG)
My question
What is the name for a binary relation $R$ on $V$ that corresponds to a graph $G = (V,E)$ that is a directed acyclic (simple) graph?
Background
There is a bijection between simple directed ...
- 414
0
votes
0
answers
30
views
Well-founded Relation on infinite DAGs
A well-founded relation on set $X$ is a binary relation $R$ such that for all non-empty $S \subseteq X$
$$\exists m \in S\colon \forall s \in S\colon \neg(s\;R\;m).$$
A relation is well-founded when ...
- 83
0
votes
0
answers
19
views
$P = (X, \leq)$ ... vertex-edge partial order of the graph $W_4$, $\text{dim}(P)$=?
Let $P = (X, \leq)$ be a vertex-edge partial order of the graph $W_4$. Calculate $\text{dim}(P)$.
All the theory we have covered:
Let $G$ be a graph. The vertex-edge incidence partial order $P = (X, \...
user1308280
0
votes
1
answer
60
views
Contraction, loops and flats.
This idea is being used a lot, but I cannot justify why it is correct:
If M is a matroid and $T$ a subset of $E(M).$ Then $M/T$ has no loops iff $T$ is a flat of $M.$
I know how to proof that in a ...
- 3,127
-1
votes
1
answer
52
views
what will happen if we contract an element in a uniform matroid? [closed]
Are the parallel elements in a matroid just behaving like loops? If so, why?
For example, in $U_{2,3}$ if we contract an element what will happen? In $U_{2,2}$ if we contract an element what Will ...
- 95
2
votes
1
answer
87
views
Partition lattice properties and an invariant.
I am trying to guess the value of the beta invariant of the partition lattice $\pi_4$ if I know the following information:
For any matroid $M,$ I know that
1- $\beta(M) \geq 0.$
2- $\beta(M) > 0$ ...
- 95
1
vote
0
answers
36
views
Does this bowtie shaped digraph define a semilattice in the sense of Hasse diagram?
I apologise for the bad formatting.
Motivation:
In my research, I have developed some ideas to do with semilattices. I regard them each as a set $L$ under an associative, commutative, idempotent ...
- 45.8k
2
votes
1
answer
68
views
A poset $P$ is series-parallel iff it contains no subset isomorphic to $Z_4$
I'm trying to prove that a finite poset is series-parallel (i.e. it can be built up from a one-element poset using disjoint union and ordinal sum of posets) iff it contains no subset isomorphic to $...
- 114
-1
votes
1
answer
24
views
Prove that if A is a finite non-empty partial order set and it has a unique maximal element, then it is the greatest element (proof by contradiction) [closed]
I was given this question as an extra question on the lecture notes. I had been thinking about this question for the past 2 weeks but to no avail. Before making this post, I have scoured through ...
- 1
0
votes
1
answer
19
views
Antipath in regard to a graph of transitive closure
I'm in the process of reading a paper that deals with graphs and their cliques. In the paper it uses graphs $G=(X,\Gamma)$ and their graph of transitive closure $G_t$. It then states:
It is not worth ...
- 413
1
vote
0
answers
39
views
How many small polls are required to fully order a set of elements?
Problem
Imagine you have some set of $N$ elements (say, movies), and group of people who collectively have a complete ranking of these movies. You can poll them with a subset of the movies to see how ...
- 991
3
votes
1
answer
229
views
Is there any way to quickly check if a partial order is transitive?
Is there any fail safe and quick way to check if a partial order $\preceq$ on a set $A$ is transitive without checking through trial and error?
0
votes
0
answers
158
views
topological sort and parallel task scheduling
I was reading MIT's reading notes on relations and partial orders. In doing so I came across a section which said that because posets have topological sort, it will helps us in executing tasks ...
- 23