Example of $omega(G times H) leq min{omega(G), omega(H)}$
up vote
2
down vote
favorite
It's written in this paper by Alon and Lubetzky that $omega(G times H) leq min{omega(G), omega(H)}$, where $omega$ denotes the clique number, and $times$ denotes the tensor product on a graph, where $((a, b), (c, d))$ is an edge in $G times H$ iff $(a, c)$ is an edge in $G$ and $(b, d)$ is an edge in $H$.
I am wondering if there are any examples to the "less than" case of this inequality. How come this isn't an equality? Suppose we take the maximum clique in $G$ and in $H$ and consider all 2-tuples representing vertices in $G times H$ composed of vertices from these cliques. Then based on the definition, by connecting all of these vertices, we can find a new clique in $G times H$ has size which is equal to the smaller of the two clique sizes. So why is there a $leq$?
graph-theory ramsey-theory
New contributor
add a comment |
up vote
2
down vote
favorite
It's written in this paper by Alon and Lubetzky that $omega(G times H) leq min{omega(G), omega(H)}$, where $omega$ denotes the clique number, and $times$ denotes the tensor product on a graph, where $((a, b), (c, d))$ is an edge in $G times H$ iff $(a, c)$ is an edge in $G$ and $(b, d)$ is an edge in $H$.
I am wondering if there are any examples to the "less than" case of this inequality. How come this isn't an equality? Suppose we take the maximum clique in $G$ and in $H$ and consider all 2-tuples representing vertices in $G times H$ composed of vertices from these cliques. Then based on the definition, by connecting all of these vertices, we can find a new clique in $G times H$ has size which is equal to the smaller of the two clique sizes. So why is there a $leq$?
graph-theory ramsey-theory
New contributor
Was the $le$ in the title of your question supposed to be a $lt$?
– bof
Nov 15 at 6:06
In the paper you linked to, the identity $omega(Gtimes H)=min{omega(G),omega(H)}$ is asserted at the top of page 2, and again a couple of lines below the statement of Conjecture 3.4. I don't have time to read the whole paper; where do they say that $omega(Gtimes H)lemin{omega(G),omega(H)}$?
– bof
Nov 15 at 6:14
I must be going insane, because I swore it said $leq$. $=$ is consistent with what I believe it to be.
– Richard
2 days ago
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
It's written in this paper by Alon and Lubetzky that $omega(G times H) leq min{omega(G), omega(H)}$, where $omega$ denotes the clique number, and $times$ denotes the tensor product on a graph, where $((a, b), (c, d))$ is an edge in $G times H$ iff $(a, c)$ is an edge in $G$ and $(b, d)$ is an edge in $H$.
I am wondering if there are any examples to the "less than" case of this inequality. How come this isn't an equality? Suppose we take the maximum clique in $G$ and in $H$ and consider all 2-tuples representing vertices in $G times H$ composed of vertices from these cliques. Then based on the definition, by connecting all of these vertices, we can find a new clique in $G times H$ has size which is equal to the smaller of the two clique sizes. So why is there a $leq$?
graph-theory ramsey-theory
New contributor
It's written in this paper by Alon and Lubetzky that $omega(G times H) leq min{omega(G), omega(H)}$, where $omega$ denotes the clique number, and $times$ denotes the tensor product on a graph, where $((a, b), (c, d))$ is an edge in $G times H$ iff $(a, c)$ is an edge in $G$ and $(b, d)$ is an edge in $H$.
I am wondering if there are any examples to the "less than" case of this inequality. How come this isn't an equality? Suppose we take the maximum clique in $G$ and in $H$ and consider all 2-tuples representing vertices in $G times H$ composed of vertices from these cliques. Then based on the definition, by connecting all of these vertices, we can find a new clique in $G times H$ has size which is equal to the smaller of the two clique sizes. So why is there a $leq$?
graph-theory ramsey-theory
graph-theory ramsey-theory
New contributor
New contributor
New contributor
asked Nov 15 at 5:16
Richard
133
133
New contributor
New contributor
Was the $le$ in the title of your question supposed to be a $lt$?
– bof
Nov 15 at 6:06
In the paper you linked to, the identity $omega(Gtimes H)=min{omega(G),omega(H)}$ is asserted at the top of page 2, and again a couple of lines below the statement of Conjecture 3.4. I don't have time to read the whole paper; where do they say that $omega(Gtimes H)lemin{omega(G),omega(H)}$?
– bof
Nov 15 at 6:14
I must be going insane, because I swore it said $leq$. $=$ is consistent with what I believe it to be.
– Richard
2 days ago
add a comment |
Was the $le$ in the title of your question supposed to be a $lt$?
– bof
Nov 15 at 6:06
In the paper you linked to, the identity $omega(Gtimes H)=min{omega(G),omega(H)}$ is asserted at the top of page 2, and again a couple of lines below the statement of Conjecture 3.4. I don't have time to read the whole paper; where do they say that $omega(Gtimes H)lemin{omega(G),omega(H)}$?
– bof
Nov 15 at 6:14
I must be going insane, because I swore it said $leq$. $=$ is consistent with what I believe it to be.
– Richard
2 days ago
Was the $le$ in the title of your question supposed to be a $lt$?
– bof
Nov 15 at 6:06
Was the $le$ in the title of your question supposed to be a $lt$?
– bof
Nov 15 at 6:06
In the paper you linked to, the identity $omega(Gtimes H)=min{omega(G),omega(H)}$ is asserted at the top of page 2, and again a couple of lines below the statement of Conjecture 3.4. I don't have time to read the whole paper; where do they say that $omega(Gtimes H)lemin{omega(G),omega(H)}$?
– bof
Nov 15 at 6:14
In the paper you linked to, the identity $omega(Gtimes H)=min{omega(G),omega(H)}$ is asserted at the top of page 2, and again a couple of lines below the statement of Conjecture 3.4. I don't have time to read the whole paper; where do they say that $omega(Gtimes H)lemin{omega(G),omega(H)}$?
– bof
Nov 15 at 6:14
I must be going insane, because I swore it said $leq$. $=$ is consistent with what I believe it to be.
– Richard
2 days ago
I must be going insane, because I swore it said $leq$. $=$ is consistent with what I believe it to be.
– Richard
2 days ago
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
accepted
The bound is always tight. To see this, first note that it’s enough to prove it when $G$ and $H$ are complete graphs and, since $K_m$ is an induced subgraph of $K_n$ (when $mle n$), it’s enough to consider the case $K_mtimes K_m$. But the subgraph induced by the diagonal of $Gtimes G$ is isomorphic to $G$, for any graph $G$.
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
The bound is always tight. To see this, first note that it’s enough to prove it when $G$ and $H$ are complete graphs and, since $K_m$ is an induced subgraph of $K_n$ (when $mle n$), it’s enough to consider the case $K_mtimes K_m$. But the subgraph induced by the diagonal of $Gtimes G$ is isomorphic to $G$, for any graph $G$.
add a comment |
up vote
0
down vote
accepted
The bound is always tight. To see this, first note that it’s enough to prove it when $G$ and $H$ are complete graphs and, since $K_m$ is an induced subgraph of $K_n$ (when $mle n$), it’s enough to consider the case $K_mtimes K_m$. But the subgraph induced by the diagonal of $Gtimes G$ is isomorphic to $G$, for any graph $G$.
add a comment |
up vote
0
down vote
accepted
up vote
0
down vote
accepted
The bound is always tight. To see this, first note that it’s enough to prove it when $G$ and $H$ are complete graphs and, since $K_m$ is an induced subgraph of $K_n$ (when $mle n$), it’s enough to consider the case $K_mtimes K_m$. But the subgraph induced by the diagonal of $Gtimes G$ is isomorphic to $G$, for any graph $G$.
The bound is always tight. To see this, first note that it’s enough to prove it when $G$ and $H$ are complete graphs and, since $K_m$ is an induced subgraph of $K_n$ (when $mle n$), it’s enough to consider the case $K_mtimes K_m$. But the subgraph induced by the diagonal of $Gtimes G$ is isomorphic to $G$, for any graph $G$.
answered 2 days ago
Chris Godsil
11.5k21634
11.5k21634
add a comment |
add a comment |
Richard is a new contributor. Be nice, and check out our Code of Conduct.
Richard is a new contributor. Be nice, and check out our Code of Conduct.
Richard is a new contributor. Be nice, and check out our Code of Conduct.
Richard is a new contributor. Be nice, and check out our Code of Conduct.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2999252%2fexample-of-omegag-times-h-leq-min-omegag-omegah%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Was the $le$ in the title of your question supposed to be a $lt$?
– bof
Nov 15 at 6:06
In the paper you linked to, the identity $omega(Gtimes H)=min{omega(G),omega(H)}$ is asserted at the top of page 2, and again a couple of lines below the statement of Conjecture 3.4. I don't have time to read the whole paper; where do they say that $omega(Gtimes H)lemin{omega(G),omega(H)}$?
– bof
Nov 15 at 6:14
I must be going insane, because I swore it said $leq$. $=$ is consistent with what I believe it to be.
– Richard
2 days ago