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.

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.

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).

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.

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.

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.

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.)

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.

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.)

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.

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.

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)).

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.

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

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

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.)

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.

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.

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.