BSM-TDK — Research Opportunities — RES

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, Involve or many others.

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

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

You can view articles that were written under the auspices of the BSM program

COURSE LOGISTICS

The list of research topics and professors proposing them can be seen below. Contact the professor whose problem you are interested in.

• Who can participate? Most professors 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 as much of these as you can by the Welcome Party and discuss your progress with the professor. First enrollment will be based on work on these problem sets/reading assignments. Final enrollment will be decided by the third week (as explained below).
• Which topics will actually be offered ("stay alive")? Of the initially offered research topics below those will be offered eventually, for which a group of students (at least around 3) would like to sign up and are accepted by the Professor based on discussions at the Welcome party and/or the first week.
• Course work: weekly meetings.
  Class will meet twice weekly, two hours each. One class time is devoted to group work, when you discuss the problem and possible solutions with your student group (without the professor). The other class time is spent with your professor who will monitor your group's progress.
• Course work: presentations.
  Week 3 - Milestone 1: The first three weeks of the course are spent discussing, gathering and studying necessary background information for your problem. At the end of the 3rd week, you (and your group) will have to present the problem you are working on in 20 minutes at a "mini workshop" organized for all BSM-TDK participants, their professors and everyone else interested. At this point professors evaluate progress and final enrollment decision is made. Ideally, the size of research groups is low, at most three.
  Week 9 - Milestone 2:: Work continuous thrughout the semester. At the 9th week each group should present their results at a "Preliminary report session" organized for all BSM-TDK participants, their professors and everyone else interested.
  Week 9/10-14:: Write up of results continuous and papers are produced.

TOPICS PROPOSED — FALL 2015

1. Title: Combinatorial explanation of the holographic algorithms
   
   Description: Leslie Valiant introduced the holographic algorithms that can reduce exponential running time to polynomial to count certain combinatorial objects.The key idea of the method is to use linear algebraic reduction of a counting problem to counting the number of perfect matchings of planar graphs. The squared number of perfect matchings of a planar graph can be calculated as the determinant of an adjacency matrix of the planar graph with appropriate orientation. There is an interesting efficient algorithm to calculate the determinant of a matrix using so-called closed ordered walks. This algorithm does not use any linear algebraic method, only basic combinatorial technics.
   
   The idea is to build up holographic algorithms in a pure combinatorial way, starting with closed ordered walks. In this way, we will have a combinatorial framework to count certain combinatorial objects in polynomial time. Then we are going to search other counting problems that can be solved efficiently in this way.
   
   Prerequisites: Basic combinatorics and linear algebra, strong interest in computer science
   Best for: students who intend to do research in modern computer science, computational complexity and combinatorics
   Professor: Dr. István Miklós
   ASSIGNEMENT FOR THE FIRST WEEK: downloadable from here http://renyi.hu/~miklosi/RES2015Fall/assignment-firstweek.pdf
   
   Further reading: we are going to read and discuss the following papers and notes:
   1. Michael Soltys: Berkowitz's algorithm and clow sequences
   2. Rich Schwartz: Kastelyn's formula for perfect matchings
   3. Leslie G. Valiant: Holographic algorithms
   
   
2. Title: Modeling epidemic and information propagation on networks by using differential equations
   
   Description: Epidemic and information propagation on random graphs can be described by several, so-called mean-field, models that are systems of non-linear differential equations. Some characteristics of the graph structure are reflected by the differential equations enabling us to derive dynamical consequences from graph properties. Our main focus in this project is to study SIR (susceptible-infected-recovered) epidemics on configuration random networks with different degree distributions. The aim is to understand how the final size of the epidemic depends on the degree distribution of the graph.
   
   The starting point to the research is the paper: Y. Moreno, R. Pastor-Satorras, A. Vespignani, Epidemic outbreaks in complex heterogeneous networks, Eur. Phys. J. B 26, 521-529 (2002) available at: http://arxiv.org/pdf/cond-mat/0107267.pdf
   
   Prerequisites: basic knowledge about differential equations and graphs
   Best for: students who are interested in modelling real-word phenomena by using mathematics
   Professor:dr Peter Simon
   ASSIGNMENT FOR THE FIRST WEEK: Read and understand Sections 1 and 2 of the above paper. Then derive formula (4) in the case when μ=1 and S(0)=1 is not assumed, that is μ is an arbitrary positive number and S(0)<1 is also arbitrary. Try to develop an algorithm to solve (4) for R_∞ numerically.
   
   
3. Title: Proving implications between generalized quasi-random properties
   
   Description:At the turn of the millennium, thanks to the spread of the World Wide Web and the human genome project, the study of expanding networks was extended to random situations different from the classical Erdôs-Rényi model, and to large deterministic networks showing so-called quasi-random properties. The multiclass generalization is the generalized random graph (popularly, stochastic block model), the deterministic counterpart of which is the generalized quasi-random graph (L. Lovász and V. T-Sós). We have characterized spectra and spectral subspaces of graph based matrices, and established relations to the multiway discrepancy, a measure of a good clustering. Based on the spectra, multiway discrepancy, and degree sequences, at the end of Section 3 of the arXiv paper below, we have defined so-called generalized quasi-random properties PI-PV, the implications of which are true for certain deterministic graph sequences, irrespective of stochastic models. The research aims at proving the missing implications, mainly the one between the subgraph degrees and discrepancies (PIII versus PV), where former results of Thomason, Chung, Graham, and Wilson can be used (these apply to the one-cluster situation).
   
   Prerequisites: Basic combinatorics and linear algebra
   Best for: students who intend to do research in networks
   Professor: Dr. Marianna Bolla
   
   Assignment for the first week: read the first three sections of the arXiv paper: http://arxiv.org.abs/1508.04369
   and have a look at the available parts of Bolla, M., Spectral Clusterin and Biclustering. Learning Large Graphs and Contingency Tables. Wiley, 2013.
   
   
4. Title: Rigid and globally rigid frameworks
   
   Description: click here for the description of the problem
   
   Prerequisites: basic graph theory, basic geometry
   Best for: students who intend to do research in combinatorics, graph theory or discrete geometry
   Professor: dr Tibor Jordan
   ASSIGNMENT FOR THE FIRST WEEK: Start working on the exercises given in the description.
   
   
   
5. Title: Stars and Stripes
   
   Description: click here for the description of the problem
   
   Prerequisites: basic combinatorics;
   Best for: students who intend to do research in combinatorics
   Professor: Dr. András Gyárfás
   ASSIGNEMENT FOR THE FIRST WEEK: work on the exercises given in the description.



6. Title: Which graph has the MMS property?
   
   Description: Based on an old paper of the professor, Huang and Sudakov and - independently - Pokrovskiy introduced the MMS property of a (hyper)graph: a (hyper)graph H has the MMS property if for every assignment of weights to its vertices with nonnegative sum, the number of edges whose total weight is nonnegative is at least the minimum degree of H. The definition was born from the MMS conjecture which (in this language) says that the hypergraph containing all k-element subsets of an n-element set has the MMS property for n > 4k. In general it seems to be very difficult to decide whether a general hypergraph has the MMS property.
   
   In this project we will target the question: which graph has the MMS property (i.e., we restrict to the much simle case when all edges have exactly two vertices). More general, let mms(G) (for a graph G) denote the minimum number of nonnegative edges over all assignment of weights to the vertices of the graph with nonnegative sum (where the weight of an edge is the sum of the weights of the two endvertices). We will investigate the behaviour (value) of this new graph parameter.
   
   Prerequisites: basic combinatorics and graph theory
   Best for: students who intend to do research in graph theory or combinatorics
   Professor: Dr. Dezsô Miklós
   ASSIGNMENT FOR THE FIRST WEEK: prior the first meeting of the course: think over the definition and try to answer the following questions:
   1. prove that mms(G) \ le min deg (G)
   2. what is the mms of a bipartite graph with unequal class sizes?
   3. prove that the mms of a regular graph is at least 1.
   4. find mms(K_5)
   5. find mms (C_5), in general (C_{2n+1}) and mms(C_{2n})
   6. which are the graphs with mms(G)=0 (hard)?
   
   Read the introduction of these related articles:
   1. Alexey Pokrovskiy, A linear bound on the Manickam-Miklós-Singhi Conjecture
   2. Hao Huang, Benny Sudov, The minimum number of nonnegative edges in hypergrap
   3. Noga Alon, Hao Huan, Benny Sudakov, Nonnegative k-sums, fractional covers, and probability of small deviations