Reputation
374
Top tag
Next privilege 500 Rep.
Access review queues
Badges
2 12
Newest
 Outspoken
Impact
~26k people reached

  • 0 posts edited
  • 1 helpful flag
  • 263 votes cast
Apr
26
comment The output of Kruskal's algorithm is a spanning tree
lol its not stated very well is it? it needs some induction there. the algorithm starts with a forest of 0-edge 1-vertex "trees" (1 for all vertices). every step of the algorithm increases the size of those (separate) trees (adding edges/ vertices) or joins two trees to form a new tree. at the end there is a single tree. maybe watch a visualization of it running & then try to describe why it always works in mathematical terms.
Apr
26
comment The output of Kruskal's algorithm is a spanning tree
the complete proof is on wikipedia under kruskals algorithm entry here
Apr
24
comment Tree decomposition by hand for understanding
seems to be returning a bag but having trouble following $X_{V_1}$ vs $X_V$, do you get it? fyi all chat room on this
Apr
24
comment Tree decomposition by hand for understanding
Bodlaender (oops missed edit). see also tree decomposition fastest algorithm in practice / Computer Science where the answer might indicate that the algorithm(s) have never actually been implemented (?)
Apr
24
revised Tree decomposition by hand for understanding
add cs tag
Apr
24
suggested approved edit on Tree decomposition by hand for understanding
Feb
24
comment Notable examples of “impossible” results ruled out by earlier barrier or no-go theorems or widespread beliefs
reading the wikipedia entry on Abel Ruffini thm supports your pov after "nearby" work of Lagrange in ~1770. "This innovative work by Lagrange was a precursor to Galois theory, and its failure to develop solutions for equations of fifth and higher degrees hinted that such solutions might be impossible, but it did not provide conclusive proof." however basically on problems that are open for a long time, as eg the solution of the quintic, there tends to be at least some speculation either way, eg majority/ minority opinion etc.
Feb
24
comment Notable examples of “impossible” results ruled out by earlier barrier or no-go theorems or widespread beliefs
this is hairsplitting. open problems are essentially interchangeable with conjectures. I for one conjecture there are infinitely many. :)
Feb
24
comment Notable examples of “impossible” results ruled out by earlier barrier or no-go theorems or widespread beliefs
ok good catch thx for the correction, its an open problem if/ conjectured there are infinitely many. (which shows another interesting angle to the problem that its connected to an unresolved/ open conjecture & number theory etc.)
Feb
24
answered Notable examples of “impossible” results ruled out by earlier barrier or no-go theorems or widespread beliefs
Feb
24
accepted Notable examples of “impossible” results ruled out by earlier barrier or no-go theorems or widespread beliefs
Feb
12
asked Notable examples of “impossible” results ruled out by earlier barrier or no-go theorems or widespread beliefs
Feb
3
awarded  Outspoken
Feb
3
comment Can the cube of every perfect number be written as the sum of three cubes?
surprised! nobody noticed this is a special case of eulers conjecture for cubes. it was disproved for 4th powers also. there is probably a clever computer program that can find counterexamples, at least that is how it was done for 4th powers. heres a recent blog on topic by by brian hayes
Jan
29
comment Research done by high-school students
not sure about your claim/ slightly skeptical re "the IMO doesnt give unsolved problems". is that official written policy anywhere? while thats plausible it seems not inconceivable they might throw in an occasional conjecture from somewhere esp if students are given partial credit for some real insights that fall short of solving the entire problem. agreed it is not typical research in various ways but one essence of research is to find a solution to a problem that was not previously known. fyi iirc this problem appeared in usenet sci.math around ~1989...
Jan
8
comment Research done by high-school students
Potato's comments seem off to me & seem to indicate a lack of familiarity with the field of number theory. presumably no experts volunteered to solve the problem after working on it for 6 hours, so the 6 hour limit is only a lower bound. the experts may not have thought it solvable. also number theory is rampant for problems that "look elementary" but proofs can be very difficult to find, even "elementary" ones. a famous example is finding primes between $n$ and $2n$ by Erdos. he found a new "elementary" proof that was celebrated. it maybe was not conjectured to even exist before he found it.
Sep
24
awarded  Autobiographer
Sep
18
asked looking for origin of number theory problem on 4x-floor-sqrt (maybe IMO)?
Sep
10
comment Is there a power of 2 that, written backward, is a power of 5?
seems somewhat similar to a conjecture of Erdős and Graham that the base 3 expansion of $2^n$ avoids the digit “2” for infinitely many $n$, see also some analysis by RJLipton
Sep
4
comment How to determine the number of directed/undirected graphs?
it is possible the homework is asking for the answer of number of "random graphs" disregarding identical graphs, a simpler answer using the powerset of combinatorial C(n,2). a correct answer involves graph isomorphism.