Georgia Institute of Technology College of Sciences

TBA

TBA

An $r$-sunflower is a collection of $r$ sets such that the intersection of any two sets in the collection is identical. We analyze a random process which constructs a $w$-uniform $r$-sunflower free family starting with an empty family, and at each step, adding a set chosen uniformly at random from all choices that could be added without creating an $r$-sunflower with the previously chosen sets. To analyze this process, we extend results of Bennett and Bohman (arXiv:1308.3732v5 [math.CO]) who analyzed a general random process which adds one object at a time chosen uniformly at random from all objects that can be added without creating certain forbidden subsets. This talk is based on joint work with Professor Patrick Bennett.

Given an integer $k\ge1$, an edge-$k$-coloring of a graph $G$ is an assignment of $k$ colors $1,\ldots,k$ to the edges of $G$ such that no two adjacent edges receive the same color. A vertex-distinguishing (resp. sum-distinguishing) edge-$k$-coloring of $G$ is an edge-$k$-coloring such that for any two distinct vertices $u$ and $v$, the set (resp. sum) of colors taken from all the edges incident with $u$ is different from that taken from all the edges incident with $v$. The vertex-distinguishing chromatic index (resp. sum-distinguishing chromatic index), denoted $\chi'_{vd}(G)$ (resp.  $\chi'_{sd}(G)$), is the smallest value $k$ such that $G$ has a vertex-distinguishing edge-$k$-coloring (resp. sum-distinguishing edge-$k$-coloring). Let $G$ be a   $d$-regular graph on $n$ vertices, where $n$ is even and sufficiently large. We show that $\chi'_{vd}(G) =d+2$ if $d$ is arbitrarily close to $n/2$ from above, and $\chi'_{sd}(G) =d+2$ if $d\ge \frac{2n}{3}$. 

This is joint work with Yuping Gao and Guanghui Wang.