Reputation
756
Next privilege 1,000 Rep.
Create new tags
Badges
1 6 20
Impact
~43k people reached

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$