Timeline for Connectivity and the minimum degree of bipartite graph
Current License: CC BY-SA 4.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 9, 2021 at 18:55 | comment | added | okw1124 | Thanks for brilliant idea! | |
| Oct 9, 2021 at 18:55 | vote | accept | okw1124 | ||
| Oct 7, 2021 at 23:21 | comment | added | Tony Huynh | Yes, and it does not matter which vertex you pick from each of $A_2, A_3, B_2, B_3$. For one of those four sets, every vertex in that set will have degree at most $\frac{n+\kappa(G)}{4}$. I re-wrote the proof to make this clearer. | |
| Oct 7, 2021 at 23:18 | comment | added | okw1124 | You mean, if we pick one vertex from each of $A_2,A_3,B_2$ and $B_3$, the minimum degree of those four vertices do not exceed $\frac{n+\kappa(G)}{4}$? | |
| Oct 7, 2021 at 23:08 | history | edited | Tony Huynh | CC BY-SA 4.0 |
added 26 characters in body
|
| Oct 7, 2021 at 23:02 | comment | added | Tony Huynh | You don't need to average over those sets. The proof shows that one of those four numbers is at most $\frac{n+\kappa(G)}{4}$. Therefore, for one of those four sets, the maximum degree of a vertex in that set is at most $\frac{n+\kappa(G)}{4}$. | |
| Oct 7, 2021 at 22:57 | comment | added | okw1124 | I have observed that, but I thought the average degree is at most $\frac{a_2(b_2+b_1)+b_2(a_2+a_1)+a_3(b_3+b_1)+b_3(a_3+a_1)}{a_2+b_2+a_3+b_3}$. Can we show this one $\leq\frac{n+\kappa(G)}{4}$? | |
| Oct 7, 2021 at 22:48 | history | edited | Tony Huynh | CC BY-SA 4.0 |
added 31 characters in body
|
| Oct 7, 2021 at 22:45 | comment | added | Tony Huynh | Just add those four numbers up and divide by 4. The sum is $2|A_1|+|A_2|+|A_3|+2|B_1|+|B_2|+|B_3|=n+\kappa(G)$. | |
| Oct 7, 2021 at 22:40 | comment | added | okw1124 | Umm...in fact, I'm struggling with showing the average degree of $A_2 \cup A_3 \cup B_2 \cup B_3$ is at most $\frac{n+\kappa(G)}{4}$. Can you give me a clue? | |
| Oct 7, 2021 at 22:38 | comment | added | Tony Huynh | @okw1124 You're welcome. If you are satisfied with the answer, please click on the green checkmark to indicate that it has been answered. | |
| Oct 7, 2021 at 22:37 | history | edited | Tony Huynh | CC BY-SA 4.0 |
deleted 4 characters in body
|
| Oct 7, 2021 at 14:56 | history | edited | Tony Huynh | CC BY-SA 4.0 |
added 17 characters in body
|
| Oct 7, 2021 at 13:47 | comment | added | okw1124 | I have sketched the same proof couple of minutes ago, but it seems your one is much more logical! Thanks a lot for giving a brilliant idea. | |
| Oct 7, 2021 at 13:40 | comment | added | Tony Huynh | Yes. I have now also added a proof that it becomes true for $a > \frac{1}{3}$. | |
| Oct 7, 2021 at 13:39 | history | edited | Tony Huynh | CC BY-SA 4.0 |
added 1003 characters in body
|
| Oct 7, 2021 at 13:20 | comment | added | okw1124 | I guess it means 'merging' each pair of vertices. Am I right? | |
| Oct 7, 2021 at 12:56 | comment | added | okw1124 | Can you explain more about 'identifying'? | |
| Oct 7, 2021 at 12:14 | history | edited | Tony Huynh | CC BY-SA 4.0 |
added 359 characters in body
|
| Oct 7, 2021 at 11:11 | history | answered | Tony Huynh | CC BY-SA 4.0 |