![]() | ![]() | ![]() | |
Discrete Mathematics
Several faculty members are active researchers in various areas of discrete mathematics and collaborate with colleagues in the US and around the world. Their interests include extremal problems in graph theory, finite sets, discrete and com binatorial geometry, and combinatorial number theory. Much of their research follows in the footsteps of Paul Erdös and his disciples. Other areas of research include combinatorial properties of permutations, permutation groups, the hypercube and tournaments. What follows are four open problems, each picked by a different faculty member demonstrating the broad range of their interests.
1. Is it true that every simple closed curve in the plane contains the four vertices of a square? (Toeplitz)
2. Is it true that the vertices of a graph on 4k vertices and minimal degree 2k can be covered by k vertex disjoint 4 - cycles? (Erdös and Faudree)
3. Is it true that if b1, b2, ... bm are arbitrary integers whose sum is divisible by m and a1, a2, ... a2m-1 are arbitrary integ ers, then we can permute the sequence of the ai's such that a1b1 + a2b2 + ... + ambm is divisible by m? (Alon)
4. Let A be a family of subsets of {1, 2, ... , n} with the following property: if A is an element of A and B is a subset of A, then B is an element of A. Is it true that the number of elements in a subset B of A with the property that every two sets in B have a nonempty intersection, does not exce ed the number of elements in a subset D of A having the property that all of its elements have a single number from {1, 2, ... , n} in common? (Chvatal).