BSM-TDK — Research Opportunities

COURSE DESCRIPTION

This course is designed in the style of the Hungarian "TDK" system, allowing advanced undergraduates to become acquainted with research methods and means in detail and acquire additional knowledge beyond their obligatory curriculum. (For a brief English description of the TDK system see a relevant ELTE University homepage.)

In this course, a student can choose from the topics/problems listed below and work with other students and the professor to solve the given problem. All work is summarized in a paper and during the semester there will be opportunities to present your work as well.

This may contribute to the successful beginning of a scientific career: depending on level, the results obtained can be presented at school, statewide or national undergraduate meetings ranging from a local Undergradute Seminar at your home school to MAA's MathFest. Papers may also be published in undergraduate research journals. (such as The Rose-Hulman Undergraduate Mathematics Journal or Involve.

In some US PhD programs, fruitful undergraduate reserach activity is a prerequisite for admission.

At BSM student research is supervised by professors. Research topics are offered by them, but students can also propose topics of their own interest.

COURSE LOGISTICS

The list of research topics and professors proposing them can be seen below. Contact the professor whose problem you are interested in at the Welcome Party, but read everything carefully below first.

• Who can participate? Each professor gave a list of problems and/or some reading and related tasks for those who are interested in working on their problem. If you are interested in participating, do these by the first week (the exact deadline will be discussed with the professor at the Welcome Party or by email). Final enrollment will be based on your work on these problem sets/reading assignments.
• Which topics will actually be offered ("stay alive")? Of the initially offered research topics those will be offered eventually, for which a group of students sign up and are accepted by the Professor based on first week performance as outlined above.
• Course work: weekly meetings. The research groups will meet 3-4 times weekly, two hours each.
  Two meetings are devoted to group work, when you discuss the problem and possible solutions with your student group without the professor. The other meetings of the week are spent with your professor who will monitor your group's progress. Whether you meet once or twice with your Professor on a given week will be decided case-by-case, depending on progress.
• Course work: presentation. Work continuous thrughout the Summer Session. The 5th week each research group should present their results at a "Preliminary report session" organized for all BSM-TDK participants, their professors and everyone else interested.
• Course work: writing a paper. Depending on results obtained all work will be summarized in a paper/research report.

PROBLEMS FOR SUMMER 2015:

1. Title: Extremal sets of the vertices of the hypercube (zero sum subsets of a finite sum)
   
   Description: We plan to investigate (cases of) the following general question: How many vertices (maybe of certain further property, like of fixed weight) of the n-dimensional hypercube can be picked such that subspace spanned by them - over GF(2) or R - does not contain or does not intersect certain configurations of the hypercube (vertices, vertices of given weight, subspaces, hyperplanes, etc.) In particular we will focus on the folowing unsolved question: How many vertices of the hypercube can be picked such that subspace sapnned by them (over R or GF(2)) avoids ALL vertices of weight 2? The real case translates into the following subsum question: what is the maximum number of zero subsums of a finite set of real numbers if no two of thwm sums up to 0?
   
   In this project you will understand the structure of the hypercube over the reals and GF(2), develop algebraic methods to solve extremal set theoretical problems and establish constructions and will reach - in the worst case - some concrete results.
   
   Prerequisites: basic combinatorics and linear algebra
   Best for: students who intend to do research in algebra or combinatorics
   Professor: Dr. Dezsô Miklós
   ASSIGNMENT FOR THE FIRST WEEK: prior the first meeting of the course: think over the question and come up with a conjecture. Read this related article (and find the conjecture, should you fail to come up with one)
   
   
2. Title: First passage times
   
   Description: Many phenomena including diffusion, neuron firing, or the triggering of stock options are driven by stochastic processes and their first hitting times (also called first passage times). These hitting times are the times when the random process reaches a certain threshold. The determination of these hitting times requires the solution of certain partial differential equations associated to the random process.
   
   The disctretization of these processes lead to interesting random walks on graphs. In this project you would develop methods to explore and exploit these connections and develop tools for fast computations of first passage times.
   
   Prerequisites: strong calculus and linear algebra skills, complex numbers, basic probability
   Best for: students who would like to do research in random walks (in continuous media or on graphs), numerical methods
   Professor: Dr. Árpád Tóth
   ASSIGNEMENT FOR THE FIRST WEEK: Read this introduction to the subject, from "A guide to first passage processes" by Sidney Redner.



3. Title: (Small) Forbidden Configurations
   
   Description: The topic is extremal hypergraph theory formulated mostly in the language of 0-1 matrices, since that is the most convenient way. We say that a 0-1 matrix A has F as a configuration if there is a submatrix ofA, which is a row and column permutation of F. This concept is also called a trace or subhypergraph depending upon whether the context is set systems or hypergraphs.
   
   The fundamental question is that for given F (or sometimes for given collection F of configurations) what is the largest possible number of columns of a simple mxn 0-1 matrix A on given number of rows without having F (or any member of F as configuration, in notation forb(m,F) or forb(m,F). A 0-1 matrix is simple if it has no repeated columns. Considering columns as characteristic vectors of subsets of an m element set matrix A describes a hypergraph, or set system.
   
   In this project you will get acquainted with basic proof ideas of the area, such as ``standard induction'', shifting, applications of graph theory and linear algebra. The goal is to get results on particular forbidden configurations. For more info check
   http://www.math.ubc.ca/~anstee/FCsurvey12.pdf

   Prerequisites: basic combinatorics, possibly linear algebra;
   Best for: students who intend to do research in combinatorics
   Professor: Dr. Attila Sali
   ASSIGNMENT FOR THE FIRST WEEK: Click here




4. Title: Graphs with prescribed color spectrum sequence
   
   Description: The Havel-Hakimi theorem gives an algorithmic description deciding whether or not a graph exists with a prescribed degree sequence, namely, given a sequence of numbers D = d_1, d_2, .. d_n, is there a graph G with n vertices such that for all i, v_i has d_i edges. For such a graph, we say that G is a realization of D. We would like to extend this question for the case when the edges of the graph are colored, and for each vertex v and each color c, we would like to prescribe d_c(v), the number of edges of v having color c. The general question seems to be too hard, therefore, we will start with the simplest case, the regular color spectrum sequences, when for all color c and all pair of vertices v_1 and v_2, d_c(v_1) = d_c(v_2). The central question is for which color spectrum and number of edges a graph exists with the prescribed regular color spectrum sequence. Above the existence question, we are also interested in how to generate all possible solutions or how to generate a random solution. For this, Markov chain Monte Carlo methods are natural candidates, and therefore, we would also like to study what perturbations are necessary to transform a realization of a regular color spectrum sequence into another realization.
   
   Prerequisites: Basic combinatorics.
   Best for: students interested in combinatorics and computer science
   Assignment for the first week:
   Read Chapter 12 from this electronic note: http://www.renyi.hu/~miklosi/AlgorithmsOfBioinformatics.pdf ,
   learn the Havel-Hakimi theorem,
   understand the concept of swaps.
   Solve these exercises: http://www.renyi.hu/~miklosi/RES2015SUM/Exercises.pdf