Discrete Math Seminar By Amin Bahmanian: Extending Colorings of Triples Using Fewest Number of Color

Speaker:

Amin Bahmanian, Illinois State University

Title:

Extending Colorings of Triples Using Fewest Number of Color

Abstract:

Suppose that $X\subseteq Y$ and $|Y|\equiv 0 \Mod 3$. When can we extend a (proper) coloring of $\binom{X}{3}$ (all triples on a ground set $X$) to a coloring of $\binom{Y}{3}$ using fewest possible number of colors? It is necessary that the number of triples of each color in $\binom{X}{3}$ is at least $|X|-|Y|+|Y|/3$.  We establish a necessary and sufficient condition in terms of list coloring complete multigraphs. Using H\"aggkvist-Janssen's bound, we show that the number of triples of each color being at least $|X|/2-|Y|/6$ is sufficient. Finally we show that if $|Y|\geq 3|X|$, then any $q$-coloring of any subset of $\binom{X}{3}$ can be embedded into a $\binom{|Y|-1}{2}$-coloring of $\binom{Y}{3}$ as long as $q\leq \binom{|Y|-1}{2}-\binom{|X|-1}{2}$.

Bio:

Amin Bahmanian received his PhD in Mathematics from Auburn University. After a two-year postdoctoral fellowship at the University of Ottawa, he took a tenure track position at Illinois State University. He’s a recipient of a Young Investigator Grant from the National Security Agency. He is currently an associate professor, and his most recent research interests include list coloring problems motivated by solving higher dimensional sudoku puzzles. 

The Discrete Applied Math seminar will be held on most Fridays from 3:30 p.m. - 4:30 p.m. on Zoom during the Spring 2022 semester.

Discrete Applied Math seminar