Range searching is a classical problem that has been studied extensively both in computational geometry and databases, and problem to which Jirka contributed extensively. Over the last three decades, several sophisticated geometric techniques and data structures (e.g. range trees, eps-nets, cuttings, partition trees) have been proposed for range searching that have had a profound impact on the two fields, much beyond range searching. The first half of the talk reviews recent theoretical results on range searching, discusses a few variants of range searching that have emerged in the last few years, and sketches some of the approaches that are being used in practice. The second half focuses on an on-going interdisciplinary project focused on discerning subtle qualities of claims based on some underlying data, e.g., is a claim ``cherry-picking''? We propose a Query Response Surface (QRS) based framework that models claims based on structured data as parametrized queries. A claim is mapped to a point on the QRS, and often it is a singularity on QRS. A key insight is that we can learn much about a claim by analyzing the singularity. This framework allows us to formulate and tackle a variety of journalistic tasks as computational problems, such as reverse-engineering vague claims, countering questionable claims, and finding high-quality leads from data.

Much of the work of Jiří Matoušek, his papers and books include fascinating applications of tools from linear algebra and topology in the investigation of combinatorial problems and in the study of their algorithmic aspects. In the tradition of his work I will describe several recent and less recent applications of topological and algebraic methods in the derivation of combinatorial results. In all of them the proofs provide no efficient solutions for the corresponding algorithmic problems.

In the last few years there has been remarkable progress in our understanding of combinatorial discrepancy and in particular its algorithmic aspects. In addition to leading to efficient algorithms for various problems where only non-constructive proofs were known before, these methods have also led to improved results and various new connections between discrepancy and convex geometry, optimization and probability. In this talk, we will give an overview of some of these developments.

Given a pointed cone $C$ in $\mathbb R^d$, an integral zonotope in $C$ is the Minkowski sum of segments of the form $[0,z_i]$ $(i=1,\ldots,m)$ where $z_i$ is an integer vector from $C$. The endpoint of this zonotope is the sum of the $z_i$. The collection $T(C,k)$ of integral polytopes in $C$ with endpoint $k$ is a finite set. We show that the zonotopes in $T(C,k)$ have a limit shape as $k$ goes to infinity. The proofs combine geometry and probability theory. Several new (and exciting) questions have emerged.

Joint work with Julien Bureaux and Ben Lund.

Siegel's Lemma is a key tool in transcendental number theory and diophantine approximation. It is a clever application of the Pigeonhole Principle—a ``pure existence argument''—with strikingly powerful consequences.

Suppose we have a homogeneous system of linear equations with integer coefficients: $n$ equations, $N$ variables with $N>n$, and every coefficient has absolute value $\le A$.

PROBLEM: Give an upper bound to the maximum norm of the smallest nontrivial integer solution.

Sharpest known form of Siegel's Lemma gives the upper bound $$\left( 70\sqrt{N}A\right)^{n/(N-n)}.$$ It is easy to show that the factor $A$ cannot be replaced by $o(A)$ (hint: use primes). So, $A=1$ is the most interesting special case.

Hard Question: Assuming $A=1$, can we replace the base $\sqrt{N}$ in the upper bound $\left(\sqrt{N}\right)^{n/(N-n)}$ with a smaller base $o(\sqrt{N})$?

The answer is no: We prove that the sharpest known form of Siegel's Lemma is best possible. We outline the long proof.

We study $d$-dimensional simplicial complexes that are PL embeddable in $\mathbb{R}^{d+1}$. It is shown that such a complex must satisfy a certain homological condition. The existence of this obstruction allows us to provide a systematic approach to deriving upper bounds for the number of top-dimensional faces of such complexes, particularly in low dimensions.

Joint work with Afshin Goodarzi.

Bárány's ``topological Tverberg conjecture'' from 1976 states that any continuous map of an $N$-simplex $\Delta_N$ to $\mathbb R^d$, for $N \geq (d+1)(r-1)$, maps $r$ points from disjoint faces in $\Delta_N$ to the same point in $\mathbb R^d$. The proof of this result for the case when $r$ is a prime, as well as some colored version of the same result, using the results of Borsuk–Ulam and Dold on equivariant maps between spaces with a free group action, were main topics of Matoušek's 2003 book ``Using the Borsuk–Ulam theorem''.

In this lecture we go beyond, and present the methods that yield the case when $r$ is a prime power (and give the proof!), exhibit the failure of configuration test map scheme for non-prime powers, introduce the ``constraint method'' which yields a great variety of variations and corollaries, and sketch the path towards the Optimal colored Tverberg theorem and Bárány-Larman conjecture.

(This lecture is motivated by the classical book of Jiří Matoušek ``Using the Borsuk–Ulam Theorem. Lectures on Topological Methods in Combinatorics and Geometry'', and is based on the joint articles with Imre Bárány and Günter Ziegler.)

Many applications of linear algebra method to combinatorics rely on the bounds on ranks of matrices with few distinct entries and constant diagonal. In this talk, I will explain some of these application. I will also present a classification of sets $L$ for which no low-rank matrix with entries in $L$ exists.

Topological graph is a graph with added information which pairs of edges are allowed to cross in a drawing in the plane. The AT graphs is realizable if such a drawing indeed exists. Unlike planarity, testing realizability of AT graphs is known to be computationally hard. In our paper with Jirka Matousek published in 1991 we exhibited an unexpected feature of this problem by showing that there exist realizable AT graphs that require exponential number of edge crossing in any realization. The construction naturally popped out in an at first sight much simpler problem of noncrossing drawings of graphs with specified regions for drawings of the edges that we conisdered with Torsten Ueckerdt in 2013.

A string graph is the intersection graph of continuous arcs in the plane. Matoušek showed that every string graph with m edges has a balanced separator with $O(\sqrt{m} \log m)$ vertices. Fox and Pach have conjectured that the correct bound is $O(\sqrt{m})$, and this would be optimal if true. We modify Jirka's argument to confirm their conjecture.

This is part of our ongoing effort to develop what we call "High-dimensional combinatorics". We equate a permutation with its permutation matrix, namely an nxn array of zeros and ones in which every line (row or column) contains exactly one 1. In analogy, a two-dimensional permutation is an nxnxn array of zeros and ones in which every line (row, column or shaft) contains exactly one 1. It is not hard to see that a two-dimensional permutation is synonymous with a Latin square. It should be clear what a d-dimensional permutation is, and those are still very partially understood. We have already made good progress on several aspects of this field. We largely start from a familiar phenomenon in the study of permutations and seek its high dimensional counterparts. Specifically we already have some progress on the following:

• The enumeration problem
• Birkhoff von-Neumann theorem and d-stochastic arrays
• Erdös-Szekeres theorem and monotone sub-sequences
• Discrepancy phenomena – this will be a major focus of my lecture
• Random generation

Almost everything that I will be presenting is joint work with my ex-student Zur Luria.

Ising partition function is usually defined on a graph $G$ embedded in a 2-dimensional surface. It is equivalent to the generating function of the edge-cuts of $G$, and also to the generating function of the even sets of edges of $G$. A standard way to calculate the Ising partition function is to compute a linear combination of $4^g$ Pfaffians, where $g$ is the genus of the surface. This is known as the Arf-invariant formula. Solving a conjecture of Sergei Norine for even sets, we proved some years ago with Gregor Masbaum that $4^g$ is optimal in a very restricted but natural computational model. In the talk I will further address the complexity of computing the maximum weight of an edge-cut for embedded graphs. Close to enumeration of the even sets is the enumeration of the perfect matchings. I will discuss some questions about perfect matchings enumeration on grids suggested by physicists. Finally, I will discuss product formulas for the Ising partition functions.

We want to assign a $d$-dimensional unit vector to each node of a graph, so that non-adjacent nodes should be labeled by orthogonal vectors. In what dimension can we do so? The answer seems to be more interesting when we impose various kinds of non-degeneracy conditions. For example, if we want the representing vectors to be in general position (every $d$ of them linearly independent), then a rather old theorem of Saks, Schrijver and Lovasz says that this can be done if and only if the graph is $(n-d)$-connected.

We survey several nondegeneracy conditions, including ''transversality`` (a.k.a. Strong Arnold Property). The methods lead to a study of the algebraic variety of all orthogonal representations of a given graph in a given dimension. We characterize when this variety is irreducible up to dimension 4.

The Sum Complex $X_{A,k}$ associated with a subset $A$ of the cyclic group $\mathbb{Z}_n$ and an integer $1 \leq k \leq n$, is the $(k-1)$-dimensional simplicial complex on the vertex set $\mathbb{Z}_n$ whose maximal simplices are the sets $\sigma \subset \mathbb{Z}_n$ of cardinality $k$ such that $\sum_{x \in \sigma} x \in A$. Sum complexes may be viewed as high dimensional analogues of Cayley graphs over $\mathbb{Z}_n$ and are relevant to a number of problems in topological combinatorics. In this talk, we shall describe the homology of sum complexes as well as some of their applications, including:

1. Construction of high dimensional trees from sum complexes.
2. Upper bounds on Betti numbers in terms of links, and nearly matching lower bounds via sum complexes.
3. Uncertainty inequalities for the finite Fourier transform and their connections to the topology of sum complexes.

The talk is based in parts on joint work with Nati Linial and Mishael Rosenthal and with Amir Abu-Fraiha.

In one of his first papers, written jointly with Jan Kratochvíl in 1989, Jirka Matoušek initiated the systematic study of combinatorial and algorithmic properties of various classes of string graphs, that is, intersection graphs of continuous arcs (strings) in the plane. In a posthumously published essay (CRM Series, 2015), he addressed similar questions. During the quarter-century that elapsed between these works, he regularly returned and richly contributed to this subject and, more generally, to geometric graph theory. In this talk, we recall some of Jirka's most significant achievements in this field, and mention a few recent results.

I will describe new approach to combinatorial objects which are provably “hard to enumerate”. In particular this shows how to construct objects whose generating function is not D-finite and even ADE. We illustrate our approach in two key examples:

1. words over a linear group (we resolve negatively Kontsevich’s problem)
2. pattern avoiding permutations (we resolve negatively Noonan-Zeilberger’s Conjecture)

Joint work with Scott Garrabrant.

Given $d+1$ sets $S_1, S_2, \ldots, S_{d+1}$ (called color classes) in $\mathbb R^d$, a simplex is called colorful, if all its vertices are in different color classes. The number of colorful simplices containing a point $p\in \mathbb R^d$ is known as the colorful simplicial depth of $p$.

Since the point with the maximal depth can be seen as a higher dimensional analogue to median, the colorful simplicial depth is studied not only in discrete and computational geometry, but also in statistics and data analysis.

The first result concerning colorful simplicial depth in discrete geometry was the colorful Carathéodory's theorem by Bárány in 1982: ``Any point $p\in \mathbb R^d$ contained in the convex hull of all color classes has a non-zero simplicial depth provided that each color class has at least $d+1$ points.''

In 2006 Deza et al. asked for the minimal and maximal values of the colorful simplicial depth of the point $p$ in colorful Carathéodory's theorem. We use methods from combinatorial topology to prove a tight upper bound of the form $1+\prod_{i=1}^{d+1}\bigl(|S_i|-1\bigr)$.

Joint work with Karim Adiprasito, Philip Brinkmann, Arnau Padrol, Pavel Paták, and Raman Sanyal.

I will survey algorithms for testing whether two point sets are congruent, that is, equal up to a Euclidean isometry. I will introduce the important techniques for congruence testing, namely dimension reduction and pruning, or more generally, condensation. I will illustrate these techniques on the three-dimensional version of the problem. I will then discuss algorithms for higher dimensions, and in particular, highlight the unpublished contributions of Jiří Matoušek. Finally, I will sketch our recent algorithm for four dimensions with near-linear running time (joint work with Heuna Kim).

Brief history of Charles University.

We show that the following algorithmic problem is decidable: given a 2-dimensional simplicial complex, can it be embedded in $\mathbb{R}^3$? By a known reduction, it suffices to decide the embeddability of a given triangulated 3-manifold $X$ in the 3-sphere. The main step, which allows us to simplify $X$ and recurse, is in proving that if $X$ can be embedded, then there is also an embedding in which $X$ has a short meridian, i.e., an essential curve in the boundary of $X$ bounding a disk in $S^3\setminus X$, whose length is bounded by a computable function of the number of tetrahedral of $X$.

This is joint work with Matoušek, Tancer and Wagner.

Let $F$ be a collection of bivariate continuous functions of constant complexity, which changes dynamically by insertions and deletions of functions. We present a technique for dynamically maintaining the lower envelope of $F$, so that we can efficiently retrieve the function attaining the envelope at any query point $q\in\mathbb R^2$. Our data structure answers queries and performs updates in polylogarithmic time per operation, improving an earlier technique of Agarwal, Efrat, and Sharir.

The main tool in our analysis are vertical shallow cuttings, a refined variant of the notion of shallow cuttings, as introduced by Matoušek in his seminal 1992 paper on reporting points in halfspaces. In our variant, the cells of the cutting are vertical semi-unbounded (pseudo-)prisms, whose union covers the first $k$ levels of the arrangement of $F$. Vertical shallow cuttings have already been considered by Chan and others, but our version has additional properties: The ``celinigs'' of the prisms form an $xy$-monotone terrain, which approximates the $k$-level up to any prespecified relative error.

The construction of such a vertical shallow cutting for arrangements of planes is simpler, and its construction simplifies and improves earlier approaches.

A special instance of the dynamic lower envelope problem is the dynamic maintenance of the convex hull of a point set in $\mathbb R^3$; it is dual to the dynamic maintenance of the lower envelope of planes. We re-examine the best known technique for doing this, due to Chan, and manage to improve the cost of a deletion (the costliest operation in his scheme) to $O(\log^5 n)$ (from $O(\log^6 n)$), while keeping the cost of insertions and queries unchanged.

Our scheme has many applications. For example, we get efficient schemes for dynamic nearest neighbor queries in the plane with respect to a general family of distance functions that includes $L_p$-norms and additively weighted Euclidean distances, and for general (convex, pairwise disjoint) sites that have constant description complexity (line segments, disks, etc.). The polylogarithmic update and query time of our data structure improves the earlier data structure of Agarwal, Efrat and Sharir that required $O(n^\varepsilon)$ time for an update and $O(\log n)$ time for a query. Our data structure has numerous other applications, and in all of them it gives faster algorithms, typically reducing an $O(n^\varepsilon)$ factor in the bounds to polylogarithmic.

Joint works with Sariel Har-Peled, Haim Kaplan, Wolfgang Mulzer, Liam Roditty and Paul Seiferth.

I will mention four recent breakthrough results in incidence geometry:

1. Finite field Kakeya problem. (Dvir 2008) If $A$ is a subset of $F_q^n$ and contains a line in every direction, then $|A| > cq^n$, where $c$ depends on $n$ only.
2. Joints problem. (Guth-Katz 2010) Any $N$ lines in the space determine at most $O(N^{3/2})$ joints (a joint is a point incident to three non-coplanar lines).
3. Erdos distinct distance problem. (Guth-Katz 2015) Any $N$ points in the plane have at least $cN/logN$ distinct pairwise distances.
4. Cap-set problem. (Ellenberg and Gijswijt, using a lemma of Croot, Lev and Pach. 2016+) This is a huge improvement on the bound for the size of a cap(-set) in affine space over the field $GF(3)$ of three elements.

The common feature of the proofs of the four results is the smart use of a polynomial where the zero-set of the polynomial vanishes on a pointset determined by the problem. As a further illustration I will present a new application of the method, bounding the number of tangencies between algebraic curves in the plane. (Joint work with Jordan Ellenberg and Josh Zahl)

The classic analysis of the probability that the Galton-Watson tree is infinite gives an equation with two solutions. What about other properties. For first order properties we show that the equation system has a unique solution. More generally we consider properties defined by tree automata. There is then a natural equation system. Sometimes the system has rogue solutions, meaning solutions with no interpretation. This area combines structural combinatorics, probabilistic combinatorics and logic, all topics Jirka loved.

Joint work with Moumanti Podder.

Ryser's Conjecture states that for every $r$-partite $r$-uniform hypergraph it is possible to find a vertex cover of size only $(r-1)$-times the matching number. For $r=2$, the conjecture reduces to König's Theorem, for $r=3$ it was proved by Aharoni by topolgical methods, while for larger $r$ it is wide open. In the talk we will be focusing on those hypergraphs that are extremal for Ryser's Conjecture, that is their vertex cover number is exactly $(r-1)$-times their matching number. An intricate extension of Aharoni's topological method (obtained with Penny Haxell and Lothar Narins) provides a characterization of the $3$-uniform Ryser-extremal hypergraphs. In the talk we describe a recent joint work with Ahmad Abu-Khazneh, János Barát, and Alexey Pokrovskiy, where we construct exponentially many non-isomorphic Ryser-extremal hypergraphs, for a new infinite sequence of uniformities $r$. We speculate that these constructions provide further evidence that Ryser's Conjecture, if true in general, will not be solved by purely combinatorial methods.

The semi-random method was introduced in the early eighties. In its first form of the method lower bounds were given for the size of the largest independent set in hypergraph with certain uncrowdedness properties. The first geometrical application was a major achievement in the history of Heilbronn's triangle problem. It proved that the original conjecture of Heilbronn was false. The semi-random method was extended and applied to other problems. In this talk we give two further geometrical applications of it.

First we give a slight improvement on Payne and Wood's upper bounds on a Ramsey-type parameter, introduced by Gowers. We prove that if given any planar point set of size $\Omega \left(\frac{n^2\log n}{\log\log n}\right)$, then one can find $n$ points on a line or $n$ independent points.

Second we give a slight improvement on Schmidt's bound on Heilbronn's quadrangle problem. We prove that there exists a point set of size $n$ in the unit square that doesn't contain four points with convex hull of area at most $\mathcal O(n^{-3/2}(\log n)^{1/2})$.

This is a joint work with Péter Hajnal.

In this survey talk, we will discuss several mostly recent results on embeddings of simplicial complexes into the Euclidean space and into manifolds. We will mainly focus on the algorithmic aspects of this question. However, we will also touch few theoretical results.

The talk will be based on joint works with Jirka Matoušek and also with Xavier Goaoc, Isaac Mabillard, Pavel Paták, Zuzana Patáková, Eric Sedgwick and Uli Wagner.

Three measures of non-convexity of a set in $R^d$ will be discussed. The invisibility graph $I(X)$ of a set $X \subseteq R^d$ is a (possibly infinite) graph whose vertices are the points of $X$ and two vertices are connected by an edge if and only if the straight-line segment connecting the two corresponding points is not fully contained in $X$. We consider the following three parameters of a set $X$: the clique number $\omega(I(X))$, the chromatic number $\chi(I(X))$ and the minimum number $\gamma(X)$ of convex subsets of $X$ that cover $X$. Observe that $\omega(X) \leq \chi(X) \leq \gamma(X)$ for any set $X$, where $\omega(X):=\omega(I(X))$ and $\chi(X)=\chi(I(X))$.

Here is a sample of results comparing the above three parameters:

1. Let $X \subseteq R^2$ be a planar set with $\omega(X)=\omega < \infty$ and with no one-point holes. Then $\gamma(X) \leq O(\omega^4)$.
2. For every planar set $X$, $\gamma(X)$ can be bounded in terms of $\chi(X)$.
3. There are sets $X$ in $R^5$ with $\chi(X)=3$, but $\gamma(X)$ arbitrarily large.

The talk is based on joint papers with J. Matoušek, J. Cibulka, M. Korbelář, M. Kynčl, V. Mészáros, and R. Stolař.

We consider conditions under which a finite simplicial complex $K$ can be mapped to $\mathbf{R}^d$ without triple, quadruple, or higher-multiplicity intersections. More precisely, an almost $r$-embedding of $K$ in $\mathbf{R}^d$ is a map $f\colon K \rightarrow \mathbf{R}^d$ such that the images of any $r$ pairwise disjoint simplices of $K$ do not have a common point. In recent joint work with Mabillard, we proved that a well-known deleted product criterion is sufficient for the existence of almost $r$-embeddings of $k(r - 1)$-dimensional complexes in $\mathbf{R}^{kr}$, provided $k \geq 3$. This was extended to codimension $k = 2$ and $r \geq 3$ in joint work with Avvakumov, Mabillard, and Skopenkov. We survey these results and the main ideas, and we discuss how sufficiency of the deleted product criterion, together with results of Özaydin and of Gromov, Blagojevic, Frick, and Ziegler, implies the existence of counterexamples to the topological Tverberg conjecture, i.e., almost $r$-embeddings of the $(d + 1)(r - 1)$-simplex in $\mathbf{R}^d$ whenever $r$ is not a prime power and $d \geq 2r$.

A perfect matching on a finite planar point set $S$ is crossing-free if all of its edges are disjoint in the straight-line embedding on $S$. In 1948 Motzkin was interested in the number of such crossing-free perfect matchings for $S$ the $2m$ vertices of a convex polygon and he proved that to be the $m$-th Catalan number.

$S$ is called a wheel set if all but exactly one point in $S$ are vertices of its convex hull. Again we start by asking for the number of crossing-free perfect matchings of such a wheel set $S$, going the smallest possible step beyond Motzkin's endeavor. Since position matters now, in the sense that the number is not determined by the cardinality of the wheel set alone, this immediately raises extremal and algorithmic questions. Answering these comes with all kinds of surprises.

In fact, it turns out that for the purpose of counting crossing-free geometric graphs (of any type, e.g. triangulations or crossing-free spanning trees) on such a set $P$ it suffices to know the so-called frequency vector of $P$ (as opposed to the full order type information) – a simple formula dependent on this frequency vector exists. Interestingly, the number of order types of $n$ points in almost convex position is roughly $2^n$, compared to the number of frequency vectors which is about $2^{n/2}$.

Finally, this takes us on a journey to the rectilinear crossing-number of the complete graph, to counting of origin-embracing triangles and simplices (simplicial depth) and to (algorithms for) counting facets of high-dimensional polytopes with few vertices.

Based on recent joint work with Andres J. Ruiz-Vargas, Alexander Pilz, and Manuel Wettstein.

The story told in this lecture starts with an innocuous little geometry problem, posed in a September 2006 blog entry by R. Nandakumar, an engineer from Calcutta, India: ``Can you cut every polygon into a prescribed number $n$ of convex pieces that have equal area and equal perimeter?''

On the path to a (partial) solution of (the $d$-dimensional version of) this problem, we will encounter a number of quite different areas of Mathematics that Jirka has worked on and written about. This includes Discrete and Computational Geometry, specifically Optimal Transport and weighted Voronoi diagrams, as well as LP duality. This will set up the stage for application of topological tools. Thus we solve the problem for $n=2$ by using the Borsuk–Ulam theorem, but for larger $n$ we employ Equivariant Obstruction Theory. On the way to a solution, combinatorial properties of the permutahedron turn out to be essential. These will, at the end of the story, lead us back to India, with some time travel 100 years into the past.

The lecture might end by a philosophical reflection: Do we need high-power topological tools for such an elementary problem? How accessible, and how reliable, are such tools?

Joint work with Pavle Blagojević.

Let $G$ be a group with identity $e$ and let $R$ be a commutative $% G$-graded ring. A proper graded ideal $P$ of $R$ is called graded prime ideal if whenever $r,s\in h(R)$ and $rs\in I$, then $r\in I$ or $s$ $\in I$. In this work we will investigate commutative graded rings which have the $% \mathbf{\ast }$-property. We say that a graded ring $R$ satisfy $% \mathbf{\ast }$-property if $P$ is a graded prime ideal of $R$ and if $\{I_{\alpha }\}_{\alpha \in \Delta }$ is a nonempty family of graded ideals of $R$, then $P$ contains $\cap _{\alpha \in \Delta }I_{\alpha }$ only if $P$ contains some $I_{\alpha }.$

Acknowledgements: This work is supported by Jordan University of Science and Technology.

A matching $M$ in a graph $G$ is a collection of edges of $G$ such that no two edges of $M$ share a vertex. If every vertex of $G$ is incident to an edge of $M$, the matching $M$ is called perfect. Perfect matchings have played an important role in the chemical graph theory, in particular for benzenoid graphs, where their number correlates with the compound's stability. Let $\Phi(G)$ be the number of perfect matchings in G.

A fullerene graph is a cubic, planar, 3-connected graph with only pentagonal and hexagonal faces. Classical fullerene graphs have been intensely researched since the discovery of buckminsterfullerene in the fundamental paper by H. W. Kroto, J. R. Heath, S. C. O'Brien, R. F. Curl, and R. E. Smaley [C60: Buckminsterfullerene, Nature 318 (1985) 162–163]. This paper gave rise to the whole new area of fullerene science. A connected planar graph is called $m$-generalized fullerene if two of its faces are $m$-gons and all other faces are pentagons and hexagons.

Fullerenes are a special case of planar bridgeless graphs. Recall the Lovász-Plummer conjecture which claims that $\text{perfmat } G$ is exponential in $n$ for every cubic bridgeless graph. It is a generalization of the Erdős-Rényi conjecture for $3$-regular bipartite graphs. The Lovász-Plummer conjecture for planar graphs was proved by Chudnovsky and Seymour, and the complete conjecture was demonstrated by Esperet-Kardos-King-Kral-Norine. In this paper we present some upper bound for the number of perfect matching in planar cubic graph and proved that the number of perfect matching in these graph is less than $3^\frac{n}{4}$. In the case of Fullerene graphs(F) we proved that $\Phi(F) \le 20^{\frac{n}{12}}$. Also, we provide both upper and lower bounds on the number of perfect matchings in $m$-generalized fullerene graphs and state exact results in some special cases.

We investigate upper bounds for the absolute values of the sum $\sum_{r=1}^{\tau} e(\frac{a 2^r}{q})$ (where $\tau$ is the multiplicative order of 2 modulo $q$), concentrating primarily on the case of small $\tau$ i.e. of the order of $\log{q}$. We generalize methods used by Kaczorowski and Molteni and strengthen their results. In particular, we prove that if $\tau \geq \kappa (\lfloor \log _2 (q) \rfloor + 4) + 5$ then $\max_{(a,q)=1} |s(a/q)| < \tau - 2 (\kappa - 1)$ (possibly we can replace 2 with some larger constant at a cost of increasing $\tau$ slightly). Work in progress.

We combine some known results and techniques with new ones to show that there exists a non-algebraic, multi-linear matroid. This answers an open question by Matus (Discrete Mathematics 1999), and an open question by Pendavingh and van Zwam (Advances in Applied Mathematics 2013). The proof is constructive and the matroid is explicitly given.

We consider the problem of finding a low discrepancy coloring for sparse set systems where each element lies in at most $t$ sets. We give an efficient algorithm that finds a coloring with discrepancy $O((t \log n)^{1/2})$, matching the best known non-constructive bound for the problem due to Banaszczyk. The previous algorithms only achieved an $O(t^{1/2} \log n)$ bound even in the special case when all the sets have size $O(t^2)$. The result also extends to the more general Komlós setting and gives an algorithmic $O(\log^{1/2} n)$ bound. This is joint work with Nikhil Bansal and Daniel Dadush.

Let $\mathcal{G}$ denote the category whose objects are undirected graphs without multiple edges and morphisms are graph homomorphisms. We will define the notion of double mapping cylinder in the category $\mathcal{G}$. Let $\mathcal{G}'$ be subcategory of $\mathcal{G}$, whose objects do not contain $P_3$ as an induced subgraph. We will show that the Hom complex functor $Hom(T, \_\_ )$ which was defined by Lovász maps double mapping cylinders in graphs to homotopy pushouts in topological spaces where $T$ is a graph in $\mathcal{G}'$.

Joint work with Rekha Santhanam.

The authors recently extended the notion of quadrangulation of a surface to higher-dimensional spaces, and showed that every non-bipartite quadrangulation of the $n$-dimensional projective space is at least $(n+2)$-chromatic [J. Combin. Theory Ser. B, 113 (2015), pp. 1–17]. They conjectured that for any integers $k\geq 1$ and $n\geq 2k+1$, the Schrijver graph $SG(n,k)$ contains a spanning subgraph which quadrangulates the projective space of dimension $n-2k$. We outline a proof of this conjecture.

The notion of Violator Space was introduced by J. Matoušek et al. in 2008 as a generalization of a Linear Programming type problem. Convex geometries were invented by Edelman and Jamison in 1985 as proper combinatorial abstractions of convexity. We concentrate on interrelations between violator spaces and convex geometries. In particular, we show that convex geometries generate nondegenerate violator spaces.

Joint work with Vadim E. Levit.

Scheduling problems are fundamental in combinatorial optimization. Much work has been done on approximation algorithms for NP-hard cases, but relatively little is known about exact solutions when some part of the input is a fixed parameter. In 2014, Mnich and Wiese initiated a systematic study in this direction.

In this paper we continue this study and show that several additional cases of fundamental scheduling problems are fixed parameter tractable for some natural parameters. Our main tool is $n$-fold integer programming, a recent variable dimension technique which we believe to be highly relevant for the parameterized complexity community. This paper serves to showcase and highlight this technique.

Specifically, we show the following four scheduling problems to be fixed-parameter tractable, where $p_{max}$ is the maximum processing time of a job and $w_{max}$ is the maximum weight of a job:

• Makespan minimization on uniformly related machines ($Q||C_{max}$) parameterized by $p_{max}$,
• Makespan minimization on unrelated machines ($R||C_{max}$) parameterized by $p_{max}$ and the number of kinds of machines,
• Sum of weighted completion times minimization on unrelated machines ($R||\sum w_jC_j$) parameterized by $p_{max}+w_{max}$ and the number of kinds of machines,
• The same problem, $R||\sum w_jC_j$, parameterized by the number of distinct job times and the number of machines.

Neighborly cubical polytopes play as important role in the theory of cubical polytopes as ciclyc polytopes have palyed among simplicial polytopes. The formula for the face numbers of cyclic polytopes is well-known. We give an analogous formula for neighborly cubical polytopes by using the notion of the h-vector of the cubical polytopes and the Cubical Dehn-Sommerville Equations. The face numbers of a neighborly cubical polytope turn out to form a unimodal vector.

In 2010, Arocha, Bracho, Montejano and Ramírez-Alfonsín posed the following problem. Let $d$, $\lambda$ and $k$ be positive integers. What is the maximum number of points in $\mathbb{R}^d$ so that no matter how we choose them it is possible to find a common $(d-\lambda)$-transversal plane to all the convex hulls of $k$-sets of the set of points? Call this number $m(k,d,\lambda)$.

As was pointed by the authors, and independently B. Bukh, J. Matoušek and G. Nivash, this problem has connections to generalizations of two classical problems in combinatorial geometry: determining the chromatic number of Kneser graphs and Rado's central point theorem. Arocha et al. also obtained upper and lower bounds on $m(k,d,\lambda)$ and stated a conjecture concerning its precise value.

In this poster we will present part of a follow-up work on this problem. We will introduce a discrete variant of the parameter that, unlike the original parameter, is invariant on the order type. This allows us to study the problem using the theory of oriented matroids. In particular, we can completely solve the problem asymptotically for when the points are vertices of a cyclic polytope. These results can be applied to obtain new insights on the value of the parameter $m(k,d,\lambda)$.

Joint work with J. Chappelon, L. Montejano, L.P. Montejano, and J. Ramírez-Alfonsín.

In this poster I would present an extension of the well-known game of NIM. The game is a mixture of the chip firing game, that is a solitaire game, and the game of NIM, for which an strategy exists. The game is called NIM-o-DO, and there is also an strategy by using kernels by monochromatic paths, which generalises kernels in digraphs. I will give some boards where people can play the game.

Our results are concerned with art gallery theorems on orthogonal polygons. The first theorem of this kind is due to Kahn, Klawe and Kleitman: in 1980 they proved that $\lfloor n/4\rfloor$ point guards are sufficient and sometimes necessary to cover the interior of an orthogonal polygon of $n$ vertices. The original proof used deep geometrical insight, however, Győri (and independently O'Rourke) found a nice underlying partition theorem with a much shorter combinatoric proof. For many classical art gallery results the corresponding partition theorems have been proven for decades. Yet, Aggarwal's theorem, which states that $\lfloor\frac{3n+4}{16}\rfloor$ mobile guards are sufficient and sometimes necessary to control any $n$-vertex orthogonal simple polygon, has been a notable exception up until very recently:

Theorem [Győri, M., 2015]

Any $n$-vertex orthogonal simple polygon can be partitioned into at most $\lfloor\frac{3n+4}{16}\rfloor$ at most 8-vertex orthogonal simple polygons.

Moreover, our proof can be turned into a linear time algorithm using standard techniques.

From the mentioned results we can read off that from an extremal point of view point guards are $\frac34$ as efficient as mobile guards. The following theorem provides insight into why this is the case, as the $\frac34$ bound appears already for a single polygon.

Theorem [Győri, M., 2016]

Given a $P$ simple orthogonal polygon let $m_V$ be the minimum number of vertical mobile guards necessary to cover $P$, let $m_H$ be defined analogously for horizontal mobile guards, and finally let $p$ be the minimum number of point guards necessary to cover $P$. Then $$\frac{m_V+m_H-1}{p}\ge \frac{3}{4}.$$

The proof of this theorem can be turned into an $\frac83$-approximation algorithm for covering simple orthogonal polygons with point guards.

Given a finite point set $P$ in $\mathbb R^d$, we call a multiset $A$ a one-sided epsilon-approximant for $P$ (with respect to convex sets) if, for every convex set $C$ in $\mathbb R^d$, if $\alpha$ is the fraction of points of $P$ contained in $C$, then $C$ contains at least an $(\alpha-\varepsilon)$-fraction of the points of $A$.

We show that, in contrast with the usual (two-sided) epsilon-approximants, for every set $P$ in $\mathbb R^d$ there exists a one-sided epsilon-approximant of size bounded by a function of $\varepsilon$ and $d$.

Joint work with Boris Bukh.

A graph $G$ is said to be $k$-distinguishable if the vertex set can be colored using $k$ colors such that no nontrivial automorphism of $G$ fixes all the color classes. Distinguishing number $D(G)$ is the least $k$ for which $G$ is $k-$distinguishable.

A graph $G$ is said to be $k$-list distinguishable if each of the vertices can be colored from corresponding given lists of size $k$ such that $G$ is $k$-distinguishable. List distinguishing number $D_l(G)$ is the least $k$ for which $G$ is $k-$list distinguishable. In this poster we show $D_l(G)=D(G)$ when $G$ is a Kneser graph.

The Distinguishing chromatic number of a graph $G$, $\chi_D(G)$ is the minimum number of colors needed to proper color $G$ such that the coloring makes $G$ distinguishable. We show that for given $k\in\mathbb{N}$, there exists a sequence of graphs $G_{n_i}$ satisfying

• $\chi(G_{n_i})>k$,
• $\chi_D(G_{n_i})>\chi(G_{n_i})$,
• $G_{n_i}$ is vertex transitive and $|Aut(G_{n_i})|=O(n_i^{3/2})$

where $\chi(G)$ is the chromatic number and $Aut(G)$ is the automorphism group of the graph $G$.

Joint work with Niranjan Balachandran.

Given $k \ge 1$, the Fox-Kleitman conjecture states that there exists a nonzero integer $b$ such that the $2k$-variable linear Diophantine equation $$\displaystyle \sum_{i=1}^{k} (x_i-y_i) \ = \ b$$ is $(2k-1)$-regular. This would be best possible, since Fox and Kleitman showed that for all $b \ge 1$, the degree of regularity of this equation is at most $2k-1$. The conjecture has recently been shown to hold for $k=2$. In this work, we settle the conjecture for $k=3$. More precisely, we determine the degree of regularity of this equation for $k=3$ and all $b \ge 1$. We also briefly discuss the open case $k=4$ of the Fox-Kleitman conjecture.

A geometric graph is a graph drawn in the plane such that its $n$ vertices are points in general position, and its edges are straight-line segments. Two edge-disjoint geometric subgraphs cross if there is an edge in the first subgraph and an edge in the second subgraph that have an interior point in common. A set of edge-disjoint geometric subgraphs is called mutually crossing if any two of their elements cross. We show that for any geometric complete graph there always exists a set of mutually crossing $2$-paths (paths of length $2$) of size at least $\sqrt{n/2+1}-1$, and a set of mutually crossing claw graphs (a star of tree leaves) of size at least $n/6$.

Joint work with J. Cravioto, D. Lara, and J. Urrutia.

A 3-flow on an oriented graph is an assignment of values $\{0,\pm 1,\pm 2\}$ to the oriented edges in such a way that the total outflow at every vertex of the graph is 0. Each oriented graph admits a trivial 3-flow that assigns value 0 to every edge. We investigate 3-flows where the number of edges with flow value 0 is minimal. We prove that every 3-edge-connected graph admits a 3-flow such that at most $1/6$ of the edges carries value 0. This bound is attained for $K_4$.

Joint work with Matt DeVos, Jessica McDonald, Irene Pivotto, and Robert Šámal.

For given graphs $G_1,G_2,G_3$ the three-color bipartite Ramsey number $br(G_1,G_2,G_3)$ is defined to be the least positive $p$ such that any coloring of edges of $K_{p,p}$ with 3-colors contains a monochromatic copy of $G_i$ colored with $i$, for some $1 \leq i \leq 3$. In this poster, we show that $br(P_{2n-1},P_{2n-1},C_{2n})\geq 3n-2$ and $br(P_{2n},P_{2n},C_{2n})\geq 3n-1$ for integer $n\geq 2$.

Joint work with Sarinee Lotrakulnukid.

We consider every integer partition of $n$ as a nonnegative integral point $x \in \mathbb{R}^n$ with $x_i$ being the number of parts of size $i$ in the partition. The integer partition polytope $P_n$ is the convex hull of all partitions $x$ of $n.$ This approach revealed the previously unknown geometric structure of the set of partitions of $n$ and gave rise to many appealing questions. We prove that the following problems over $P_n$ can be solved in polynomial time using linear programming without the ellipsoid method:

• Extremality: for integer partition $x$ of $n$, decide if it is a vertex of $P_n$.
• Adjacency: for vertices $x,y$ of $P_n$, decide if they are adjacent on $P_n$.
• Separation: for $x \in \mathbb{R}^n$, find $h \in \mathbb{R}^n$ with $h^{^\intercal} x>h^{^\intercal} y$ $\forall y\in P_n$ or assert $x\in P_n.$
• Optimization: for $c\in\mathbb{R}^n$, find $x^*\in P_n$ which attains $\min\{c^{^\intercal} x:x\in P_n\}$ (included for completeness).

A key ingredient in the proof is the construction of a novel extended formulation for $P_n$. We prove that there exists a polynomial time constructible polytope $Q_n$ of size polynomial in $n$ such that $P_n$ is the projection of $Q_n$.

Joint work with Shmuel Onn.

We study conditions under which a finite simplicial complex $K$ can be mapped to $\mathbb R^d$ without higher-multiplicity intersections. An almost $r$-embedding is a map $f\colon K\to \mathbb R^d$ such that the images of any $r$ pairwise disjoint simplices of $K$ do not have a common point. We show that if $r$ is not a prime power and $d\geq 2r+1$, then there is a counterexample to the topological Tverberg conjecture, i.e., there is an almost $r$-embedding of the $(d+1)(r-1)$-simplex in $\mathbb R^d$. This improves on previous constructions of counterexamples (for $d\geq 3r$) based on a series of papers by M. Özaydin, M. Gromov, P. Blagojević, F. Frick, G. Ziegler, and I. Mabillard, U. Wagner, see surveys [P. Blagojević, G. Ziegler, Beyond the Borsuk-Ulam theorem: The topological Tverberg story] and [A. Skopenkov, A user's guide to disproof of topological Tverberg Conjecture]. The counterexamples are obtained by proving the following algebraic criterion in codimension 2: If $r\ge3$ and if $K$ is a finite $2(r-1)$-complex then there exists an almost $r$-embedding $K\to \mathbb R^{2r}$ if and only if there exists a general position PL map $f \colon K\to \mathbb R^{2r}$ such that the algebraic intersection number of the $f$-images of any $r$ pairwise disjoint simplices of $K$ is zero. This result can be restated in terms of cohomological obstructions or equivariant maps, and extends an analogous codimension $3$ criterion by the second and fourth author.

It follows from work of M. Freedman, V. Krushkal, and P. Teichner that the analogous criterion for $r=2$ is false. We give a short elementary proof of a beautiful lemma on singular $4$-dimensional Borromean rings, yielding an elementary proof of the counterexample. As another application of our methods, we classify ornaments $f\colon S^3 \sqcup S^3 \sqcup S^3\to \mathbb R^5$ up to ornament concordance.

Joint work with S. Avvakumov, I. Mabillard, and U. Wagner.

A median graph is a connected graph, such that for any three vertices $u,v,w$ there is exactly one vertex $x$ that lies simultaneously on a shortest $(u,v)$-path, a shortest $(v,w)$-path and a shortest $(w,u)$-path. Examples of median graphs are trees and hypercubes. We introduce and study a generalisation of tree decompositions where a graph can be modelled after any median graph, along with their respective width invariants. Depending on the notion of dimension we consider, this gives rise to hierachies of graph parameters that start from treewidth or pathwidth and converge to the clique number, while other variations characterise the chromatic number of a graph. We present connections to other concepts, such as characterisations of the parameters through a generalisation of the classical Cops and Robber game, where the robber plays against not just one, but many cop players. Finally, we discuss some applications in future work.

Graphs representing intersections of families of geometric objects are intensively studied for their practical applications and for their interesting theoretical properties. {In particular}, unit disk intersection graphs are interesting for applications in radio network modeling. We consider the problem of classical coloring, as well as the $L(2,1)$-labeling of such graphs.

Unit disk intersection graphs can be colored on-line with competitive ratio equal to 5. We improve this ratio by a new approach: using $j$-fold colorings of the so-called unit distance graph as a tool. (The unit distance graph is an infinite graph, whose vertex set is $\mathbb{R}^2$, and two points are adjacent if their Euclidean distance is exactly 1).

J. Fiala, A.V. Fishkin and F.V. Fomin [On distance constrained labeling of disk graphs, Theor. Comput. Sci. 326 (2004), pp. 261–292] presented an on-line algorithm for $L(2,1)$-labeling of unit disk intersection graphs with competitive ratio $50/3 \approx 16.66$. We improve this algorithm to the one with competitive ratio $40/3 \approx 13.33$. Moreover, using the $j$-fold coloring, we manage to improve this ratio for unit disks intersection graphs with a large clique number.

We also consider off-line $L(2,1)$-labeling. Z. Shao, R. Yeh, K.K. Poon and W.C. Shiu [The $L(2,1)$-labeling of $K_{1,n}$-free graphs and its applications, Appl. Math. Lett. 21 (2008), pp. 1188–1193] proved that $\lambda(G)\leq \frac{4}{5} \Delta^2 + 2\Delta$ for unit disk intersection graph $G$ with maximum degree $\Delta$. We improve this result to $\lambda(G)\leq \frac{3}{4} \Delta^2 + 3\Delta-3$. Moreover, from the work of Fiala, Fishkin and Fomin, we derive a bound $\lambda \leq 18\Delta + 18$, which is significantly better for large $\Delta$.

Joint work with Konstanty Junosza-Szaniawski, Paweł Rzążewski, and Joanna Sokół.