## General Information

Student: Peter Korcsok 444 Charles University in Prague peter.korcsok guess_what_is_here rutgers.edu Binary Kakeya Sets $L(p,q)$-labeling of Interval Graphs

## Binary Kakeya Sets

### Project Description

For $x,y \in \{0,1\}^n$ we define the line $L_{x,y} = \{x^i \oplus y \mid i = 0, ..., n-1\}$ of direction $x$ where $x^i$ denotes the $i$-th rotation of $x$. We say that a set $S \subseteq \{0,1\}^n$ is a Kakeya set if for every $x \in \{0,1\}^n$ there exists $y \in \{0,1\}^n$ such that $L_{x,y} \subseteq S$. Michal Koucký asks for the smallest Kakeya set for a given $n$.

### Previous work

• J. Bourgain Harmonic analysis and combinatorics: How much may they contribute to each other? IMU/Amer. Math. Soc., pages 13–32, 2000.
• Zeev Dvir On the size of Kakeya sets in finite fields, arXiv:0803.2336 [math.CO].

### Current activities

#### First week (June 2nd - June 6th)

• Introduction to the problem.
• Reading the article by Zeev Dvir.
• Few first observations.
• Computer program for finding all Kakeya sets for dimensions up to 5.

#### Second week (June 9th - June 13th)

• Slightly better upper bound.
• Computer program for finding out size of Kakeya sets for dimension 6. (Program failed because of using too much memory.)
• Some computer experiments on sets from the first week.
• Some small observations.

#### Third week (June 16th - June 20th)

• Computer program for finding out size of Kakeya sets for dimension 6 using external SAT solver. (Program killed because it would run too long.)
• Integer program for finding out size of Kakeya sets for dimension 6.
• Integer program for finding out size of Kakeya sets for dimension 7. (Program failed because of using too much memory.)
• More small observations.

#### Fourth week (June 23th - June 27th)

• Nontrivial lower bound - roughly $2^{n/2}$.
• Observation about "surronded" point - point whose neighborhood is subset of Kakeya set.
• Observation that each Kakeya set can be "normalized" - transformed in such way that it contains all unit vectors.
• Computer program for finding all normalized Kakeya sets for dimensions up to 5.
• Preparations for Cultural Day.

#### Fifth week (June 30th - July 4th)

• Computer program for finding all normalized Kakeya sets for dimension 6. (Program killed because it would run too long.)
• Some experiments on normalized sets from the previous week.
• Some improvements of the program for finding all normalized Kakeya sets for dimension 6. (Program is still slightly inefficient and still running at the end of the week.)
• Some partial results for finding all normalized Kakeya sets for dimension 6.

#### Sixth week (July 7th - July 11th)

Week has not finished yet.

#### Seventh week (July 14th - July 18th)

Week has not started yet.

## $L(p,q)$-labeling of Interval Graphs

### Project Description

Interval graphs are intersection graphs of a family of intervals of real numbers. $L(p,q)$-labeling of a graph $G$ is a mapping $l \colon V_G \to X$ where $X \subset \mathbb{Z}$ such that
• $|f(u) - f(v)| \geq p$ whenever the vertices $u$ and $v$ are connected by an edge,
• $|f(u) - f(v)| \geq q$ whenever there exists some vertex $w$ such that both $u$ and $v$ are neighbors of $w$.
Finally, span of graph $G$ is the smallest number $k$ such that there exists $L(p,q)$-labeling of $G$ using $X = \{ 0, \dots, k \}$. In this project, we look for a formula for the span of $L(2,1)$ for the class of interval graphs and its connection to the chromatic number of the graph and the maximum degree of the graph.

### Previous work

• Peter Che Bor Lam, Guohua Gu, Wai Chee Shiu, Tao-Ming Wang: On Distance Two Labelling of Unit Interval Graphs (see the paper).
• G.J. Chang; D. Kuo, The L(2,1)-labeling problem on graphs. SIAM J. Discrete Math. 9 (1996), 309--316.
• D. Sakai, Labelling chordal graphs: distance two condition. SIAM J. Disc. Math. 7 (1994), 133--140.
• J.R. Griggs; R.K. Yeh, Labelling graphs with a condition at distance 2. SIAM J. Discrete Math. 5 (1992), 586--595.

### Current activities

See progress on Veronica's webpage.