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


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


  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

    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:

    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:
    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