Monthly Archives: August 2011

Alantha Newman and Alexandar Nikolov Disprove Beck’s 3-Permutations Conjecture

Posted on August 29, 2011 by

Alantha Newman and Alexandar Nikolov disproved a few months ago one of the most famous and frustrating open problem in discrepancy theory: Beck’s 3-permutations conjecture. Their paper  A counterexample to Beck’s conjecture on the discrepancy of three permutations is already on … Continue reading →

Posted in Combinatorics | Tagged | Leave a comment

Discrepancy, The Beck-Fiala Theorem, and the Answer to “Test Your Intuition (14)”

Posted on August 28, 2011 by

The Question Suppose that you want to send a message so that it will reach all vertices of the discrete -dimensional cube. At each time unit (or round) you can send the message to one vertex. When a vertex gets the … Continue reading →

Posted in Combinatorics, Test your intuition | Tagged , | 7 Comments

Test Your Intuition (14): A Discrete Transmission Problem

Posted on August 4, 2011 by

Recall that the -dimensional discrete cube is the set of all binary vectors ( vectors) of length n. We say that two binary vectors are adjacent if they differ in precisely one coordinate. (In other words, their Hamming distance is 1.) This … Continue reading →

Posted in Combinatorics, Test your intuition | Tagged , | 35 Comments