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
-
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 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.
-
(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.
-
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.
-
Work on the Ramsey number R(C4 , K9 ) .
-
Work on the Ramsey number R(K5 , K5-P3) .
-
Work on the Ramsey number R(K5 , K5-e) .
-
Work on small off-diagonal book Ramsey numbers.
In particular try B3 versus B6 .
-
Revisit Ramsey numbers for K4-e versus
K6-e, K6, K7-e
and attack K4-e versus K7 .
-
Work on the 3-color Ramsey number R(C4 , C4 , K4 ) .
-
Work on the 3-color Ramsey number R(C4 , K4 , K4 ) .
-
Work on the 4-color Ramsey number R(C4 , C4 ,
C4 , K3 ) .
-
... more coming soon
Folkman Numbers
-
Study Folkman graphs in Fe (3,3;G)
for graphs G between K4+e and K5-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 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.
-
Work on the edge Folkman number Fe (3,3;4) .
-
Work on the vertex Folkman number Fv (4,4;5) .
-
Compute all critical graphs witnessing Fv (3,4;5) = 13 .
-
What is the order of the smallest 7- chromatic K4-free graph?
Does there exist a 6- chromatic K4-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 1570-1573.
-
... more coming soon
back to spr's main page