Zhanar Berikkyzy

Given a graph $G$, an exact $r$-coloring of $G$ is a surjective function $c:V(G) \to [1,\dots,r]$. An arithmetic progression in $G$ of length $j$ with common difference $d$ is a set of vertices $\{v_1,\dots, v_j\}$ such that $dist(v_i,v_{i+1}) = d$ for $1\le i < j$. An arithmetic progression is rainbow if all of the vertices are colored distinctly. The fewest number of colors that guarantees a rainbow arithmetic progression of length three is called the anti-van der Waerden number of $G$ and is denoted $aw(G,3)$. It is known that $3 \le aw(G\square H,3) \le 4$. Here we determine exact values $aw(T\square T',3)$ for some trees $T$ and $T'$, determine $aw(G\square T,3)$ for some trees $T$, and determine $aw(G\square H,3)$ for some graphs $G$ and $H$.

A fundamental identity in the representation theory of the partition algeba is $n^k = \sum_{\lambda} f^\lambda m_k^\lambda$ for $n \geq 2k$, where $\lambda$ ranges over integer partitions of $n$, $f^\lambda$ is the number of standard Young tableaux of shape $\lambda$, and $m_k^\lambda$ is the number of vacillating tableaux of shape $\lambda$ and length $2k$. Using a combination of RSK insertion and jeu de taquin, Halverson and Lewandowski constructed a bijection $DI_n^k$ that maps each integer sequence in $[n]^k$ to a pair consisting of a standard Young tableau and a vacillating tableau. In this paper, we show that for a given integer sequence $\boldsymbol{i}$, when $n$ is sufficiently large, the vacillating tableaux determined by $DI_n^k(\boldsymbol{i})$ become stable when $n \rightarrow \infty$; the limit is called the limiting vacillating tableau for $\boldsymbol{i}$. We give a characterization of the set of limiting vacillating tableaux and presents explicit formulas that enumerate those vacillating tableaux.

Let $G$ be a simple graph and $v$ be a vertex of $G$. The triangle-degree of $v$ in $G$ is the number of triangles that contain $v$. While every graph has at least two vertices with the same degree, there are graphs in which every vertex has a distinct triangle-degree. In this paper, we construct an infinite family of graphs with this property. We also study the vertex degrees and size of graphs with this property.

In this paper, we work with simple and finite graphs. We study a generalization of the \emph{Cage Problem}, which has been widely studied since cages were introduced by Tutte \cite{T47} in 1947 and after Erd\" os and Sachs \cite{ES63} proved their existence in 1963. An \emph{$(r,g)$-graph} is an $r$-regular graph in which the shortest cycle has length equal to $g$; that is, it is an $r$-regular graph with girth $g$. An \emph{$(r,g)$-cage} is an $(r,g)$-graph with the smallest possible number of vertices among all $(r,g)$-graphs; the order of an $(r,g)$-cage is denoted by $n(r,g)$. The Cage Problem consists of finding $(r,g)$-cages; it is well-known that $(r,g)$-cages have been determined only for very limited sets of parameter pairs $(r, g)$. There exists a simple lower bound for $n(r,g)$, given by Moore and denoted by $n_0(r,g)$. The cages that attain this bound are called \emph{Moore cages}.

Given a coloring of group elements, a rainbow solution to an equation is a solution whose every element is assigned a different color. The rainbow number of $\mathbb{Z}_n$ for an equation $eq$, denoted $rb(\mathbb{Z}_n,eq)$, is the smallest number of colors $r$ such that every exact $r$-coloring of $\mathbb{Z}_n$ admits a rainbow solution to the equation $eq$. We prove that for every exact $4$-coloring of $\mathbb{Z}_p$, where $p\geq 3$ is prime, there exists a rainbow solution to the Sidon equation $x_1+x_2=x_3+x_4$. Furthermore, we determine the rainbow number of $\mathbb{Z}_n$ for the Sidon equation.