Series talks

Lecture series on random regular graphs

In this series we will get familiar with two tools needed to analyze random regular graphs: the configuration model (due to B. Bollobas) and the switching method (due to B. McKay). I invite you to choose one of the the four topics to present. After you read, I suggest meeting you and discussing the challenges and make suggestion what to omit (if it is hard to fit in a single talk) or how to expand (if things are going too easy).

    Topics about d-regular graphs, d fixed
  1. Limit distribution of number of cycles in R(n,d), d fixed (and the asymptotic number of d-regular graphs that follows), section 9.2 in book 'Random graphs' by Janson and Luczak and Rucinski.
  2. Almost every d-regular graph is d-connected (with room to spare), Thm 7.32 in book 'Random graphs' by Bollobas.

  3. Topics about d-regular graphs, d growing (the method of switchings)
  4. Asymptotic formula for number of graphs with given degree sequence, when max degree is o(n^{1/3}). Based on [MW90] pages 52-59, can be simplified by assuming d-regular graphs. (Alternative source: Theorem 10.4 in the book 'Introduction to random graphs' by Frieze and Karonski).
  5. Generating uniformly a graph with given degree sequence, max degree o(n^{1/3}) in expected polynomial O(n^2k^4) time. Based on [MW90], pages 59-62, you can assume that topic 3 is already presented; if you are doing well, you can present the better algorithm from Section 5); you can simplify the presentation by assuming d-regular graphs.

If you are interested contact me at matas.sileikis at gmail.com

Introduction to Communication Complexity

Communication model seems to be good to prove unconditional lower bounds and still sufficiently strong to design some non-trivial algorithms. There are two players Alice and Bob in the standard communication model and they know some function f: X x Y -> Z of two variables. Alice gets x in X and Bob gets y in Y. Their goal is to communicate and then output f(x,y). Communication complexity of f is the minimal number of bits needed to send to compute the function f. In this series we introduce this model, show some basic technique and applications of lower bounds in the communication model. The series is suitable for bachelor and master students. It is planned for 3 slots:

  1. Introduction of the communication model and its variants. Basic lower bounds technique.
  2. A little bit advanced techniques and applications.

For more information please write at koblich at iuuk.mff.cuni.cz.

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.
Minimum density of identifying codes of king grids by R. Dantas, R.M. Sampaio, and F. Havet
Identifying code in a graph is a set of vertices such that every vertex of graph is uniquely defined by the set of adjacent vertices from the identifying code. Paper gives some bounds on minimum density of such codes using discharging methods. As usual for discharging methods, some proofs get rather technical and they should be omitted or only the main idea should be presented (this in particular applies to Theorems 8 and 9 in the paper).
NP-hardness and fixed-parameter tractability of the minimum spanner problem by Yusuke Kobayashi
A t-spanner of a graph G is a spanning subgraph in which the distance between every pair of vertices is at most t times of their distance in G. It is shown that finding minimum t-spanner in a planar graphs is NP-hard for any t at least 2.
Constant query time (1 + eps)-approximate distance oracle for planar graphs by Qian-Ping Gu and Gengchun Xu
Construction of an oracle which (after some preprocessing) approximately answers queries regarding distance in the given planar graph in constant time.
Sharing a pizza: bisecting masses with two cuts by Luis Barba, Alexander Pilz, Patrick Schnider
Assume you have a pizza consisting of four ingredients (e.g. bread, tomatoes, cheese and olives) that you want to share with your friend. You want to do this fairly, meaning that you and your friend should get the same amount of each ingredient. How many times do you need to cut the pizza so that this is possible? We will show that two straight cuts always suffice.
Tiling the plane with equilateral triangles by Janos Pach, Gabor Tardos
Let 𝒯 be a tiling of the plane with equilateral triangles no two of which share a side. We prove that if the side lengths of the triangles are bounded from below by a positive constant, then 𝒯 is periodic and it consists of translates of only at most three different triangles. As a corollary, we prove a theorem of Scherer and answer a question of Nandakumar.
Tilings with noncongruent triangles by Andrey Kupavskii, Janos Pach, Gabor Tardos
We solve a problem of R. Nandakumar by proving that there is no tiling of the plane with pairwise noncongruent triangles of equal area and equal perimeter. We also show that any tiling of a convex polygon with more than three sides with finitely many triangles contains a pair of triangles that share a full side.
Acute Sets by Dmitriy Zakharov
A set of points in R^d is acute if any three points from this set form an acute triangle. In this note we construct an acute set in R^d of size at least 1.618^d. We also present a simple example of an acute set of size at least 2^d/2.
A bound on the inducibility of cycles by D. Kral, S. Norine and J. Volec
Short and elegant proof that every graph on n vertices contains at most 2n^k/k^k induced cycles of length k.
Infinitude of Primes Using Formal Languages, Aalok Thakkar
A nontradional way how to show that there are infintely many primes via playing with regular languages. (This is perhaps going to be a shorter talk.
Sacks of Dice with Fair Totals, Ian Morrison
The paper describes how to from `very fair sacks' of dice where every sum is equally likely.
A vertex ordering characterization of simple-triangle graphs Asahi Takaoka
A simple triangle graph is a graph that can be represented as an intersection graph of triangles in between of two lines (for a precise definition, see the paper). This paper provides a characterization of these graphs via existence of a certain ordering on the set of vertices of the graph.