The Mathematics of Jiří Matoušek

About |
Participants |
Program |
Travel |
Photos |
Organisers |

Saturday 23.7. | Sunday 24.7. | Monday 25.7. | Tuesday 26.7. | Wednesday 27.7. | Thursday 28.7. | |
---|---|---|---|---|---|---|

9:00-9:45 | Registration (8:30-9:45) Intro (9:45-10:00) | Joel Spencer | Günter Ziegler | James R. Lee | Micha Sharir | Noga Alon |

10:00-10:30 | János Pach (until 10:45) | Coffee break | Coffee break | Coffee break | Coffee break | Coffee break |

10:30-11:15 | Coffee break (11-11:30) | Jan Kratochvíl | Roy Meshulam | Uli Wagner | Nikhil Bansal | Tibor Szabó |

11:30-12:15 | László Lovász | Pavel Valtr | Martin Tancer | József Solymosi | Nati Linial | Lunch Break |

12:15-14:30 | Lunch Break | Lunch Break | Lunch Break | Lunch Break | Lunch Break | |

Poster installation (from 13:00) | ||||||

14:30-15:15 | Emo Welzl | Endre Szemerédi | Pavle Blagojević | Boris Bukh | József Beck | Poster session (from 15:00) |

15:30-16:15 | Imre Bárány | Pankaj Agarwal | Eric Sedgwick | Igor Pak | Martin Loebl | |

16:30-17:15 | Günter Rote | Anders Björner | Jan Royt | Zuzana Patáková | ||

Welcome reception (from 17:30) | Karolinum excursion (18:00) | |||||

Banquet (from 19:00) |

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

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:

- Construction of high dimensional trees from sum complexes.
- Upper bounds on Betti numbers in terms of links, and nearly matching lower bounds via sum complexes.
- 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:

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

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:

- 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.
- 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).
- Erdos distinct distance problem. (Guth-Katz 2015) Any $N$ points in the plane have at least $cN/logN$ distinct pairwise distances.
- 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 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:

- 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)$.
- For every planar set $X$, $\gamma(X)$ can be bounded in terms of $\chi(X)$.
- There are sets $X$ in $R^5$ with $\chi(X)=3$, but $\gamma(X)$ arbitrarily large.

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

The poster can be of any size with recommended maximum format A0 according to the standard ISO 216. The dimensions of our stands for the posters are 117cm width x 145cm height.
We kindly ask you to **print your poster and bring it with you**.

Poster session was held in the university building at Malostranské náměstí 25 which is about 25 minutes by foot from the venue of the conference, here is a map how to get there.

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.*
##### 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}.$$
*

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.

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})$

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

Photos by Michal Krajíček.