Combinatorics Seminar External Ical Atom

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 3-space. 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$ non-vertical 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.

Mass partition theorems like the Ham-Sandwich 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.

In a deductive game for two players, SF and PGOM, SF conceals an n-digit 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 n-digit 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.

The Container Method, developed in 2015 by Balogh-Morris-Samotij and Saxton-Thomason, has produced numerous applications in combinatorics. We will discuss applications to triangle free graphs and an Erdos discrete geometry problem.

Experimentally, the convex-layer decomposition of subsets of the integer grid (“grid peeling”) seems to behave at the limit like the affine curve-shortening flow. We offer some theoretical arguments to explain this phenomenon. In particular, we derive some rigorous results for the special case of peeling the quarter-infinite 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 Har-Peled

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 CF-coloring 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 CF-color H is called the CF-chromatic 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 CF-coloring of G instead of CF-coloring of the corresponding open neighborhood hypergraph. We call the least number of colors sufficient to open CF-color G its open CF-chromatic 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 CF-chromatic number of members of some class of hypergraphs. Motivated by problems of frequency assignment, the concept of CF-coloring was introduced by Even et al. in 2003 and was extensively studied since then. The research on open CF-coloring 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 CF-colored. Open CF-coloring 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 CF-colored 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 k-quasi-planar 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 CF-coloring of graphs and coloring of string graphs attracted the attention of numerous researchers nobody studied open CF-coloring of string graphs. After briefly introducing the area of open CF-coloring of general graphs, I will focus on open CF-coloring and its weaker variant open k-CF-coloring, 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 CF-colored, 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.

We present a two-player combinatorial game over a $k$-ary shift-register 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 prefer-max 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 shift-rule for the prefer-max sequence.

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 out-performs 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)