Activities This Week

The Littlewood and the p-adic Littlewood conjectures are famous open problems on the border between number theory and dynamics. In a joint work with Faustin Adiceam and Fred Lunnon we show that the analogue of the p-adic Littlewood conjecture over $F_3((1/t))$ is false. The counterexample is given by the Laurent series whose coefficients are the regular paper folding sequence, and the method of proof is by reduction to the non vanishing of certain Hankel determinants. The proof is computer assisted and it uses substitution tilings of $Z^2$ and a generalisation of Dodson’s condensation algorithm for computing the determinant of any Hankel matrix.

גרפים מרחיבים הם נושא מחקר עדכני וחם, המושך תשומת לב רבה וגורם לשיתוף פעולה בין מדעני מחשב לבין תיאורטיקנים כבדים של תורות החבורות ותורת המספרים, ולא בכדי. מעבר לעניין המתמטי בגרפים מרחיבים, נראה שהם פותרים המון בעיות.

המעניין בגרפים המרחיבים הוא שיש להם תיאורים שקולים טבעיים במושגים של קומבינטוריקה, אלגברה לינארית ותורת ההסתברות (ועוד).

בהרצאה נציג את מושג הגרף המרחיב ונדון בתכונותיו, ונראה איך הוא שימושי כדי לפתור שתי בעיות מרכזיות ממדעי המחשב. לאחר מכן, עד כמה שהזמן יאפשר, נדון בפריצות הדרך המכוננות של התחום ובפני המחקר בתחום בימינו.

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.