Search

We investigate the longstanding problem of determining the maximum size of a $(d+1)$-uniform set system with VC-dimension at most $d$. Since the seminal 1984 work of Frankl and Pach, which established the elegant upper bound $\binom{n}{d}$, this question has resisted significant progress. The best-known lower bound is $\binom{n-1}{d} + \binom{n-4}{d-2}$, obtained by Ahlswede and Khachatrian, leaving a substantial gap of $\binom{n-1}{d-1}-\binom{n-4}{d-2}$. Despite decades of effort, improvements to the Frankl--Pach bound have been incremental at best: Mubayi and Zhao introduced an $\Omega_d(\log{n})$ improvement for prime powers $d$, while Ge, Xu, Yip, Zhang, and Zhao achieved a gain of 1 for general $d$. In this work, we provide a purely combinatorial approach that significantly sharpens the Frankl--Pach upper bound. Specifically, for large $n$, we demonstrate that the Frankl--Pach bound can be improved to $\binom{n}{d} - \binom{n-1}{d-1} + O_d(n^{d-1 - \frac{1}{4d-2}})=\binom{n-1}{d}+O_d(n^{d-1 - \frac{1}{4d-2}})$. This result completely removes the main term $\binom{n-1}{d-1}$ from the previous gap between the known lower and upper bounds. It also offers fresh insights into the combinatorial structure of uniform set systems with small VC-dimension. In addition, the original Erd\H{o}s--Frankl--Pach conjecture, which sought to generalize the EKR theorem in the 1980s, has been disproven. We propose a new refined conjecture that might establish a sturdier bridge between VC-dimension and the EKR theorem, and we verify several specific cases of this conjecture, which is of independent interest., Comment: 25 pages

The strong Ramsey game $R(\mathcal{B}, H)$ is a two-player game played on a graph $\mathcal{B}$, referred to as the board, with a target graph $H$. In this game, two players, $P_1$ and $P_2$, alternately claim unclaimed edges of $\mathcal{B}$, starting with $P_1$. The goal is to claim a subgraph isomorphic to $H$, with the first player achieving this declared the winner. A fundamental open question, persisting for over three decades, asks whether there exists a graph $H$ such that in the game $R(K_n, H)$, $P_1$ does not have a winning strategy in a bounded number of moves as $n \to \infty$. In this paper, we shift the focus to the variant $R(K_n \sqcup K_n, H)$, introduced by David, Hartarsky, and Tiba, where the board $K_n \sqcup K_n$ consists of two disjoint copies of $K_n$. We prove that there exist infinitely many graphs $H$ such that $P_1$ cannot win in $R(K_n \sqcup K_n, H)$ within a bounded number of moves through a concise proof. This perhaps provides evidence for the existence of examples to the above longstanding open problem., Comment: 12 pages

For any positive integers $n\ge d+1\ge 3$, what is the maximum size of a $(d+1)$-uniform set system in $[n]$ with VC-dimension at most $d$? In 1984, Frankl and Pach initiated the study of this fundamental problem and provided an upper bound $\binom{n}{d}$ via an elegant algebraic proof. Surprisingly, in 2007, Mubayi and Zhao showed that when $n$ is sufficiently large and $d$ is a prime power, the Frankl-Pach upper bound is not tight. They also remarked that their method requires $d$ to be a prime power, and asked for new ideas to improve the Frankl-Pach upper bound without extra assumptions on $n$ and $d$. In this paper, we provide an improvement for any $d\ge 2$ and $n\ge 2d+2$, which demonstrates that the long-standing Frankl-Pach upper bound $\binom{n}{d}$ is not tight for any uniformity. Our proof combines a simple yet powerful polynomial method and structural analysis., Comment: 7 pages

Reconstructing 3D models from single-view images is a long-standing problem in computer vision. The latest advances for single-image 3D reconstruction extract a textual description from the input image and further utilize it to synthesize 3D models. However, existing methods focus on capturing a single key attribute of the image (e.g., object type, artistic style) and fail to consider the multi-perspective information required for accurate 3D reconstruction, such as object shape and material properties. Besides, the reliance on Neural Radiance Fields hinders their ability to reconstruct intricate surfaces and texture details. In this work, we propose MTFusion, which leverages both image data and textual descriptions for high-fidelity 3D reconstruction. Our approach consists of two stages. First, we adopt a novel multi-word textual inversion technique to extract a detailed text description capturing the image's characteristics. Then, we use this description and the image to generate a 3D model with FlexiCubes. Additionally, MTFusion enhances FlexiCubes by employing a special decoder network for Signed Distance Functions, leading to faster training and finer surface representation. Extensive evaluations demonstrate that our MTFusion surpasses existing image-to-3D methods on a wide range of synthetic and real-world images. Furthermore, the ablation study proves the effectiveness of our network designs., Comment: PRCV 2024

Celebrated results often unfold like episodes in a long-running series. In the field of extremal set thoery, Erd\H{o}s, Ko, and Rado in 1961 established that any $k$-uniform intersecting family on $[n]$ has a maximum size of $\binom{n-1}{k-1}$, with the unique extremal structure being a star. In 1967, Hilton and Milner followed up with a pivotal result, showing that if such a family is not a star, its size is at most $\binom{n-1}{k-1} - \binom{n-k-1}{k-1} + 1$, and they identified the corresponding extremal structures. In recent years, Han and Kohayakawa, Kostochka and Mubayi, and Huang and Peng have provided the second and third levels of stability results in this line of research. In this paper, we provide a unified approach to proving the stability result for the Erd\H{o}s-Ko-Rado theorem at any level. Our framework primarily relies on a robust linear algebra method, which leverages appropriate non-shadows to effectively handle the structural complexities of these intersecting families., Comment: 16 pages

Generating high-quality meshes with complex structures and realistic surfaces is the primary goal of 3D generative models. Existing methods typically employ sequence data or deformable tetrahedral grids for mesh generation. However, sequence-based methods have difficulty producing complex structures with many faces due to memory limits. The deformable tetrahedral grid-based method MeshDiffusion fails to recover realistic surfaces due to the inherent ambiguity in deformable grids. We propose the GenUDC framework to address these challenges by leveraging the Unsigned Dual Contouring (UDC) as the mesh representation. UDC discretizes a mesh in a regular grid and divides it into the face and vertex parts, recovering both complex structures and fine details. As a result, the one-to-one mapping between UDC and mesh resolves the ambiguity problem. In addition, GenUDC adopts a two-stage, coarse-to-fine generative process for 3D mesh generation. It first generates the face part as a rough shape and then the vertex part to craft a detailed shape. Extensive evaluations demonstrate the superiority of UDC as a mesh representation and the favorable performance of GenUDC in mesh generation. The code and trained models are available at https://github.com/TrepangCat/GenUDC., Comment: ACMMM 2024, code:https://github.com/TrepangCat/GenUDC

A well-known theorem of Nikiforov asserts that any graph with a positive $K_{r}$-density contains a logarithmic blowup of $K_r$. In this paper, we explore variants of Nikiforov's result in the following form. Given $r,t\in\mathbb{N}$, when a positive $K_{r}$-density implies the existence of a significantly larger (with almost linear size) blowup of $K_t$? Our results include: For an $n$-vertex ordered graph $G$ with no induced monotone path $P_{6}$, if its complement $\overline{G}$ has positive triangle density, then $\overline{G}$ contains a biclique of size $\Omega(\frac{n}{\log{n}})$. This strengthens a recent result of Pach and Tomon. For general $k$, let $g(k)$ be the minimum $r\in \mathbb{N}$ such that for any $n$-vertex ordered graph $G$ with no induced monotone $P_{2k}$, if $\overline{G}$ has positive $K_r$-density, then $\overline{G}$ contains a biclique of size $\Omega(\frac{n}{\log{n}})$. Using concentration of measure and the isodiametric inequality on high dimensional spheres, we provide constructions showing that, surprisingly, $g(k)$ grows quadratically. On the other hand, we relate the problem of upper bounding $g(k)$ to a certain Ramsey problem and determine $g(k)$ up to a factor of 2. Any incomparability graph with positive $K_{r}$-density contains a blowup of $K_r$ of size $\Omega(\frac{n}{\log{n}}).$ This confirms a conjecture of Tomon in a stronger form. In doing so, we obtain a strong regularity type lemma for incomparability graphs with no large blowups of a clique, which is of independent interest. We also prove that any $r$-comparability graph with positive $K_{(2h-2)^{r}+1}$-density contains a blowup of $K_h$ of size $\Omega(n)$, where the constant $(2h-2)^{r}+1$ is optimal. The $\frac{n}{\log n}$ size of the blowups in all our results are optimal up to a constant factor.

A widely open conjecture proposed by Bollob\'as, Erd\H{o}s, and Tuza in the early 1990s states that for any $n$-vertex graph $G$, if the independence number $\alpha(G) = \Omega(n)$, then there is a subset $T \subseteq V(G)$ with $|T| = o(n)$ such that $T$ intersects all maximum independent sets of $G$. In this paper, we prove that this conjecture holds for graphs that do not contain an induced $K_{s,t}$ for fixed $t \ge s$. Our proof leverages the probabilistic method at an appropriate juncture., Comment: 5 pages

For an $n$-vertex graph $G$, let $h(G)$ denote the smallest size of a subset of $V(G)$ such that it intersects every maximum independent set of $G$. A conjecture posed by Bollob\'{a}s, Erd\H{o}s and Tuza in early 90s remains widely open, asserting that for any $n$-vertex graph $G$, if the independence number $\alpha(G) =\Omega(n) $, then $h(G) = o(n)$. In this paper, we establish the validity of this conjecture for various classes of graphs, Our main contributions include: \begin{enumerate} \item We provide a novel unified framework to find sub-linear hitting sets for graphs with certain locally sparse properties. Based on this framework, we can find hitting sets of size at most $O(\frac{n}{\log{n}})$ in any $n$-vertex even-hole-free graph (in particular, chordal graph) and in any $n$-vertex disk graph, with linear independence numbers. \item Utilizing geometric observations and combinatorial arguments, we show that any $n$-vertex circle graph $G$ with linear independence number satisfies $h(G)\le O(\sqrt{n})$. Moreover, we extend this methodology to more general classes of graphs. \item We show the conjecture holds for those hereditary graphs having sublinear balanced separators. \end{enumerate} We also show that $h(G)$ can be upper bounded by constants for several sporadic families of graphs with large independence numbers., Comment: The results on (in)comparability graphs have been removed, as we were informed that perfect graphs satisfy the conjecture. Meanwhile, the results on circle graphs have been strengthened and extended

Given a graph $G$, denote by $h(G)$ the smallest size of a subset of $V(G)$ which intersects every maximum independent set of $G$. We prove that any graph $G$ without induced matching of size $t$ satisfies $h(G)\le \omega(G)^{3t-3+o(1)}$. This resolves a conjecture of Hajebi, Li and Spirkl (Hitting all maximum stable sets in $P_{5}$-free graphs, JCTB 2024).

We establish a novel connection between the well-known chromatic threshold problem in extremal combinatorics and the celebrated $(p,q)$-theorem in discrete geometry. In particular, for a graph $G$ with bounded clique number and a natural density condition, we prove a $(p,q)$-theorem for an abstract convexity space associated with $G$. Our result strengthens those of Thomassen and Nikiforov on the chromatic threshold of cliques. Our $(p,q)$-theorem can also be viewed as a $\chi$-boundedness result for (what we call) ultra maximal $K_r$-free graphs. We further show that the graphs under study are blow-ups of constant size graphs, improving a result of Oberkampf and Schacht on homomorphism threshold of cliques. Our result unravels the cause underpinning such a blow-up phenomenon, differentiating the chromatic and homomorphism threshold problems for cliques. It implies that for the homomorphism threshold problem, rather than the minimum degree condition usually considered in the literature, the decisive factor is a clique density condition on co-neighborhoods of vertices. More precisely, we show that if an $n$-vertex $K_{r}$-free graph $G$ satisfies that the common neighborhood of every pair of non-adjacent vertices induces a subgraph with $K_{r-2}$-density at least $\varepsilon>0$, then $G$ must be a blow-up of some $K_r$-free graph $F$ on at most $2^{O(\frac{r}{\varepsilon}\log\frac{1}{\varepsilon})}$ vertices. Furthermore, this single exponential bound is optimal. We construct examples with no $K_r$-free homomorphic image of size smaller than $2^{\Omega_r(\frac{1}{\varepsilon})}$., Comment: 24 pages, the extended abstract is accepted in SoCG 2024

Motivated by an extremal problem on graph-codes that links coding theory and graph theory, Alon recently proposed a question aiming to find the smallest number $t$ such that there is an edge coloring of $K_{n}$ by $t$ colors with no copy of given graph $H$ in which every color appears an even number of times. When $H=K_{4}$, the question of whether $n^{o(1)}$ colors are enough, was initially emphasized by Alon. Through modifications to the coloring functions originally designed by Mubayi, and Conlon, Fox, Lee and Sudakov, the question of $K_{4}$ has already been addressed. Expanding on this line of inquiry, we further study this new variant of the generalized Ramsey problem and provide a conclusively affirmative answer to Alon's question concerning $K_{5}$., Comment: Note added: Heath and Zerbib also proved the result on $K_{5}$ independently. arXiv:2307.01314

The Euclidean Gallai-Ramsey problem, which investigates the existence of monochromatic or rainbow configurations in a colored $n$-dimensional Euclidean space $\mathbb{E}^{n}$, was introduced and studied recently. We further explore this problem for various configurations including triangles, squares, lines, and the structures with specific properties, such as rectangular and spherical configurations. Several of our new results provide refinements to the results presented in a recent work by Mao, Ozeki and Wang. One intriguing phenomenon evident on the Gallai-Ramsey results proven in this paper is that the dimensions of spaces are often independent of the number of colors. Our proofs primarily adopt a geometric perspective.

We study the Tur\'{a}n problem for highly symmetric bipartite graphs arising from geometric shapes and periodic tilings commonly found in nature. 1. The prism $C_{2\ell}^{\square}:=C_{2\ell}\square K_{2}$ is the graph consisting of two vertex disjoint $2\ell$-cycles and a matching pairing the corresponding vertices of these two cycles. We show that for every $\ell\ge 4$, ex$(n,C_{2\ell}^{\square})=\Theta(n^{3/2})$. This resolves a conjecture of He, Li and Feng. 2. The hexagonal tiling in honeycomb is one of the most natural structures in the real world. We show that the extremal number of honeycomb graphs has the same order of magnitude as their basic building unit 6-cycles. 3. We also consider bipartite graphs from quadrangulations of the cylinder and the torus. We prove near optimal bounds for both configurations. In particular, our method gives a very short proof of a tight upper bound for the extremal number of the 2-dimensional grid, improving a recent result of Brada\v{c}, Janzer, Sudakov and Tomon. Our proofs mix several ideas, including shifting embedding schemes, weighted homomorphism and subgraph counts and asymmetric dependent random choice., Comment: Following the suggestions of the journal reviewers, we have moved the shorter proof in the previous Appendix into the main body of this paper. Additionally, we have added more content in Concluding remarks

A finite family $\mathcal{F}$ of $d$-dimensional convex polytopes is called $k$-neighborly if $d-k\le\textup{dim}(C\cap C')\le d-1$ for any two distinct members $C,C'\in\mathcal{F}$. In 1997, Alon initiated the study of the general function $n(k,d)$, which is defined to be the maximum size of $k$-neighborly families of standard boxes in $\mathbb{R}^{d}$. Based on a weighted count of vectors in $\{0,1\}^{d}$, we improve a recent upper bound on $n(k,d)$ by Alon, Grytczuk, Kisielewicz, and Przes\l awski for any positive integers $d$ and $k$ with $d\ge k+2$. In particular, when $d$ is sufficiently large and $k\ge 0.123d$, our upper bound on $n(k,d)$ improves the bound $\sum_{i=1}^{k}2^{i-1}\binom{d}{i}+1$ shown by Huang and Sudakov exponentially. Furthermore, we determine that $n(2,4)=9$, $n(3,5)=18$, $n(3,6)=27$, $n(4,6)=37$, $n(5,7)=74$, and $n(6,8)=150$. The stability result of Kleitman's isodiametric inequality plays an important role in the proofs., Comment: Final version, accepted by European Journal of Combinatorics

We study families $\mathcal{F}\subseteq 2^{[n]}$ with restricted intersections and prove a conjecture of Snevily in a stronger form for large $n$. We also obtain stability results for Kleitman's isodiametric inequality and families with bounded set-wise differences. Our proofs introduce a new twist to the classical linear algebra method, harnessing the non-shadows of $\mathcal{F}$, which may be of independent interest.

Let $\mathcal{F}$ be a family of subsets of $[n]$ and $L$ be a subset of $[n]$. We say $\mathcal{F}$ is an $L$-differencing Sperner system if $|A\setminus B|\in L$ for any distinct $A,B\in\mathcal{F}$. Let $p$ be a prime and $q$ be a power of $p$. Frankl first studied $p$-modular $L$-differencing Sperner systems and showed an upper bound of the form $\sum_{i=0}^{|L|}\binom{n}{i}$. In this paper, we obtain new upper bounds on $q$-modular $L$-differencing Sperner systems using elementary $p$-adic analysis and polynomial method, extending and improving existing results substantially. Moreover, our techniques can be used to derive new upper bounds on subsets of the hypercube with restricted Hamming distances. One highlight of the paper is the first analogue of the celebrated Snevily's theorem in the $q$-modular setting, which results in several new upper bounds on $q$-modular $L$-avoiding $L$-intersecting systems. In particular, we improve a result of Felszeghy, Heged\H{u}s, and R\'{o}nyai, and give a partial answer to a question posed by Babai, Frankl, Kutin, and \v{S}tefankovi\v{c}., Comment: 22 pages, results in table 1 and section 6.1 improved

Several network communication problems are highly related such as coded caching and distributed computation. The centralized coded caching focuses on reducing the network burden in peak times in a wireless network system and the coded distributed computation studies the tradeoff between computation and communication in distributed system. In this paper, motivated by the study of the only rainbow $3$-term arithmetic progressions set, we propose a unified framework for constructing coded caching schemes. This framework builds bridges between coded caching schemes and lots of combinatorial objects due to the freedom of the choices of families and operations. We prove that any scheme based on a placement delivery array (PDA) can be represented by a rainbow scheme under this framework and lots of other known schemes can also be included in this framework. Moreover, we also present a new coded caching scheme with linear subpacketization and near constant rate using the only rainbow $3$-term arithmetic progressions set. Next, we modify the framework to be applicable to the distributed computing problem. We present a new transmission scheme in the shuffle phase and show that in certain cases it could have a lower communication load than the schemes based on PDAs or resolvable designs with the same number of files., Comment: 13 pages

Motivated by a problem in theoretical computer science suggested by Wigderson, Alon and Ben-Eliezer studied the following extremal problem systematically one decade ago. Given a graph $H$, let $C(n,H)$ be the minimum number $k$ such that the following holds. There are $n$ colorings of $E(K_{n})$ with $k$ colors, each associated with one of the vertices of $K_{n}$, such that for every copy $T$ of $H$ in $K_{n}$, at least one of the colorings that are associated with $V(T)$ assigns distinct colors to all the edges of $E(T)$. In this paper, we obtain several new results in this problem including: \begin{itemize} \item For paths of short length, we show that $C(n,P_{4})=\Omega(n^{1/5})$ and $C(n,P_{t})=\Omega(n^{1/3})$ with $t\in\{5,6\}$, which significantly improve the previously known lower bounds $(\log{n})^{\Omega(1)}$. \item We make progress on the problem of Alon and Ben-Eliezer about complete graphs, more precisely, we show that $C(n,K_{r})=\Omega(n^{2/3})$ when $r\geqslant 8$. This provides the first instance of graph for which the lower bound goes beyond the natural barrier $\Omega(n^{1/2})$. Moreover, we prove that $C(n,K_{s,t})=\Omega(n^{2/3})$ for $t\geqslant s\geqslant 7$. \item When $H$ is a star with at least $4$ leaves, a matching of size at least $4$, or a path of length at least $7$, we give the new lower bound for $C(n,H)$. We also show that for any graph $H$ with at least $6$ edges, $C(n,H)$ is polynomial in $n$. All of these improve the corresponding results obtained by Alon and Ben-Eliezer., Comment: 13 pages

Given a finite abelian group $G$ and a subset $J\subset G$ with $0\in J$, let $D_{G}(J,N)$ be the maximum size of $A\subset G^{N}$ such that the difference set $A-A$ and $J^{N}$ have no non-trivial intersection. Recently, this extremal problem has been widely studied for different groups $G$ and subsets $J$. In this paper, we generalize and improve the relevant results by Alon and by Heged\H{u}s by building a bridge between this problem and cyclotomic polynomials with the help of algebraic graph theory. In particular, we construct infinitely many non-trivial families of $G$ and $J$ for which the current known upper bounds on $D_{G}(J, N)$ can be improved exponentially. We also obtain a new upper bound $D_{\mathbb{F}_{p}}(\{0,1\},N)\le (\frac{1}{2}+o(1))(p-1)^{N}$, which improves the previously best-known result by Huang, Klurman, and Pohoata., Comment: 18 pages

Virtual Reality (VR) technology has been shown to achieve remarkable results in multiple fields. Due to the nature of the immersive medium of Virtual Reality it logically follows that it can be used as a high-quality educational tool as it offers potentially a higher bandwidth than other mediums such as text, pictures and videos. This short paper illustrates the development of a climate change educational awareness application for virtual reality to simulate virtual scenes of local scenery and sea level rising until 2100 using prediction data. The paper also reports on the current in progress work of porting the system to Augmented Reality (AR) and future work to evaluate the system., Comment: Published in 8th International Conference of the Immersive Learning Research Network (iLRN 2022)

Recently, deep convolution neural networks (CNNs) steered face super-resolution methods have achieved great progress in restoring degraded facial details by jointly training with facial priors. However, these methods have some obvious limitations. On the one hand, multi-task joint learning requires additional marking on the dataset, and the introduced prior network will significantly increase the computational cost of the model. On the other hand, the limited receptive field of CNN will reduce the fidelity and naturalness of the reconstructed facial images, resulting in suboptimal reconstructed images. In this work, we propose an efficient CNN-Transformer Cooperation Network (CTCNet) for face super-resolution tasks, which uses the multi-scale connected encoder-decoder architecture as the backbone. Specifically, we first devise a novel Local-Global Feature Cooperation Module (LGCM), which is composed of a Facial Structure Attention Unit (FSAU) and a Transformer block, to promote the consistency of local facial detail and global facial structure restoration simultaneously. Then, we design an efficient Feature Refinement Module (FRM) to enhance the encoded features. Finally, to further improve the restoration of fine facial details, we present a Multi-scale Feature Fusion Unit (MFFU) to adaptively fuse the features from different stages in the encoder procedure. Extensive evaluations on various datasets have assessed that the proposed CTCNet can outperform other state-of-the-art methods significantly. Source code will be available at https://github.com/IVIPLab/CTCNet., Comment: IEEE Transactions on Image Processing, 12 figures, 9 tables

Let $R_k(H;K_m)$ be the smallest number $N$ such that every coloring of the edges of $K_{N}$ with $k+1$ colors has either a monochromatic $H$ in color $i$ for some $1\leqslant i\leqslant k$, or a monochromatic $K_{m}$ in color $k+1$. In this short note, we study the lower bound for $R_k(H;K_m)$ when $H$ is $C_5$ or $C_7$, respectively. We show that \begin{equation*} R_{k}(C_5;K_m)=\Omega(m^{\frac{3k}{8}+1}/(\log{m})^{\frac{3k}{8}+1}), \end{equation*} and \begin{equation*} R_{k}(C_7;K_m)=\Omega(m^{\frac{2k}{9}+1}/(\log{m})^{\frac{2k}{9}+1}), \end{equation*} for fixed positive integer $k$ and $m\rightarrow\infty$. These slightly improve the previously known lower bound $R_{k}(C_{2\ell+1};K_m)=\Omega(m^{\frac{k}{2\ell-1}+1}/(\log m)^{k+\frac{2k}{2\ell-1}})$ obtained by Alon and R\"{o}dl. The proof is based on random block constructions and random blowups argument.

Given a graph $H$ and an integer $k\geqslant 2$, let $f_{k}(n,H)$ be the smallest number of colors $C$ such that there exists a proper edge-coloring of the complete graph $K_{n}$ with $C$ colors containing no $k$ vertex-disjoint color isomorphic copies of $H$. In this paper, we prove that $f_{2}(n,H_{t})=\Omega(n^{1+\frac{1}{2t-3}})$ where $H_{t}$ is the $1$-subdivision of the complete graph $K_{t}$. This answers a question of Conlon and Tyomkyn (arXiv: 2002.00921)., Comment: 9 pages

In this paper, we first study a new extremal problem recently posed by Conlon and Tyomkyn~(arXiv: 2002.00921). Given a graph $H$ and an integer $k\geqslant 2$, let $f_{k}(n,H)$ be the smallest number of colors $c$ such that there exists a proper edge-coloring of the complete graph $K_{n}$ with $c$ colors containing no $k$ vertex-disjoint color-isomorphic copies of $H$. Using algebraic properties of polynomials over finite fields, we give an explicit proper edge-coloring of $K_{n}$ and show that $f_{k}(n, C_{4})=\Theta(n)$ when $k\geqslant 3$ and $n\rightarrow\infty$. The methods we used in the edge-coloring may be of some independent interest. We also consider a related generalized Ramsey problem. For given graphs $G$ and $H,$ let $r(G,H,q)$ be the minimum number of edge-colors (not necessarily proper) of $G$, such that the edges of every copy of $H\subseteq G$ together receive at least $q$ distinct colors. Establishing the relation to the Tur\'{a}n number of specified bipartite graphs, we obtain some general lower bounds for $r(K_{n,n},K_{s,t},q)$ with a broad range of $q$., Comment: 13 pages, accepted by SIAM Journal on Discrete Mathematics

For a graph $H$, the 1-subdivision of $H$, denoted by $H'$, is the graph obtained by replacing the edges of $H$ by internally disjoint paths of length 2. Recently, Conlon, Janzer and Lee (arXiv: 1903.10631) asked the following question: For any integer $s\ge2$, estimate the smallest $t$ such that $\textup{ex}(n,K_{s,t}')=\Omega(n^{\frac{3}{2}-\frac{1}{2s}})$. In this paper, we consider the case $s=3$. More precisely, we provide an explicit construction giving \begin{align*} \text{ex}(n,K_{3,30}')=\Omega(n^{\frac{4}{3}}), \end{align*} which reduces the estimation for the smallest value of $t$ from a magnitude of $10^{56}$ to the number $30$. The construction is algebraic, which is based on some equations over finite fields., Comment: 15 pages

Recently, Berge theta hypergraphs have received special attention due to the similarity with Berge even cycles. Let $r$-uniform Berge theta hypergraph $\Theta_{\ell,t}^{B}$ be the $r$-uniform hypergraph consisting of $t$ internally disjoint Berge paths of length $\ell$ with the same pair of endpoints. In this work, we determine the Tur\'{a}n number of $3$-uniform Berge theta hypergraph when $\ell=3$ and $t$ is relatively small. More precisely, we provide an explicit construction giving \begin{align*} \textup{ex}_{3}(n,\Theta_{3,217}^{B})=\Omega(n^{\frac{4}{3}}). \end{align*} This matches an earlier upper bound by He and Tait up to an absolute constant factor. The construction is algebraic, which is based on some equations over finite fields, and the parameter $t$ in our construction is much smaller than that in random algebraic construction. Our main technique is using the resultant of polynomials, which appears to be a powerful technique to eliminate variables., Comment: 19 pages

Recently, several hypergraph Tur\'{a}n problems were solved by the powerful random algebraic method. However, the random algebraic method usually requires some parameters to be very large, hence we are concerned about how these Tur\'{a}n numbers depend on such large parameters of the forbidden hypergraphs. In this paper, we determine the dependence on such specified large constant for several hypergraph Tur\'{a}n problems. More specifically, for complete $r$-partite $r$-uniform hypergraphs, we show that if $s_{r}$ is sufficiently larger than $s_{1},s_{2},\ldots,s_{r-1},$ then $$\textup{ex}_{r}(n,K_{s_{1},s_{2},\ldots,s_{r}}^{(r)})=\Theta(s_{r}^{\frac{1}{s_{1}s_{2}\cdots s_{r-1}}}n^{r-\frac{1}{s_{1}s_{2}\cdots s_{r-1}}}).$$ For complete bipartite $r$-uniform hypergraphs, we prove that if $s$ is sufficiently larger than $t,$ we have $$\textup{ex}_{r}(n,K_{s,t}^{(r)})=\Theta(s^{\frac{1}{t}}n^{r-\frac{1}{t}}).$$ In particular, our results imply that the famous K\H{o}v\'{a}ri--S\'{o}s--Tur\'{a}n's upper bound $\textup{ex}(n,K_{s,t})=O(t^{\frac{1}{s}}n^{2-\frac{1}{s}})$ has the correct dependence on large $t$. The main approach is to construct random multi-hypergraph via a variant of random algebraic method., Comment: Accepted to European Journal of Combinatorics

For two $r$-graphs $\mathcal{T}$ and $\mathcal{H}$, let $\text{ex}_{r}(n,\mathcal{T},\mathcal{H})$ be the maximum number of copies of $\mathcal{T}$ in an $n$-vertex $\mathcal{H}$-free $r$-graph. The determination of Tur\'{a}n number $\text{ex}_{r}(n,\mathcal{T},\mathcal{H})$ has become the fundamental core problem in extremal graph theory ever since the pioneering work Tur\'{a}n's Theorem was published in $1941$. Although we have some rich results for the simple graph case, only sporadic results have been known for the hypergraph Tur\'{a}n problems. In this paper, we mainly focus on the function $\text{ex}_{r}(n,\mathcal{T},\mathcal{H})$ when $\mathcal{H}$ is one of two different hypergraph extensions of the complete bipartite graph $K_{s,t}$. The first extension is the complete bipartite $r$-graph $K_{s,t}^{(r)}$, which was introduced by Mubayi and Verstra\"{e}te~[J. Combin. Theory Ser. A, 106: 237--253, 2004]. Using the powerful random algebraic method, we show that if $s$ is sufficiently larger than $t$, then \[\text{ex}_{r}(n,\mathcal{T},K_{s,t}^{(r)})=\Omega(n^{v-\frac{e}{t}}),\] where $\mathcal{T}$ is an $r$-graph with $v$ vertices and $e$ edges. In particular, when $\mathcal{T}$ is an edge or some specified complete bipartite $r$-graph, we can determine their asymptotics. The second important extension is the complete $r$-partite $r$-graph $K_{s_{1},s_{2},\ldots,s_{r}}^{(r)}$, which has been widely studied. When $r=3$, we provide an explicit construction giving \[\text{ex}_{3}(n,K_{2,2,7}^{(3)})\geqslant\frac{1}{27}n^{\frac{19}{7}}+o(n^{\frac{19}{7}}).\] Our construction is based on the Norm graph, and improves the lower bound $\Omega(n^{\frac{73}{27}})$ obtained by probabilistic method., Comment: To appear in SCIENCE CHINA Mathematics

Recently, Bennett et al. introduced the vertex-induced weighted Tur\'an problem. In this paper, we consider their open Tur\'an problem under sum-edge-weight function and characterize the extremal structure of $K_{l}$-free graphs. Based on these results, we propose a generalized version of the Erd\H{o}s-Stone theorem for weighted graphs under two types of vertex-induced weight functions.

Permutation codes under different metrics have been extensively studied due to their potentials in various applications. Generalized Cayley metric is introduced to correct generalized transposition errors, including previously studied metrics such as Kendall's $\tau$-metric, Ulam metric and Cayley metric as special cases. Since the generalized Cayley distance between two permutations is not easily computable, Yang et al. introduced a related metric of the same order, named the block permutation metric. Given positive integers $n$ and $d$, let $\mathcal{C}_{B}(n,d)$ denote the maximum size of a permutation code in $S_n$ with minimum block permutation distance $d$. In this paper, we focus on the theoretical bounds of $\mathcal{C}_{B}(n,d)$ and the constructions of permutation codes under block permutation metric. Using a graph theoretic approach, we improve the Gilbert-Varshamov type bound by a factor of $\Omega(\log{n})$, when $d$ is fixed and $n$ goes into infinity. We also propose a new encoding scheme based on binary constant weight codes. Moreover, an upper bound beating the sphere-packing type bound is given when $d$ is relatively close to $n$.