[October, 2012] Discrepancy of Three Permutations
DIMACS researcher Alantha Newman and graduate student Aleksandar Nikolov discovered a counterexample to a long-standing a conjecture by Jozsef Beck (Rutgers) on the discrepancy of a set system arising from three permutations on the integers 1 through n. Given a set system (i.e., m sets on n elements where m is O(n)), the problem is to assign each element a value of 1 or -1 so as to minimize the maximum over all sets of the absolute value of the sum of the values assigned to its elements. This minimum is the discrepancy.   >>

[May, 2012] Mantel’s Theorem for Random Graphs
Rutgers graduate student Bobby DeMarco and his advisor Jeffry Kahn (pictured) have determined when the size of the largest triangle-free subgraph and the largest bipartite subgraph of a random graph are likely to be equal. This is the “random graph version” of a classic (1907) result by Mantel showing that the sizes are equal in a complete graph.  >>

DIMACS Home Page