For $k\ge2$, a graph is $C_{2k}$-connected if every two distinct edges lie together on an even cycle of length at most $2k$ in that graph. Let $f_k(n,m)$ be the largest number of edges in a $C_{2k}$-connected subgraph that every $n$-vertex graph with $m$ edges must contain. In this paper, we study two cycle-connected p...
An $r$-uniform hypergraph is linear if any two edges share at most one vertex. For a family $\mathcal F$ of $r$-graphs, let $\text{ex}^{\text{lin}}_r(n,\mathcal F)$ and $\text{spex}^{\text{lin}}_r(n,\mathcal F)$ denote, respectively, the maximum number of edges and the maximum spectral radius of an $n$-vertex $\mathcal...
We prove a sparse version of the four-colour theorem of Brandt and Thomass\'{e}, answering a question of Allen, B\"ottcher, Kohayakawa and Roberts. For every fixed $0<\gamma\le1/10$ and every $p=p(n)\in(0,1]$, asymptotically almost surely every spanning triangle-free $H\subseteq G(n,p)$ with $\delta(H)\ge(1/3+\gamma)pn...
Let $X$ be an alphabet, let $t\geq 0$ and $n\geq t+1$, and let $((a_i,b_i))_{i=1}^{m}$ be an ordered family of word pairs in $X^n$ satisfying $dist(a_i,b_i)\geq t+1$ for every $i$ and $dist(a_i,b_j)\leq t$ whenever $i<j$. We prove the sharp bound $m\leq 2^{t+1}$, thereby resolving a problem posed by Alon, Jin, and Suda...
Guo-Rong Gao, Run-Han Zhao· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.