tag:www.math.bgu.ac.il,2005:/he/research/seminars/combinatorics-seminar/meetingsCombinatorics Seminar, בן-גוריוןDr. Charles Wolfcharlesi@bgu.ac.ilhttps://sites.google.com/view/charleswolf/2018-03-04T19:55:26+02:00tag:www.math.bgu.ac.il,2005:MeetingDecorator/3802018-03-04T19:55:26+02:002018-03-04T19:55:37+02:00<span class="mathjax">Esther Ezra: Constructive Polynomial Partitioning for Lines in R^3 and its Applications</span>מרץ 5, 14:00—15:00, 2018, -101<div class="mathjax"><p>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.</p>
<p>Joint work with Boris Aronov.</p></div>Esther EzraBar Ilantag:www.math.bgu.ac.il,2005:MeetingDecorator/3822018-03-12T17:45:35+02:002018-03-12T17:45:40+02:00<span class="mathjax">Gabor Damasdi: Conical partitions for point sets</span>מרץ 12, 14:10—15:10, 2018, -101<div class="mathjax"><p>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.</p></div>Gabor DamasdiHUJItag:www.math.bgu.ac.il,2005:MeetingDecorator/3882018-03-25T17:26:42+03:002018-03-25T17:26:55+03:00<span class="mathjax">Zilin Jiang: How to guess an n-digit number</span>מרץ 26, 14:10—15:10, 2018, -101<div class="mathjax">
<p>In a deductive game for two players, SF and PGOM, SF conceals an n-digit number <span class="kdmath">$x = x_1, ..., x_n,$</span> 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 <span class="kdmath">$y = y_1, ..., y_n$</span>; each answer is a number a(x, y), the
number of subscripts i such that <span class="kdmath">$x_i = y_i$</span>. Moreover we require the questions from PGOM are predetermined.</p>
<p>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.</p>
<p>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.</p>
<p>Joint work with Nikita Polyanskii.</p></div>Zilin JiangTechniontag:www.math.bgu.ac.il,2005:MeetingDecorator/3992018-04-16T10:30:10+03:002018-04-16T10:30:12+03:00<span class="mathjax">Charles Wolf: Applications of the Container Method</span>אפריל 16, 14:10—15:10, 2018, -101<div class="mathjax"><p>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.</p></div>Charles Wolftag:www.math.bgu.ac.il,2005:MeetingDecorator/4052018-04-28T21:32:16+03:002018-04-28T21:32:20+03:00<span class="mathjax">Gabriel Nivasch: Grid peeling and the affine curve-shortening flow</span>אפריל 30, 14:10—15:10, 2018, -101<div class="mathjax"><p>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</p></div>Gabriel NivaschAriel Universitytag:www.math.bgu.ac.il,2005:MeetingDecorator/4092018-05-10T10:09:17+03:002018-05-10T10:09:30+03:00<span class="mathjax">Alexandre Rok: CF-Coloring of String Graphs.</span>מאי 14, 14:10—15:10, 2018, -101<div class="mathjax"><p>Based on a joint work with Chaya Keller and Shakhar Smorodinsky.</p>
<p>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.</p></div>Alexandre RokBGUtag:www.math.bgu.ac.il,2005:MeetingDecorator/4102018-05-10T11:31:26+03:002018-05-15T11:34:03+03:00<span class="mathjax">Yotam Svoray: A Combinatorial Game and an Efficiently Computable Shift Rule for the Prefer Max De Bruijn Sequence</span>מאי 21, 14:10—15:10, 2018, -101<div class="mathjax"><p>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.</p></div>Yotam SvorayBGUtag:www.math.bgu.ac.il,2005:MeetingDecorator/4112018-05-10T11:32:23+03:002018-05-10T11:32:25+03:00<span class="mathjax">Roman Glebov: TBA</span>מאי 28, 14:10—15:10, 2018, -101Roman GlebovHUJItag:www.math.bgu.ac.il,2005:MeetingDecorator/4122018-05-10T11:33:16+03:002018-05-29T18:38:33+03:00<span class="mathjax">Chris Cox: A fractional version of Haemers‘ bound</span>יוני 4, 14:10—15:10, 2018, -101<div class="mathjax"><p>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)</p></div>Chris CoxCarnegie Mellontag:www.math.bgu.ac.il,2005:MeetingDecorator/4652018-11-07T14:42:09+02:002018-11-08T16:23:37+02:00<span class="mathjax">Roman Glebov: Finitely Forcible Graphons</span>נובמבר 13, 16:10—17:10, 2018, 201<div class="mathjax"><p>Abstract:
In extremal graph theory, we often consider large graphs that are in
the limit uniquely determined by finitely many densities of their
subgraphs. The corresponding limits (so-called graphons) are called
finitely forcible. Motivated by classical results in extremal
combinatorics as well as by recent developments in the study of
finitely forcible graphons, Lovasz and Szegedy made some conjectures
about the structure of such graphons. In particular, they conjectured
that the topological space of typical points of every finitely
forcible graphon is compact and finitely dimensional.
In joint results with D. Kral, T. Klimosova, and J. Volec, we could
disprove both conjectures.</p></div>Roman GlebovBGUtag:www.math.bgu.ac.il,2005:MeetingDecorator/4672018-11-19T13:41:02+02:002018-11-19T13:41:03+02:00<span class="mathjax">Noam Lifshitz: Sparse sharp thresholds and hypercontractivity</span>נובמבר 20, 16:00—17:00, 2018, 201<div class="mathjax"><p>The sharp threshold phenomenon is a central topic of research in the analysis of Boolean functions. Here, one aims to give sufficient conditions for a monotone Boolean function f to satisfy\mu_p(f)=o(\mu_q(f)), where q = p + o(p), and \mu_p(f) is the probability that f=1 on an input with independent coordinates, each taking the value 1 with probability p.</p>
<p>The dense regime, where \mu_p(f)=\Theta(1), is somewhat understood due to seminal works by Bourgain, Friedgut, Hatami, and Kalai. On the other hand, the sparse regime where \mu_p(f)=o(1) was out of reach of the available methods. However, the potential power of the sparse regime was suggested by Kahn and Kalai already in 2006.</p>
<p>In this talk we show that if a monotone Boolean function f with \mu_p(f)=o(1) satisfies some mild pseudo-randomness conditions then it exhibits a sharp threshold in the interval [p,q], with q = p+o(p). More specifically, our mild pseudo-randomness hypothesis is that the p-biased measure of f does not bump up to Θ(1) whenever we restrict f to a sub-cube of constant co-dimension, and our conclusion is that we can find q=p+o(p), such that \mu_p(f)=o(\mu_q(f)).</p></div>Noam LifshitzBar Ilantag:www.math.bgu.ac.il,2005:MeetingDecorator/4702018-11-25T13:21:29+02:002018-11-25T13:24:55+02:00<span class="mathjax">Lena Yuditsky: Almost all string graphs are intersection graphs of plane convex sets</span>נובמבר 27, 15:45—16:45, 2018, 201<div class="mathjax"><p>A <em>string graph</em> is the intersection graph of a family of continuous arcs in the plane. We prove the following structure theorem conjectured by Janson and Uzzell: The vertex set of <em>almost all</em> string graphs on $n$ vertices can be partitioned into <em>five</em> cliques such that some pair of them is not connected by any edge ($n\rightarrow\infty$). As a corollary, we obtain that <em>almost all</em> string graphs on $n$ vertices are intersection graphs of plane convex sets.</p>
<p>This is a joint work with Janos Pach and Bruce Reed.</p></div>Lena YuditskyBGUtag:www.math.bgu.ac.il,2005:MeetingDecorator/4922018-12-11T10:43:45+02:002018-12-11T10:43:46+02:00<span class="mathjax">Arnold Filtser: Steiner Point Removal with distortion O(log k), using the Relaxed Voronoi algorithm</span>דצמבר 4, 15:30—17:00, 2018, 201<div class="mathjax"><p>In the Steiner Point Removal (SPR) problem, we are given a weighted graph $G=(V,E)$ and a set of terminals $K\subset V$ of size $k$.
The objective is to find a minor $M$ of $G$ with only the terminals as its vertex set, such that distances between the terminals will be preserved up to a small multiplicative distortion.
Kamma, Krauthgamer and Nguyen [SICOMP2015] devised a ball-growing algorithm with exponential distributions to show that the distortion is at most $O(\log^5 k)$.
Cheung [SODA2018] improved the analysis of the same algorithm, bounding the distortion by $O(\log^2 k)$.
We devise a novel and simpler algorithm (called the Relaxed Voronoi algorithm) which incurs distortion $O(\log k)$. This algorithm can be implemented in almost linear time ($O(|E|\log |V|)$).</p></div>Arnold FiltserBGUtag:www.math.bgu.ac.il,2005:MeetingDecorator/4912018-12-11T10:37:09+02:002018-12-11T10:37:10+02:00<span class="mathjax">Yaar Solomon: Dense forests and low visibility</span>דצמבר 11, 15:45—16:45, 2018, 201<div class="mathjax"><p>In this talk we will discuss a type of visibility problem (in Euclidean spaces), with an infinite, discrete, set of obstacles. A dense forest refers to a discrete point set Y that satisfies dist(L,Y)=0 for every ray L in $R^d$, and moreover, the distance between Y and every line segment decays uniformly, as the length of the segments tend to infinity. The constructions of dense forests that are known today were given using tools from Diophantine approximations (Bishop+Peres), homogeneous dynamics (Solomon-Weiss), Fourier analysis (Adiceam), the Lovász local lemma (Alon), and more tools form number theory and dynamics (Adiceam-Solomon-Weiss). We will discuss some of these constructions of dense forests, as well as the speed of which the visibility decays in them.
Some of the results that I will discuss come from a joint work with Faustin Adiceam and with Barak Weiss.</p></div>Yaar SolomonBGUtag:www.math.bgu.ac.il,2005:MeetingDecorator/4932018-12-11T10:45:33+02:002018-12-17T13:18:51+02:00<span class="mathjax">Ilan Karpas: Frankl‘s conjecture for dense families.</span>דצמבר 18, 10:45—11:45, 2018, -101<div class="mathjax"><p>A union closed family F is a family of sets, so that for any two sets A,B in F,
A$\cup$B is also on F. Frankl conjectured in 1979 that for any union-closed family F of subsets of [n], there is some element i $\in$ [n] that appears in at least half the members of F.</p>
<table>
<tbody>
<tr>
<td>We prove that the conjecture is true if</td>
<td>F</td>
<td>>= 2^{n-1}, using tools from boolean analysis.</td>
</tr>
</tbody>
</table></div>Ilan Karpastag:www.math.bgu.ac.il,2005:MeetingDecorator/4942018-12-11T10:47:52+02:002019-05-02T17:03:13+03:00<span class="mathjax">Bruno Jartoux: Piercing Edges with Subsets in Geometric Hypergraphs</span>דצמבר 25, 10:45—11:45, 2018, -101Bruno JartouxBGUtag:www.math.bgu.ac.il,2005:MeetingDecorator/4972018-12-30T14:57:22+02:002018-12-30T14:57:24+02:00<span class="mathjax">Chaya Keller: Improved lower and upper bounds on the Hadwiger-Debrunner numbers</span>ינואר 1, 10:45—11:45, 2019, -101<div class="mathjax"><p>A family of sets F is said to satisfy the (p,q)-property if among any p sets in F, some q have a non-empty intersection. Hadwiger and Debrunner (1957) conjectured that for any p > q > d there exists a constant c = c_d(p,q), such that any family of compact convex sets in R^d that satisfies the (p,q)-property, can be pierced by at most c points. Helly‘s Theorem is equivalent to the fact that c_d(p,p)=1 (p > d).</p>
<p>In a celebrated result from 1992, Alon and Kleitman proved the conjecture. However, obtaining sharp bounds on the minimal such c_d(p,q), called `the Hadwiger-Debrunner numbers‘, is still a major open problem in combinatorial geometry.</p>
<p>In this talk we present improved upper and lower bounds on the Hadwiger-Debrunner numbers, the latter using the hypergraph container method.
Based on joint works with Shakhar Smorodinsky and Gabor Tardos.</p></div>Chaya KellerTechniontag:www.math.bgu.ac.il,2005:MeetingDecorator/4982019-01-06T13:26:57+02:002019-01-06T13:26:58+02:00<span class="mathjax">Roman Glebov: In extremal graph theory, we often consider large graphs that are in the limit uniquely determined by finitely many densities of their subgraphs. The corresponding limits (so-called graphons) are called finitely forcible. Motivated by classical results in extremal combinatorics as well as by recent developments in the study of finitely forcible graphons, Lovasz and Szegedy made some conjectures about the structure of such graphons. In particular, they conjectured that the topological space of typical points of every finitely forcible graphon is compact and finitely dimensional. In joint results with D. Kral, T. Klimosova, and J. Volec, we could disprove both conjectures.</span>ינואר 8, 10:45—11:45, 2019, -101Roman GlebovBGUtag:www.math.bgu.ac.il,2005:MeetingDecorator/5002019-01-13T11:22:08+02:002019-01-13T11:22:09+02:00<span class="mathjax">Csaba Toth: Polygonizations for Disjoint Line Segments</span>ינואר 15, 10:45—11:45, 2019, -101<div class="mathjax"><p>Given a planar straight-line graph $G=(V,E)$ in $\mathbb{R}^2$, a
<em>circumscribing polygon</em> of $G$ is a simple polygon $P$ whose vertex
set is $V$, and every edge in $E$ is either an edge or an internal
diagonal of $P$. A circumscribing polygon is a \emph{polygonization} for
$G$ if every edge in $E$ is an edge of $P$.</p>
<p>We prove that every arrangement of $n$ disjoint line segments in the
plane (i.e., a geometric perfect matching) has a subset of size
$\Omega(\sqrt{n})$ that admits a circumscribing polygon, which is the
first improvement on this bound in 20 years. We explore relations
between circumscribing polygons and other problems in combinatorial
geometry, and generalizations to $\mathbb{R}^3$.</p>
<p>We show that it is NP-complete to decide whether a given graph $G$
admits a circumscribing polygon, even if $G$ is 2-regular. Settling a
30-year old conjecture by Rappaport, we also show that it is
NP-complete to determine whether a geometric matching admits a
polygonization.
(Joint work with Hugo A. Akitaya, Matias Korman, Mikhail Rudoy, and
Diane L. Souvaine.)</p></div>Csaba TothCSUNtag:www.math.bgu.ac.il,2005:MeetingDecorator/5012019-01-13T11:25:06+02:002019-01-13T11:25:22+02:00<span class="mathjax">Andrey Kupavskii: Simple juntas for shifted families</span>ינואר 15, 14:15—15:15, 2019, -101<div class="mathjax"><p>We say that a family F of k-element sets is a j-junta if there is a set J of size j such that, for any set, its presence in F depends on its intersection with J only. Approximating arbitrary families by j-juntas with small j is a recent powerful technique in extremal set theory.
The weak point of all known approximation by juntas results is that they work in the range n>Ck, where C is an extremely fast growing function of the input parameters. In this talk, we present a simple and essentially best possible junta approximation result for an important class of families, called shifted. As an application, we present some progress in the question of Aharoni and Howard on families with no cross-matching. Joint work with Peter Frankl.</p></div>Andrey KupavskiiOxfordtag:www.math.bgu.ac.il,2005:MeetingDecorator/5272019-04-28T11:26:42+03:002019-04-28T11:26:42+03:00<span class="mathjax">Minki Kim: Rainbow independent sets in certain classes of graphs</span>אפריל 30, 13:00—14:00, 2019, -101<div class="mathjax"><p>Let $F = (F_1, \ldots, F_m)$ be a collection of (not neccessarily distinct) sets.
A (partial) rainbow set for $F$ is a set of the form $R = {x_{i_1}, \ldots, x_{i_k}}$ of distinct elements, where $1 \leq i_1 < \cdots < i_k \leq m$ and $x_{i_j}$ is an element of $F_{i_j}$.
We are interested in the following question: given sufficiently many independent sets of size $a$ in a graph belonging to a certain class, there exists a rainbow independent set of size $b$.
In this talk, I will present our recent results on this question, mainly regarding $H$-(induced) free graphs and graphs of bounded maximum degree.
This is joint work with Ron Aharoni, Joseph Briggs and Jinha Kim.</p></div>Minki KimTechniontag:www.math.bgu.ac.il,2005:MeetingDecorator/5382019-05-13T11:02:23+03:002019-05-13T11:02:23+03:00<span class="mathjax">Roman Glebov: The number of Hamiltonian decompositions of regular graphs.</span>מאי 14, 13:00—14:00, 2019, -101<div class="mathjax"><p>A Hamiltonian decomposition of $\Gamma$ is a partition of its edge set
into disjoint Hamilton cycles. One of the oldest results in graph
theory is Walecki‘s theorem from the 19th century, showing that a
complete graph $K_n$ on an odd number of vertices $n$ has a
Hamiltonian decomposition. This result was recently greatly extended
by Kuhn and Osthus. They proved that every $r$-regular $n$-vertex
graph $\Gamma$ with even degree $r=cn$ for some fixed $c>1/2$ has a
Hamiltonian decomposition, provided $n=n(c)$ is sufficiently large. In
this talk we address the natural question of estimating $H(\Gamma)$,
the number of such decompositions of $\Gamma$. The main result is that
$H(\Gamma)=r^{(1+o(1))nr/2}$. In particular, the number of Hamiltonian
decompositions of $K_n$ is $n^{(1+o(1))n^2/2}$.</p>
<p>Joint work with Zur Luria and Benny Sudakov.</p></div>Roman GlebovBGU