Abstract-Ges tre permutationer på heltal 1 till n, överväga det inställda systemet som består av varje intervall i var och en av de tre permutationer. 1982 antog Beck att skillnaden i detta set system är O(1). Med andra ord, gissningen säger att varje heltal från 1 till n kan färgas antingen rött eller blått så att antalet röda och blå heltal i varje intervall av varje permutationer skiljer sig endast med en konstant. (Skillnaden i ett fastställt system baserat på två permutationer är högst två.) Vårt huvudsakliga resultat är ett motexempel på denna hypotes: för alla positiva heltal n = 3 k, Vi konstruerar tre permutationer vars motsvarande set system har diskrepans  och (log n). Vårt motexempel är baserat på en enkel rekursiv konstruktion, och vårt bevis på avvikelsen lägre gräns är genom induktion. Denna konstruktion motbevisar också en generalisering av Becks gissningar på grund av Spencer, Srinivasan och Tetali, som förmodade att ett set system som motsvarar permutationer har diskrepans O ( ε ). Vårt arbete inspirerades av ett spännande papper från SODA 2011 av Eisenbrand, Pálvölgyi och Rothvoß, som visar en överraskande koppling mellan skillnaden mellan tre permutationer och bin förpackningsproblem: De visar att Beck förmodar innebär en konstant värsta fall bunden på additiv integrality gap för Gilmore-Gomory LP avslappning för bin förpackning i specialfallet när alla objekt har storlekar strikt mellan 1/4 och 1/2, även känd som de tre partition problem. Vårt motexempel visar att detta tillvägagångssätt för att begränsa den additiva integrality gap för bin förpackning inte kommer att fungera. Vi kan dock visa en intressant inverkan av vår konstruktion i omvänd riktning: det finns exempel på bin förpackning och motsvarande optimala grundläggande genomförbara lösningar för Gilmore-Gomory LP avslappning så att varje förpackning som innehåller endast mönster från stödet för dessa lösningar kräver minst opt +  och (log m) behållare, där m är antalet objekt. Slutligen diskuterar vi några konsekvenser som vår konstruktion har för andra områden av diskrepansteori.
Å andra sidan visade sig diskrepansen för k = 3 nyligen vara  och (log n) REF som motbevisade en gissning om Beck.
Beck's Three Permutations Conjecture: A Counterexample and Some Consequences
{'venue': '2012 IEEE 53rd Annual Symposium on Foundations of Computer Science', 'journal': '2012 IEEE 53rd Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}