I'd like to prove a proposition true over all valid Directed Acausal Graphs. I think I can do that by starting with a graph with one node and adding either a new node and connection, or a new valid connection. This seems like it would require it's own proof, though - can someone corroborate my intuition, or else show that the proof is trivial?

  • $\begingroup$ What is your claim? $\endgroup$
    – agha
    Commented Jun 22, 2014 at 15:03
  • $\begingroup$ Does it matter? It's rather complicated to explain, but it's a function that takes a DAG and returns a boolean, so it's valid. $\endgroup$ Commented Jun 22, 2014 at 23:56
  • $\begingroup$ Of course it matters ! Being able to use the inductive hypothesis really depends on what you want to prove. If your inductive hypothesis states something like "if $D$ has property $X$, then it has property $Y$", then to use induction you have to be able to remove a vertex from your graph, and show that the graph has property $X$. If it does, then you can use induction to show it has property $Y$. But sometimes you can't guarantee property $X$ is there after removing a vertex. $\endgroup$ Commented Jun 23, 2014 at 17:10
  • $\begingroup$ Isn't that the same as starting from a lower-vertex graph and using the inductive hypothesis to show that it's true for the next step? $\endgroup$ Commented Jun 23, 2014 at 20:45
  • $\begingroup$ Anyway, the statement is something like "Given that each node of the graph is an independent random variable, show that a one-to-one correspondence exists between the product space of the variables and the space of permutations of values in the graph." That is, given a DAG of random variables, you can "pull out" the randomness and point to "the version of this graph where the random variables take on these values." $\endgroup$ Commented Jun 23, 2014 at 21:49


You must log in to answer this question.

Browse other questions tagged .