Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userExact bipartite Turan numbers of large even cycles
111
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let the bipartite Turan number $ex(m,n,H)$ of a graph $H$ be the maximum number of edges in an $H$-free bipartite graph with two parts of sizes $m$ and $n$, respectively. In this paper, we prove that $ex(m,n,C_{2t})=(t-1)n+m-t+1$ for any positive integers $m,n,t$ with $ngeq mgeq tgeq frac{m}{2}+1$. This confirms the rest of a conjecture of Gy{o}ri cite{G97} (in a stronger form), and improves the upper bound of $ex(m,n,C_{2t})$ obtained by Jiang and Ma cite{JM18} for this range. We also prove a tight edge condition for consecutive even cycles in bipartite graphs, which settles a conjecture in cite{A09}. As a main tool, for a longest cycle $C$ in a bipartite graph, we obtain an estimate on the upper bound of the number of edges which are incident to at most one vertex in $C$. Our two results generalize or sharpen a classical theorem due to Jackson cite{J85} in different ways.
rate research
Read More
Let $mathrm{rex}(n, F)$ denote the maximum number of edges in an $n$-vertex graph that is regular and does not contain $F$ as a subgraph. We give lower bounds on $mathrm{rex}(n, F)$, that are best possible up to a constant factor, when $F$ is one of $C_4$, $K_{2,t}$, $K_{3,3}$ or $K_{s,t}$ when $t>s!$.
We prove new upper bounds on the multicolour Ramsey numbers of paths and even cycles. It is well known that $(k-1)n+o(n)leq R_k(P_n)leq R_k(C_n)leq kn+o(n)$. The upper bound was recently improved by Sarkozy who showed that $R_k(C_n)leqleft(k-frac{k}{16k^3+1}right)n+o(n)$. Here we show $R_k(C_n) leq (k-frac14)n +o(n)$, obtaining the first improvement to the coefficient of the linear term by an absolute constant.
We call a $4$-cycle in $K_{n_{1}, n_{2}, n_{3}}$ multipartite, denoted by $C_{4}^{text{multi}}$, if it contains at least one vertex in each part of $K_{n_{1}, n_{2}, n_{3}}$. The Turan number $text{ex}(K_{n_{1},n_{2},n_{3}}, C_{4}^{text{multi}})$ $bigg($ respectively, $text{ex}(K_{n_{1},n_{2},n_{3}},{C_{3}, C_{4}^{text{multi}}})$ $bigg)$ is the maximum number of edges in a graph $Gsubseteq K_{n_{1},n_{2},n_{3}}$ such that $G$ contains no $C_{4}^{text{multi}}$ $bigg($ respectively, $G$ contains neither $C_{3}$ nor $C_{4}^{text{multi}}$ $bigg)$. We call a $C^{multi}_4$ rainbow if all four edges of it have different colors. The ant-Ramsey number $text{ar}(K_{n_{1},n_{2},n_{3}}, C_{4}^{text{multi}})$ is the maximum number of colors in an edge-colored of $K_{n_{1},n_{2},n_{3}}$ with no rainbow $C_{4}^{text{multi}}$. In this paper, we determine that $text{ex}(K_{n_{1},n_{2},n_{3}}, C_{4}^{text{multi}})=n_{1}n_{2}+2n_{3}$ and $text{ar}(K_{n_{1},n_{2},n_{3}}, C_{4}^{text{multi}})=text{ex}(K_{n_{1},n_{2},n_{3}}, {C_{3}, C_{4}^{text{multi}}})+1=n_{1}n_{2}+n_{3}+1,$ where $n_{1}ge n_{2}ge n_{3}ge 1.$
For given graphs $G$ and $F$, the Turan number $ex(G,F)$ is defined to be the maximum number of edges in an $F$-free subgraph of $G$. Foucaud, Krivelevich and Perarnau and later independently Briggs and Cox introduced a dual version of this problem wherein for a given number $k$, one maximizes the number of edges in a host graph $G$ for which $ex(G,H) < k$. Addressing a problem of Briggs and Cox, we determine the asymptotic value of the inverse Turan number of the paths of length $4$ and $5$ and provide an improved lower bound for all paths of even length. Moreover, we obtain bounds on the inverse Turan number of even cycles giving improved bounds on the leading coefficient in the case of $C_4$. Finally, we give multiple conjectures concerning the asymptotic value of the inverse Turan number of $C_4$ and $P_{ell}$, suggesting that in the latter problem the asymptotic behavior depends heavily on the parity of $ell$.
Recently, Lazar and Wachs (arXiv:1910.07651) showed that the (median) Genocchi numbers play a fundamental role in the study of the homogenized Linial arrangement and obtained two new permutation models (called D-permutations and E-permutations) for (median) Genocchi numbers. They further conjecture that the distributions of cycle numbers over the two models are equal. In a follow-up, Eu et al. (arXiv:2103.09130) further proved the gamma-positivity of the descent polynomials of even-odd descent permutations, which are in bijection with E-permutations by Foatas fundamental transformation. This paper merges the above two papers by considering a general moment sequence which encompasses the number of cycles and number of drops of E-permutations. Using the combinatorial theory of continued fraction, the moment connection enables us to confirm Lazar-Wachs conjecture and obtain a natural $(p,q)$-analogue of Eu et als descent polynomials. Furthermore, we show that the $gamma$-coefficients of our $(p,q)$-analogue of descent polynomials have the same factorization flavor as the $gamma$-coeffcients of Brandens $(p,q)$-Eulerian polynomials.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
