Available individual papers

Series talk
Bc student
Ms student
Phd student
Detecting an induced subdivision of K_4 by Ngoc Khang Le
Polynomial time algorithm for testing whether a given graph contains a subdivision of complete graph on four vertices.
A STABILITY THEOREM ON CUBE TESSELLATIONS by Peter Frankl and János Pach
The paper shows that if a (big) cube is split into smaller cubes such that side length of each of the smaller cubes is in the interval [1,1+epsilon] for some quite small epsilon, then the only option is that the smaller cubes have all the same side length.
Using Dynamical Systems to Construct Infinitely Many Primes, Andrew Granville
Similarly as in paper 2., this paper is also focused on constructing infinitely many primes. This time the paper is indeed constructive and shows how it is possible to construct infinite sequence of primes from varying starting conditions on certain dynamical system(s).
Lattice Point Visibility on Generalized Lines of Sight, Edray H. Goins, Pamela E. Harris, Bethany Kubik and Aba Mbirika
The paper focuses on counting the ratio of the lattice points visible from the origin when the visibility is considered along functions ax^b. Somewhat amazingly, the Reimann zeta function appears in the solution.
Rational Right Triangles of a Given Area, Stephanie Chan
The paper is focusing on describing the set of right triangles with rational side lengths of a given area. It may serve also as an introduction to algebraic geometry.
Bipartite complements of circle graphs, L. Esperet and M. Stehlík
The paper contains very short and elegant proof of a previously known fact that a bipartite complement of a circle graph is again a circle graph. The paper is maybe too short, thus it could be beneficial to combine it with another short paper.
Graphs with at most one crossing, A. C. Silva, A. Arroyo, R. B. Richter and O. Lee
The crossing number of a graph is the minimal achievable number of crossings among all drawings of the graph. This geometric paper provides a structural characterization of graphs with crossing number at most 1. (Medium difficulty.)
A GOLDEN RATIO INEQUALITY FOR VERTEX DEGREES OF GRAPHS by F. Knox, B. Mohar, and D. R. Wood
An easy to access paper showing certain inequality for degrees of a graph. Quite surprisingly, the golden ratio appears in the exponent.
The geometry and combinatorics of discrete line segment hypergraphs, D. Oliveros, C. O’Neill and S. Zerbib
The paper that provides some bounds on the chromatic number and covering number of so called r-segment hypergraphs. The contents is on the boundary of combinatorics and geometry. (Medium difficulty.)
Bounded VC-dimension implies Schur-Erdos conjecture, J. Fox, J. Pach and A. Suk
Ramsey number r(3,m) is the minimum integer n such that any m-coloring of the edges of the complete graph K_n contains a monochromatic triangle. Understanding asymptotic behaviour of r(3,m) is a long standing problem. The paper confirms the conjectured optimal upper bound for colorings with bounded VC-dimension.
Cops and Robbers on graphs of bounded diameter, S. A. Hosseini, F. Knox and B. Mohar
The paper studies the game of Cops and Robers on a graph, where Cops and Robber take turns in which they might move to along an edge of a graph. The question is, how many Cops can capture a Robber on a given graph. The paper studies the game graphs of bounded diameter.
Large almost monochromatic subsets in hypergraphs, D. Conlon, J. Fox and B. Sudakov
The paper studies somewhat relaxed version of Ramsey number on 3-uniform hypergraphs. In particular, the authors show that every l-coloring of triples of N-element set contains an almost monochromatic subset, that is, a subset where at most epsilon fraction of triples have different color, of size O(sqrt(log n)).
On an extension of Dirac's theorem, F. Joos, J. Kim
Dirac's theorem states that if every vertex of graph on n>=3 vertices has degree at least n/2, G contains a Hamilton cycle. The paper generalizes this theorem, stating that if we are given n graphs on the same vertex set, all satisfying Dirac's condition, there is a Hamilton cycle using exactly one edge from each graph.
Caterpillars in Erdos-Hajnal, A. Liebenau, M.Pilipczuk, P. Seymour, S. Spirkl
Erdos Hajnal conjecture states that for every graph H, if G does not contain H as an induced subgraph, G has either large clique or an independent set. In the paper, the conjecture is proved for H being a subdivision of a caterpillar
On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest, K. Dabrowski, C. Feghali , M. Johnson , G. Paesani, D. Paulusma , and P. Rzążewski
The paper studies complexity of classical NP-complete problems of feedback vertex set and odd cycle transversal, when restricted to a class of graphs avoiding a fixed small forest as an induced subgraphs. The paper contains both polynomial algorithms for some settings, and NP-hardness results for other settings. The paper is rather long but contains several somewhat independent results. You are expected select only some of the results for the presentation.
The complexity of Dominating Set in geometric intersection graphs by Mark de Berg, Sándor Kisfaludi-Bak, Gerhard Woeginger
Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares by Sanjib Sadhu, Sasanka Roy, Subhas C. Nandy, Suchismita Roy
The Nash-Williams Conjecture and the Dominating Cycle Conjecture by Arthur Ho mann-Ostenhof
Short paper
On the sets of n points forming n + 1 directions by Cedric Pilatte
Long cycles through prescribed vertices have the Erdos-Posa property by Henning Bruhn, Felix Joos, Oliver Schaudt
Finite field Kakeya and Nikodym sets in three dimensions, B. Lund, S. Sarah, C. Wolf
Kakeya sets are sets that contain line in every dimension. In this paper they are studied in dimension 3 over a finite field. In particular this paper improves the lower bound on their size. The paper combines ideas from combinatorics, algebra (ideas similar to nullstellensatz) and probability. Suitable for somebody more experienced. (The paper contains more results. For presentation, it would be desirable to focus on Kakeya sets first and discuss the other parts only if time allows.)
RAINBOW MATCHINGS IN PROPERLY-COLOURED MULTIGRAPHS by P. Keevash and L. Yepremyan
Given a properly edge-colored multigraph G with not too large multiplicities of edges and with no color appearing too few times, the authors provide an algorithmic proof that G contains a big rainbow matching, that is a matching where no color appears more than once. Suitable for a Master student or a bit experienced Bachelor's student.
Two remarks on eventown and oddtown problems, B. Sudakov, P. Vieira
An eventown is a set system such that the size of each set is even and pairwise intersections are even.(Oddtown is defined similarly.) Here the authors provide several results on modifications of eventowns and oddtowns. One of them is a certain stability result describing slightly generalized eventowns with many sets. The tools are combinatorics and a bit of linear algebra. The paper is suitable for a Master student or a more experienced Bachelor student.