Mar 5, 14:00–15:00

Constructive Polynomial Partitioning for Lines in R^3 and its Applications

Esther Ezra (Bar Ilan)

A recent extension of Guth (2015) to the basic polynomial partitioning technique of Guth and Katz (2015) shows the existence of a partitioning polynomial, for a given set of $k$dimensional varieties in ${\reals}^d$, which subdivides space into open cells each of which meeting only a small fraction of the total number of varieties. For most instances, it is unknown how to efficiently obtain an explicit representation of such a partitioning polynomial. This, in particular, applies to the(simple) case of lines in 3space. In this work we present an efficient algorithmic (but somewhat suboptimal) construction for this setting. We then revisit the problem of eliminating depth cycles among $n$ nonvertical pairwise disjoint triangles in $3$space, recently been studied by Aronov etal. (2017) and de Berg (2017). Our main result is an algorithmic $O(n^{5/3+\eps})$ bound, for any $\eps > 0$, on the number of pieces one needs to cut the triangles such that the depth relation they induce does not contain cycles. The running time of our algorithm is comparable with the combinatorial bound.
Joint work with Boris Aronov.

Mar 12

Conical partitions for point sets

Gabor Damasdi (HUJI)

Mass partition theorems like the HamSandwich theorem have been extensively studied in recent decades. Conical partitions have been mainly considered in the planar case, but some higher dimensional results have been obtained by Vrecica and Zivaljevic and by Makeev. The proof of mass partition theorems usually follows the configuration space/test map procedure or some degree theoretic method, both of which heavily rely on topological results. This is especially true for results in higher dimensions, where our combinatorial tools are limited. We show a completely combinatorial proof for a discrete version of a theorem of Vrecica and Zivaljevic concerning conical partitions, and we show an equivalent result on the number of regions in a conical decomposition.

Mar 26

How to guess an ndigit number

Zilin Jiang (Technion)

In a deductive game for two players, SF and PGOM, SF conceals an ndigit number $x = x_1, ..., x_n,$ and PGOM, who knows n, tries to identify x by
asking a number of questions, which are answered by SF. Each question is an ndigit number $y = y_1, ..., y_n$; each answer is a number a(x, y), the
number of subscripts i such that $x_i = y_i$. Moreover we require the questions from PGOM are predetermined.
In this talk, I will show that the minimum number of questions required to determine x is (2+o(1))n / log n. A more general problem is to determine
the asymptotic formula of the metric dimension of Cartesian powers of a graph.
I will state the class of graphs for which the formula can be determined, and the smallest graphs for which we did not manage to settle.
Joint work with Nikita Polyanskii.

Apr 16

Applications of the Container Method

Charles Wolf

The Container Method, developed in 2015 by BaloghMorrisSamotij and SaxtonThomason, has produced numerous applications in combinatorics. We will discuss applications to triangle free graphs and an Erdos discrete geometry problem.

Apr 30

Grid peeling and the affine curveshortening flow

Gabriel Nivasch (Ariel University)

Experimentally, the convexlayer decomposition of subsets of the integer grid (“grid peeling”) seems to behave at the limit like the affine curveshortening flow. We offer some theoretical arguments to explain this phenomenon. In particular, we derive some rigorous results for the special case of peeling the quarterinfinite grid: We prove that, in this case, the number of grid points removed up to iteration $n$ is $\Theta(n^{3/2}\log{ n})$ and moreover, the boundary at iteration $n$ is sandwiched between two hyperbolas that are separated from each other by a constant factor.
Joint work with David Eppstein and Sariel HarPeled

May 14

CFColoring of String Graphs.

Alexandre Rok (BGU)

Based on a joint work with Chaya Keller and Shakhar Smorodinsky.
Given a hypergraph $H=(V, E)$ a function $c : V > N$ is said to be a CFcoloring of $H$ if for each hyperedge $e$ of $E$ there exists a vertex $v$ in $e$ s.t. $c(v) \neq c(v’)$ for $v’$ in $e \setminus {v}.$ That is, for each hyperedge some color appears exactly once. The least possible number of colors sufficient to CFcolor H is called the CFchromatic number of H. A graph G=(V,E) naturally gives rise to a hypergraph H=(V,E’) with E’={N(v) : v in V}, where N(v) stands for the neighborhood of v in G. Such an H is called open neighborhood hypergraph. By abuse, we say open CFcoloring of G instead of CFcoloring of the corresponding open neighborhood hypergraph. We call the least number of colors sufficient to open CFcolor G its open CFchromatic number. In this area, the main problem consists in finding good asymptotical bounds, in terms of the number of vertices or other graph parameters, on the CFchromatic number of members of some class of hypergraphs.
Motivated by problems of frequency assignment, the concept of CFcoloring was introduced by Even et al. in 2003 and was extensively studied since then. The research on open CFcoloring of graphs was initiated a few years later by Chelaris and Pach, who proved an upper bound of $O(\sqrt{n})$ on the open chromatic number of any graph on n vertices. On the other hand, it is not hard to come up with with graphs requiring $\Omega(\sqrt{n})$ colors in order to be open CFcolored. Open CFcoloring of graphs arising in geometric framework was also studied. One can, for example, mention the recent result of Keller and Smorodinsky that intersection graphs of Jordan regions can be open CFcolored with O(log n) colors.
A string graph is the intersection graph of a family of curves, i.e., subsets of $R^2$ homeomorphic to the interval [0,1]. Motivated by the celebrated conjecture on the maximum possible number of edges in kquasiplanar graphs on n vertices as well as practical applications to channel assignment, map labeling, and VLSI design coloring of string graphs was also studied a lot. Though both open CFcoloring of graphs and coloring of string graphs attracted the attention of numerous researchers nobody studied open CFcoloring of string graphs.
After briefly introducing the area of open CFcoloring of general graphs, I will focus on open CFcoloring and its weaker variant open kCFcoloring, where for each hyperedge some color is required to appear at least once and at most k times, of string graphs. In particular, I will talk about subclasses of the class of string graphs whose members can be efficiently open CFcolored, and some tools we use to prove such results. At the end, I will mention open problems and present a conjecture whose proof can be an important milestone in this freshly cooked area.

May 21

A Combinatorial Game and an Efficiently Computable Shift Rule for the Prefer Max De Bruijn Sequence

Yotam Svoray (BGU)

We present a twoplayer combinatorial game over a $k$ary shiftregister and analyze it. The game is defined such that, for each of the player, the only way to avoid losing is to play such that the next state of the game is the next window in the well known prefermax De Bruijn sequence. We then proceed to solve the game, i.e., to propose efficient algorithms that compute the moves for each player. Finally, we show how these algorithms can be combined into an efficiently computable shiftrule for the prefermax sequence.

May 28

TBA

Roman Glebov (HUJI)


Jun 4

A fractional version of Haemers’ bound

Chris Cox (Carnegie Mellon)

The Shannon capacity of a graph $G$ is defined as $\Theta(G):=\sup_n \alpha(G^{\otimes n})^{1/n}$ where $G^{\otimes n}$ is the $n$th tensor power of $G$. Determining $\Theta(G)$ is notoriously difficult, but there are two general upper bounds: Lovasz’s theta function and Haemers’ bound. In this talk, we present a fractional version of Haemers’ bound, originally due to Blasiak, which roughly works by embedding the vertices of $G$ as large subspaces under adjacency constraints. This bound is a common strengthening of both Haemers’ bound and the fractional chromatic number of a graph. We show that this fractional version outperforms any bound on the Shannon Capacity that could be attained through Haemers’ bound and show also that this bound in multiplicative, similar to Lovasz’s theta function. (Joint work with Boris Bukh)
