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
asked Nov 15 at 5:16
Richard
133
New contributor
Richard is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
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
asked Nov 15 at 5:16
Richard
133
New contributor
Richard is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
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
Nov 15 at 19:09
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
asked Nov 15 at 5:16
Richard
133
New contributor
Richard is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
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
asked Nov 15 at 5:16
Richard
133
New contributor
Richard is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Nov 15 at 5:16
Richard
133
New contributor
Richard is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Nov 15 at 5:16
Richard
133
New contributor
Richard is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Nov 15 at 5:16
Richard
133
asked Nov 15 at 5:16
Richard
133
133
New contributor
Richard is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Richard is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Richard is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
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
Nov 15 at 19:09
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
Nov 15 at 19:09
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
Nov 15 at 19:09
I must be going insane, because I swore it said $leq$. $=$ is consistent with what I believe it to be.
– Richard
Nov 15 at 19:09
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$.
answered Nov 15 at 14:26
Chris Godsil
11.5k21634
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$.
answered Nov 15 at 14:26
Chris Godsil
11.5k21634
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$.
answered Nov 15 at 14:26
Chris Godsil
11.5k21634
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$.
answered Nov 15 at 14:26
Chris Godsil
11.5k21634
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 Nov 15 at 14:26
Chris Godsil
11.5k21634
answered Nov 15 at 14:26
Chris Godsil
11.5k21634
answered Nov 15 at 14:26
Chris Godsil
11.5k21634
answered Nov 15 at 14:26
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
Nov 15 at 19:09