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, Folkmantype problems,
cryptographic experiments, satisfiability
Computational Ramsey Theory

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.

Revisit the concept of intervals of sets introduced
in the papers [40] and
[37].
Use intervalbased onevertex extension algorithm to
try to improve various twocolor Ramsey numbers.
Design new algorithms and/or find new applications for such sets.

(proposed by Xu Xiaodong).
Let kAP stand for kterm arithmetic progression,
r_{k} (n) be the maximal cardinality of kAPfree subsets of {1,...,n},
and r_{k} (Z_{n}) be the maximal cardinality of
kAPfree subsets of Z_{n}.
If p is an odd prime, and t>1, work on the lower and
upper bounds for r_{p} (p^{t}) and
r_{p} (Z_{pt}).
We know that r_{p}(Z_{p2}) >= (p1)^{2}.
The problem is to find the value of r_{p}(Z_{p2})
for small primes p, for example 5 or 7.
Possibly, it is just (p1)^{2}.

Let T(n) denote the smallest number q such that every tournament
with at least q players contains an acyclic nplayer 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.

Work on the Ramsey number R(C_{4} , K_{9} ) .

Work on the Ramsey number R(K_{5} , K_{5}P_{3}) .

Work on the Ramsey number R(K_{5} , K_{5}e) .

Work on small offdiagonal book Ramsey numbers.
In particular try B_{3} versus B_{6} .

Revisit Ramsey numbers for K_{4}e versus
K_{6}e, K_{6}, K_{7}e
and attack K_{4}e versus K_{7} .

Work on the 3color Ramsey number R(C_{4} , C_{4} , K_{4} ) .

Work on the 3color Ramsey number R(C_{4} , K_{4} , K_{4} ) .

Work on the 4color Ramsey number R(C_{4} , C_{4} ,
C_{4} , K_{3} ) .

... more coming soon
Folkman Numbers

Study Folkman graphs in F_{e} (3,3;G)
for graphs G between K_{4}+e and K_{5}e

(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 F_{v}(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.

Work on the edge Folkman number F_{e} (3,3;4) .

Work on the vertex Folkman number F_{v} (4,4;5) .

Compute all critical graphs witnessing F_{v} (3,4;5) = 13 .

What is the order of the smallest 7 chromatic K_{4}free graph?
Does there exist a 6 chromatic K_{4}free graph on 15 vertices?

... more coming soon
Graph Theory

Generate and analyze all colorings of the edges of
complete graphs with 3 colors without monochromatic
triangles.

Study the problem of Hamiltonian paths on the middle level graph.

Graph reconstruction conjecture and numbers.

Compute clique number of Paley graphs up to 20000 vertices.

Is it feasible to compute the diameter of very large networks?

... more coming soon
Cryptography

The quest for practical
privacy preserving data mining and private information retrieval.

Getting ready for the Advanced Hash Standard, AHS 2012.

Mixed software/hardware implementations of basic
cryptographic algorithms.

... more coming soon
Design Theory

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 15701573.

... more coming soon
back to spr's main page