Celeritas
Reputation
756
Next privilege 1,000 Rep.
Create new tags
 Apr 21 revised BFS and bipartites graphs added 16 characters in body Apr 21 revised BFS and bipartites graphs edited tags Apr 21 asked BFS and bipartites graphs Apr 20 comment Question about proof for bipartite containing no odd cycles Why do you say "No"? You give the same explanation I meant. Apr 20 asked Question about proof for bipartite containing no odd cycles Apr 19 comment Question about theorem with trees What other definitions of graph are there? According to wiki there are a few but they're all equivalent en.wikipedia.org/wiki/Tree_%28graph_theory%29#Definitions Apr 19 comment Question about theorem with trees @DylanSp added to question Apr 19 revised Question about theorem with trees added 128 characters in body Apr 19 asked Question about theorem with trees Apr 19 comment What is difference between cycle, path and circuit in Graph Theory This should probably be the right answer as in the field of graph theory terminology is very not standardized. Apr 18 comment Proof that Gale-Shapley is man optimal Thanks for clearing that up. How did you know the definition of man-optimal? After google searching the only definition I could find was "E ach man receives best valid partner." which was a bit to condensed for me to digest. Apr 18 accepted Proof that Gale-Shapley is man optimal Apr 13 comment Proof that Gale-Shapley is man optimal I still don't get that. It seems like we're showing a more man-optimal solution can't exist, but that doesn't necessarily mean the one we have is man optimal (since possible there could be no man optimal solution). Apr 12 comment Proof that Gale-Shapley is man optimal That's what I don't get. How does showing that $S$ would be unstable, show that $S^*$ is man optimal? We have proven $S$ has an unstable pair but I'm still unclear how that implies $S^*$ is man-optimal. Apr 12 comment Proof that Gale-Shapley is man optimal Thanks I finally get it. It seems like the proof can be a lot shorter, for example why do they even need $S$ or $B$? e.g. Suppose GS outputed a matching that wasn't man optimal. Let $Y$ be the first man who was rejected by a valid partner $A$. Suppose $A$ preferred $Y$ to $Z$. Since $Y$ was the first man to be rejected by a valid partner, $Z$ must prefer A over all other valid partners. Therefore if $A$ was with $Y$, this would be an unstable pair. This is a contradiction because GS has been proven to always output stable matching. Apr 11 comment Proof that Gale-Shapley is man optimal So in summary this proof is showing that $S^*$ can't possibly be non-man-optimal, otherwise it would have an unstable pair? Apr 10 comment Proof that Gale-Shapley is man optimal Ok I'm still confused because $S$ has the pairs $A-Y$ and $B-Z$ but then the line reads "Z has not been rejected by any valid partner at the point when Y is rejected by A". Isn't the whole point S is better than S* because A never rejects Y? It's really unclear to me when they're talking about S vs S* Apr 10 comment Proof that Gale-Shapley is man optimal When is the $*$ used in these sorts of things? Apr 10 asked Proof that Gale-Shapley is man optimal Apr 8 comment Primality testing vs sieve @Dhruv you can use a sieve up to $\sqrt{n}$ and then test all the remaining primes to see if they divide $n$