How many implication graphs are there for a given number of literals?
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
The context here is implication graphs over propositional literals and the 2-SAT problem. What function describes the possible number of non-redundant implication graphs given the number of literals? What I'm also trying to do is compare this quantity to the number of total graphs over the same number of literals.
logic graph-theory computer-science propositional-calculus
asked Aug 24 at 0:17
ShyPerson
975715
add a comment |Â
up vote
2
down vote
favorite
The context here is implication graphs over propositional literals and the 2-SAT problem. What function describes the possible number of non-redundant implication graphs given the number of literals? What I'm also trying to do is compare this quantity to the number of total graphs over the same number of literals.
logic graph-theory computer-science propositional-calculus
asked Aug 24 at 0:17
ShyPerson
975715
2
What makes an implication graph redundant?
– Misha Lavrov
Aug 24 at 3:37
@MishaLavrov: if it's easier to answer the question without considering redundancies, I'll take that answer. But an implication graph like $a rightarrow a rightarrow a rightarrow a rightarrow a$ seems pretty redundant.
– ShyPerson
Aug 24 at 20:55
But do you have a formal definition of redundant?
– Manuel Lafond
Aug 25 at 2:34
@ManuelLafond: Thanks for asking. Let's try this as a formal definition of redundant. Given two literals $alpha$ and $beta$, an implication graph $G$ is redundant if there is more than one occurrence of the implication $alpha rightarrow beta$ in $G$. This is to capture the underlying situation in 2-SAT where the same clause occurs more than once.
– ShyPerson
Aug 26 at 19:26
OK then. So is it true that if you have $n$ variables and so $2n$ literals, then there are $2 cdot 2n choose 2 - 2n$ possible directed edges (the $-2n$ to remove implications of the type $x rightarrow neg x$)? Then there'd be $2^2 cdot 2n choose 2 - 2n$ possible implication graphs.
– Manuel Lafond
Aug 27 at 2:31
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
The context here is implication graphs over propositional literals and the 2-SAT problem. What function describes the possible number of non-redundant implication graphs given the number of literals? What I'm also trying to do is compare this quantity to the number of total graphs over the same number of literals.
logic graph-theory computer-science propositional-calculus
asked Aug 24 at 0:17
ShyPerson
975715
The context here is implication graphs over propositional literals and the 2-SAT problem. What function describes the possible number of non-redundant implication graphs given the number of literals? What I'm also trying to do is compare this quantity to the number of total graphs over the same number of literals.
logic graph-theory computer-science propositional-calculus
asked Aug 24 at 0:17
ShyPerson
975715
asked Aug 24 at 0:17
ShyPerson
975715
asked Aug 24 at 0:17
ShyPerson
975715
asked Aug 24 at 0:17
ShyPerson
975715
975715
2
What makes an implication graph redundant?
– Misha Lavrov
Aug 24 at 3:37
@MishaLavrov: if it's easier to answer the question without considering redundancies, I'll take that answer. But an implication graph like $a rightarrow a rightarrow a rightarrow a rightarrow a$ seems pretty redundant.
– ShyPerson
Aug 24 at 20:55
But do you have a formal definition of redundant?
– Manuel Lafond
Aug 25 at 2:34
@ManuelLafond: Thanks for asking. Let's try this as a formal definition of redundant. Given two literals $alpha$ and $beta$, an implication graph $G$ is redundant if there is more than one occurrence of the implication $alpha rightarrow beta$ in $G$. This is to capture the underlying situation in 2-SAT where the same clause occurs more than once.
– ShyPerson
Aug 26 at 19:26
OK then. So is it true that if you have $n$ variables and so $2n$ literals, then there are $2 cdot 2n choose 2 - 2n$ possible directed edges (the $-2n$ to remove implications of the type $x rightarrow neg x$)? Then there'd be $2^2 cdot 2n choose 2 - 2n$ possible implication graphs.
– Manuel Lafond
Aug 27 at 2:31
add a comment |Â
2
What makes an implication graph redundant?
– Misha Lavrov
Aug 24 at 3:37
@MishaLavrov: if it's easier to answer the question without considering redundancies, I'll take that answer. But an implication graph like $a rightarrow a rightarrow a rightarrow a rightarrow a$ seems pretty redundant.
– ShyPerson
Aug 24 at 20:55
But do you have a formal definition of redundant?
– Manuel Lafond
Aug 25 at 2:34
@ManuelLafond: Thanks for asking. Let's try this as a formal definition of redundant. Given two literals $alpha$ and $beta$, an implication graph $G$ is redundant if there is more than one occurrence of the implication $alpha rightarrow beta$ in $G$. This is to capture the underlying situation in 2-SAT where the same clause occurs more than once.
– ShyPerson
Aug 26 at 19:26
OK then. So is it true that if you have $n$ variables and so $2n$ literals, then there are $2 cdot 2n choose 2 - 2n$ possible directed edges (the $-2n$ to remove implications of the type $x rightarrow neg x$)? Then there'd be $2^2 cdot 2n choose 2 - 2n$ possible implication graphs.
– Manuel Lafond
Aug 27 at 2:31
2
2
What makes an implication graph redundant?
– Misha Lavrov
Aug 24 at 3:37
What makes an implication graph redundant?
– Misha Lavrov
Aug 24 at 3:37
@MishaLavrov: if it's easier to answer the question without considering redundancies, I'll take that answer. But an implication graph like $a rightarrow a rightarrow a rightarrow a rightarrow a$ seems pretty redundant.
– ShyPerson
Aug 24 at 20:55
@MishaLavrov: if it's easier to answer the question without considering redundancies, I'll take that answer. But an implication graph like $a rightarrow a rightarrow a rightarrow a rightarrow a$ seems pretty redundant.
– ShyPerson
Aug 24 at 20:55
But do you have a formal definition of redundant?
– Manuel Lafond
Aug 25 at 2:34
But do you have a formal definition of redundant?
– Manuel Lafond
Aug 25 at 2:34
@ManuelLafond: Thanks for asking. Let's try this as a formal definition of redundant. Given two literals $alpha$ and $beta$, an implication graph $G$ is redundant if there is more than one occurrence of the implication $alpha rightarrow beta$ in $G$. This is to capture the underlying situation in 2-SAT where the same clause occurs more than once.
– ShyPerson
Aug 26 at 19:26
@ManuelLafond: Thanks for asking. Let's try this as a formal definition of redundant. Given two literals $alpha$ and $beta$, an implication graph $G$ is redundant if there is more than one occurrence of the implication $alpha rightarrow beta$ in $G$. This is to capture the underlying situation in 2-SAT where the same clause occurs more than once.
– ShyPerson
Aug 26 at 19:26
OK then. So is it true that if you have $n$ variables and so $2n$ literals, then there are $2 cdot 2n choose 2 - 2n$ possible directed edges (the $-2n$ to remove implications of the type $x rightarrow neg x$)? Then there'd be $2^2 cdot 2n choose 2 - 2n$ possible implication graphs.
– Manuel Lafond
Aug 27 at 2:31
OK then. So is it true that if you have $n$ variables and so $2n$ literals, then there are $2 cdot 2n choose 2 - 2n$ possible directed edges (the $-2n$ to remove implications of the type $x rightarrow neg x$)? Then there'd be $2^2 cdot 2n choose 2 - 2n$ possible implication graphs.
– Manuel Lafond
Aug 27 at 2:31
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Â
draft saved
draft discarded
Â
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2892674%2fhow-many-implication-graphs-are-there-for-a-given-number-of-literals%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
2
What makes an implication graph redundant?
– Misha Lavrov
Aug 24 at 3:37
@MishaLavrov: if it's easier to answer the question without considering redundancies, I'll take that answer. But an implication graph like $a rightarrow a rightarrow a rightarrow a rightarrow a$ seems pretty redundant.
– ShyPerson
Aug 24 at 20:55
But do you have a formal definition of redundant?
– Manuel Lafond
Aug 25 at 2:34
@ManuelLafond: Thanks for asking. Let's try this as a formal definition of redundant. Given two literals $alpha$ and $beta$, an implication graph $G$ is redundant if there is more than one occurrence of the implication $alpha rightarrow beta$ in $G$. This is to capture the underlying situation in 2-SAT where the same clause occurs more than once.
– ShyPerson
Aug 26 at 19:26
OK then. So is it true that if you have $n$ variables and so $2n$ literals, then there are $2 cdot 2n choose 2 - 2n$ possible directed edges (the $-2n$ to remove implications of the type $x rightarrow neg x$)? Then there'd be $2^2 cdot 2n choose 2 - 2n$ possible implication graphs.
– Manuel Lafond
Aug 27 at 2:31