Topics and problems to work on

*** this is little out of date, just come talk to me ***

The areas, topics and problems listed below include those suitable for projects under my supervision, which can be undergraduate independent studies, graduate independent studies, MS capstone projects, MS theses, doctoral level research, Ph.D. dissertation subjects, and problems to work on over the weekend for fun. Just ask me how to adjust your favorite choice so it fits your needs. If your favorite topic is not yet on my list convince me to include it.

Areas:

combinatorial computing, algorithms, cryptography, complexity, graph theory, design theory

Topics in:

computational Ramsey theory, Folkman-type problems, cryptographic experiments, satisfiability


Computational Ramsey Theory

  1. Some Ramsey Problems Involving Triangles - Computational Approach, a talk given at the Ramsey Theory workshop on May 28, 2009, Rutgers University, DIMACS. Here are the slides from the talk, and the associated set of problems.

  2. Revisit the concept of intervals of sets introduced in the papers [40] and [37]. Use interval-based one-vertex extension algorithm to try to improve various two-color Ramsey numbers. Design new algorithms and/or find new applications for such sets.

  3. (proposed by Xu Xiaodong). Let k-AP stand for k-term arithmetic progression, rk (n) be the maximal cardinality of k-AP-free subsets of {1,...,n}, and rk (Zn) be the maximal cardinality of k-AP-free subsets of Zn. If p is an odd prime, and t>1, work on the lower and upper bounds for rp (pt) and rp (Zpt). We know that rp(Zp2) >= (p-1)2. The problem is to find the value of rp(Zp2) for small primes p, for example 5 or 7. Possibly, it is just (p-1)2.

  4. Let T(n) denote the smallest number q such that every tournament with at least q players contains an acyclic n-player subtournament. Find values of T(n), upper and lower bounds, and asymptotic behavior. Apparently important in voting theory. The smallest open case is 31 < T (7) < 55.

  5. Work on the Ramsey number R(C4 , K9 ) .
  6. Work on the Ramsey number R(K5 , K5-P3) .
  7. Work on the Ramsey number R(K5 , K5-e) .
  8. Work on small off-diagonal book Ramsey numbers. In particular try B3 versus B6 .
  9. Revisit Ramsey numbers for K4-e versus K6-e, K6, K7-e and attack K4-e versus K7 .
  10. Work on the 3-color Ramsey number R(C4 , C4 , K4 ) .
  11. Work on the 3-color Ramsey number R(C4 , K4 , K4 ) .
  12. Work on the 4-color Ramsey number R(C4 , C4 , C4 , K3 ) .
  13. ... more coming soon


Folkman Numbers

  1. Study Folkman graphs in Fe (3,3;G) for graphs G between K4+e and K5-e

  2. (proposed by Xu Xiaodong). Take a graph G giving a good lower bound for the Ramsey number R(k,3). Search for an upper bound on vertex Folkman numbers witnessed by this graph. For instance, let G be a (15,3) graph of order 72 showing R(3,15) > 72. For 2 < a <= b < 15, test if G -> (a,b)v, so possibly we obtain Fv(a,b;15) <= 72. For each fixed b compute the largest a such that G -> (a,b)v. This and other similar computations may produce a table of upper bounds for vertex Folkman numbers extending the currently known data.

  3. Work on the edge Folkman number Fe (3,3;4) .
  4. Work on the vertex Folkman number Fv (4,4;5) .
  5. Compute all critical graphs witnessing Fv (3,4;5) = 13 .
  6. What is the order of the smallest 7- chromatic K4-free graph?
    Does there exist a 6- chromatic K4-free graph on 15 vertices?
  7. ... more coming soon


Graph Theory

  1. Generate and analyze all colorings of the edges of complete graphs with 3 colors without monochromatic triangles.
  2. Study the problem of Hamiltonian paths on the middle level graph.
  3. Graph reconstruction conjecture and numbers.
  4. Compute clique number of Paley graphs up to 20000 vertices.
  5. Is it feasible to compute the diameter of very large networks?
  6. ... more coming soon


Cryptography

  1. The quest for practical privacy preserving data mining and private information retrieval.
  2. Getting ready for the Advanced Hash Standard, AHS 2012.
  3. Mixed software/hardware implementations of basic cryptographic algorithms.
  4. ... more coming soon


Design Theory

  1. Decide the existence of 11- (24,12,1) Steiner systems.
    Decide the existence of 10- (23,11,1) Steiner systems.
    Decide the existence of 9- (22,10,1) Steiner systems.
    Decide the existence of 8- (21,9,1) Steiner systems.
    Decide the existence of 7- (20,8,1) Steiner systems.
    Decide the existence of 6- (19,7,1) Steiner systems.
    Decide the existence of 5- (18,6,1) Steiner systems.
    Decide the existence of 4- (17,5,1) Steiner systems.

    Hm, none of the above exist as shown by Ostergard and Pottonen,
    Journal of Combinatorial Theory A, vol 115 (8), November 2008, pp 1570-1573.
  2. ... more coming soon



back to spr's main page