JZJunchi Zhang
Junchi Zhang
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Junchi Zhang has a total of 8 co-authors. Here are the top co-authors by number of shared publications:
- Tianyi Tao
School of Mathematical Sciences Fudan University 200433 Shanghai P. R. China
2 shared publications - Alex Toole
Mathematics Department Palomar College San Marcos California USA
1 shared publication - Chaoliang Tang
Shanghai Center for Mathematical Sciences Fudan University 220 Handan Road 200433 Shanghai China
1 shared publication - Mohammed Alshammari
Department of Mathematics and Statistics University of Strathclyde 26 Richmond Street G1 1XH Glasgow United Kingdom
1 shared publication - Seonghyuk Im
KAIST
1 shared publication - Sergey Kitaev
Department of Mathematics and Statistics, University of Strathclyde, Glasgow, UK
1 shared publication
Latest Publications
- Open Access
New lower bounds on the non-repetitive chromatic number of some graphs
A graph \( G \) is said to be (vertex) non-repetitively colored if no simple path in \( G \) has a sequence of vertex colors that forms a repetition. Formally, a coloring \( c: V(G) \to \{1, 2, \dots, k\} \) is non-repetitive if, for every path \(\langle v_1, v_2, \dots, v_{2m} \rangle\) in \( G \), the sequence of colors \( c(v_1), c(v_2), \dots, c(v_{2m}) \) is not of the form \( ww \), where \( w \) is a sequence of \( m \) colors. The minimum number of colors required for such a coloring is called the \emph{non-repetitive chromatic number} of \(G\), denoted by \(π(G)\). In this paper, we primarily prove that \(π(P \square P) \ge 6\) and \(π(P \boxtimes P) \ge 9\), where \( P \square P \) and \( P \boxtimes P \) are the Cartesian product and the strong product of two infinite paths, respectively. This improves upon the previous best lower bounds.Open AccessNew lower bounds on the non-repetitive chromatic number of some graphs
A graph \( G \) is said to be (vertex) non-repetitively colored if no simple path in \( G \) has a sequence of vertex colors that forms a repetition. Formally, a coloring \( c: V(G) \to \{1, 2, \dots, k\} \) is non-repetitive if, for every path \(\langle v_1, v_2, \dots, v_{2m} \rangle\) in \( G \), the sequence of colors \( c(v_1), c(v_2), \dots, c(v_{2m}) \) is not of the form \( ww \), where \( w \) is a sequence of \( m \) colors. The minimum number of colors required for such a coloring is called the \emph{non-repetitive chromatic number} of \(G\), denoted by \(π(G)\). In this paper, we primarily prove that \(π(P \square P) \ge 6\) and \(π(P \boxtimes P) \ge 9\), where \( P \square P \) and \( P \boxtimes P \) are the Cartesian product and the strong product of two infinite paths, respectively. This improves upon the previous best lower bounds. - Open Access
Unbounded degree spanning hypertrees in Dirac hypergraphs
In 2001, Komlós, Sárközy, and Szemerédi proved that every sufficiently large $n$-vertex graph with minimum degree at least $\left(1/2+γ\right)n$ contains all spanning trees with maximum degree at most $cn/\log n$. We extend this result to hypergraphs by considering loose hypertrees, which are linear hypergraphs obtained by successively adding edges that share exactly one vertex with a previous edge. For all $k > \ell \geq 2$, we determine asymptotically optimal $\ell$-degree conditions that ensure the existence of all rooted spanning loose hypertrees, without any degree condition, in terms of the $(\ell-1)$-degree threshold for the existence of a perfect matching in $(k-1)$-graphs. As a corollary, we also asymptotically determine the $\ell$-degree threshold for the existence of bounded degree spanning loose hypertrees in $k$-graphs for $k/2 < \ell < k$, confirming a conjecture of Pehova and Petrova in this range. In our proof, we avoid the use of Szemerédi's regularity lemma.Open AccessUnbounded degree spanning hypertrees in Dirac hypergraphs
In 2001, Komlós, Sárközy, and Szemerédi proved that every sufficiently large $n$-vertex graph with minimum degree at least $\left(1/2+γ\right)n$ contains all spanning trees with maximum degree at most $cn/\log n$. We extend this result to hypergraphs by considering loose hypertrees, which are linear hypergraphs obtained by successively adding edges that share exactly one vertex with a previous edge. For all $k > \ell \geq 2$, we determine asymptotically optimal $\ell$-degree conditions that ensure the existence of all rooted spanning loose hypertrees, without any degree condition, in terms of the $(\ell-1)$-degree threshold for the existence of a perfect matching in $(k-1)$-graphs. As a corollary, we also asymptotically determine the $\ell$-degree threshold for the existence of bounded degree spanning loose hypertrees in $k$-graphs for $k/2 < \ell < k$, confirming a conjecture of Pehova and Petrova in this range. In our proof, we avoid the use of Szemerédi's regularity lemma. - Open Access
On 1-11-representability and multi-1-11-representability of graphs
Jeff Remmel introduced the concept of a $k$-11-representable graph in 2017. This concept was first explored by Cheon et al. in 2019, who considered it as a natural extension of word-representable graphs, which are exactly 0-11-representable graphs. A graph $G$ is $k$-11-representable if it can be represented by a word $w$ such that for any edge (resp., non-edge) $xy$ in $G$ the subsequence of $w$ formed by $x$ and $y$ contains at most $k$ (resp., at least $k+1$) pairs of consecutive equal letters. A remarkable result of Cheon at al. is that any graph is 2-11-representable, while it is still unknown whether every graph is 1-11-representable. Cheon et al. showed that the class of 1-11-representable graphs is strictly larger than that of word-representable graphs, and they introduced a useful toolbox to study 1-11-representable graphs, which was extended by additional powerful tools suggested by Futorny et al. in 2024. In this paper, we prove that all graphs on at most 8 vertices are 1-11-representable hence extending the known fact that all graphs on at most 7 vertices are 1-11-representable. Also, we discuss applications of our main result in the study of multi-1-11-representation of graphs we introduce in this paper analogously to the notion of multi-word-representation of graphs suggested by Kenkireth and Malhotra in 2023.Open AccessOn 1-11-representability and multi-1-11-representability of graphs
Jeff Remmel introduced the concept of a $k$-11-representable graph in 2017. This concept was first explored by Cheon et al. in 2019, who considered it as a natural extension of word-representable graphs, which are exactly 0-11-representable graphs. A graph $G$ is $k$-11-representable if it can be represented by a word $w$ such that for any edge (resp., non-edge) $xy$ in $G$ the subsequence of $w$ formed by $x$ and $y$ contains at most $k$ (resp., at least $k+1$) pairs of consecutive equal letters. A remarkable result of Cheon at al. is that any graph is 2-11-representable, while it is still unknown whether every graph is 1-11-representable. Cheon et al. showed that the class of 1-11-representable graphs is strictly larger than that of word-representable graphs, and they introduced a useful toolbox to study 1-11-representable graphs, which was extended by additional powerful tools suggested by Futorny et al. in 2024. In this paper, we prove that all graphs on at most 8 vertices are 1-11-representable hence extending the known fact that all graphs on at most 7 vertices are 1-11-representable. Also, we discuss applications of our main result in the study of multi-1-11-representation of graphs we introduce in this paper analogously to the notion of multi-word-representation of graphs suggested by Kenkireth and Malhotra in 2023.