Re: Impliceren ´veel´ oplossingen een monochromatische?

Dit is een reactie op vraag 62077

Allereerst: Bedankt voor je/jullie, zoals altijd, snelle antwoord!

Ten tweede moet ik toegeven dat ik niet volledig overtuigd ben door je redenering. Want voor elke r is e·r! gewoon een constante; we kunnen voor elke r een m vinden, zodat f(m) e·r!, of meer algemeen, als g(r) een bovengrens is voor een monochrome oplossing van een bepaalde vergelijking, bestaat er een m, zodat f(m) g(r). Specifieker, ik ben aan het onderzoeken of er altijd een monochrome oplossing bestaat voor 1/x = 1/y + 1/z en de methode die ik vooraf het meest geschikt achtte, was het aantal oplossingen van die vergelijking beneden een bepaalde waarde, zeg m, afschatten en vervolgens die afschatting gebruiken om te laten zien dat er zoveel oplossingen zijn dat je niet aan één ontkomt waarbij x, y en z allen dezelfde kleur hebben. Ik heb inmiddels een resultaat geboekt waarmee ik wellicht aan kan tonen dat het aantal oplossingen m, van de orde van grootte m·log(m) is. Is het redelijk om te verwachten dat, als ik deze laatste bewering inderdaad weet te bewijzen, ik dit kan gebruiken in het bewijs dat een r-kleuring altijd een monochrome oplossing impliceert? Intiutief klinkt het namelijk geloofwaardig dat het noodzakelijk, en zeker voldoende is dat een vergelijking veel oplossingen heeft, om het bestaan van een monochrome te garanderen, maar je antwoord brengt me aan het twijfelen. Het brengt me zelfs aan het twijfelen of het ooit een goed idee is om op deze manier monochrome oplossingen voor een bepaalde vergelijking 'af te dwingen'. Een andere, maar gerelateerde vraag is de volgende: is het vraagstuk waar ik momenteel aan werk al opgelost? Want naast het boek "old and new problems and results in combinatorial number theory" van erdos en graham uit 1980 waarin de vraag gesteld wordt en een ander artikel van erdos uit 1985, kan ik geen enkel artikel vinden waar aan het probleem wordt gerefereerd. Misschien dat jullie betere toegang tot bepaalde archieven hebben of gewoon beter zijn in het opzoeken van zulke zaken, maar mij lukt het in ieder geval niet.

Beseffende dat ik weer veel van jullie vraag, wil ik in ieder geval benadrukken dat deze site echt een geweldig initiatief is en ik ben erg blij dat jullie altijd de tijd nemen om mijn, soms zeer domme, vragen te beantwoorden. Ga zo door!

Met zeer vriendelijke groeten

Wouter
Student universiteit - zondag 4 april 2010

Antwoord

In het bewijs van Schur is alleen de grootte van m van belang, zodra me·r! is weet je dat je altijd een monochrome oplossing hebt; de waarde van f(m) speelt geen rol.
Als je een kleuring hebt waarbij elke kleur even vaak voorkomt dan kun je een schatting maken van het aantal monochrome drietallen: r klassen die ongeveer even groot zijn betekent dat ze ongeveer m/r elementen hebben. Elk van die klassen heeft (m/r)³ drietallen en dat geeft in totaal m³/r² monochrome drietallen.
Het aantal `goede' drietallen is m·f(m) en als je zeker wilt zijn dat er een drietal is dat goed en monochroom is moet je er voor zorgen dat de som van m·f(m) en m³/r² groter is dan m³, ofwel f(m)m²(1-1/r²) en dat lukt niet met log(m).
Simpel tellen lijkt me niet genoeg; de structuur van de oplossingsverzameling lijkt me ook van belang.

kphart
vrijdag 9 april 2010

©2001-2024 WisFaq