Impact
~12k
people reached
- 0 posts edited
- 7 helpful flags
- 60 votes cast
Jun
4 |
comment |
Provability of unprovability
Thanks for pointing that out -- as much fun as I had fussing around with modal logic for the nonconstructive proof, it's certainly better to have an explicit example. (Is it obvious that this example works? It's been a while since I've thought about these things.) |
Jun
4 |
answered | Provability of unprovability |
Apr
17 |
comment |
Is there a Degenerate Dependency Local Lemma?
It seems to me that you can cash this out formally in terms of the assignment version of the problem by taking all $x(E_i)$ and $x(A)$ equal to $1/2$, and taking the ordering so that the center vertex is minimal. Now to satisfy the hypothesis in the question we just need all $P[E_i] \leq 1/4$ and $P[A] \leq 1/2$, which as you say is easy to arrange. |
Nov
24 |
awarded | Citizen Patrol |
Nov
22 |
awarded | Critic |
Nov
21 |
awarded | Yearling |
Nov
13 |
answered | Combinatorial Databases |
Nov
3 |
answered | Deciding whether a given graph has an f-factor or not! |
Sep
12 |
awarded | Supporter |
Aug
29 |
awarded | Necromancer |
Aug
29 |
awarded | Revival |
Aug
25 |
comment |
What is the correct statement of this Erdös-Gallai-Tuza problem generalizing Turan's triangle theorem?
@darijgrinberg: Thanks for your comments! Point taken regarding (1). As far as Lemma 2.1 goes, nothing is really gained by allowing S to be empty or to be all of V(G) (this only yields f_1(G) <= f_1(G) ). It seems a hair simpler to just keep the same hypothesis as Corollary 2.2, where the condition really is needed. |
Aug
25 |
answered | What is the correct statement of this Erdös-Gallai-Tuza problem generalizing Turan's triangle theorem? |
Mar
31 |
awarded | Good Answer |
Nov
30 |
awarded | Nice Answer |
Sep
29 |
awarded | Teacher |
Sep
29 |
answered | Ingenuity in mathematics |
Jul
21 |
awarded | Enthusiast |
May
26 |
awarded | Autobiographer |