Disjoint edges in geometric graphs
A geometric graph is a graph drawn in the plane so that its vertices and edges are represented by points in general position and straight line segments, respectively. A vertex of a geometric graph is called pointed if it lies outside of the convex hull of its neighbours. We show that for a geometric graph with $n$ vertices and $e$ edges there are at least $\frac{n}{2}\binom{2e/n}{3}$ pairs of disjoint edges provided that $2e\geq n$ and all the vertices of the graph are pointed. Besides, we prove that if any edge of a geometric graph with $n$ vertices is disjoint from at most $ m $ edges, then the number of edges of this graph does not exceed $n(\sqrt{1+8m}+3)/4$ provided that $n$ is sufficiently large.These two results are tight for an infinite family of graphs.
\section{Introduction}

A \textit{geometric graph} \(G\) is a graph drawn in the plane by (possibly crossing) straight line segments, that is, its vertex set \(V(G)\) is a set of points in general position in the plane and its edge set \(E(G)\) is the set of straight line segments with endpoints belonging to \(V(G)\). One of the classical problems on geometric graphs is a question raised by Avital and Hanani~\cite{avital1966graphs}, Kupitz~\cite{Kupitz79}, Erd\H os and Perles. For positive integers \(k\) and \(n\), determine the smallest \(e_k(n)\) such that any geometric graph with \(n\) vertices and \(m>e_k(n)\) edges contains \(k+1\) pairwise disjoint edges.

By results of Hopf and Pannwitz~\cite{hopf1934} and Erd\H os~\cite{Erdos46}, we know that \(e_1(n)=n\). The upper bound for \(e_2(n)\) was studied in papers of Alon and Erd\H os~\cite{AlonErdos89}, Goddard, Katchalski, and Kleitman~\cite{GoddardKatchalskiKleitman96}, M\'esz\'aros~\cite{meszaros98}. The current best upper bound, \(e_2(n)\leq \lceil 5n/2\rceil\), was proved by \v{C}ern\'{y}~\cite{Cerny05}. This bound is tight up to additive constant: Perles found an example showing that \(e_2(n)\geq \lfloor 5n/2 \rfloor -3\). Also, in~\cite{GoddardKatchalskiKleitman96} it was shown that \({7n/2-6\leq e_3(n)\leq 10n}\). For \(k\leq n/2\), Kupitz~\cite{Kupitz79} proved the lower bound \(e_k(n)\geq kn\), and later T\'oth and Valtr~\cite{TothValtr99} improved it: \({e_k(n)\geq 3(k-1)n/2-2k^2}\). 
Using Dilworth's theorem, Pach and  T\"or\H{o}csik~\cite{PachTorocsik94} found a beautiful proof of the upper bound~\(e_k(n)\leq k^4 n\). Later, this bound was refined in~\cite{TothValtr99}, and the current best upper bound, \(e_k(n)\leq 256k^2n\), belongs to T\'oth~\cite{Toth00}; see also~Theorem~1.11 in~\cite{felsner2012geometric}. Another interesting result about disjoint edges of a \textit{convex graph} is due to Kupitz~\cite{kupitz1984pairs}. Recall that \textit{a convex graph} is a geometric graph whose vertices are in convex position. He proved that a convex graph on \(n\) vertices has no \(k+1\) pairwise disjoint edge, then its number of edges does not exceed \(kn\) provided \(n\geq 2k+1\). For further reading, we refer the interested readers to the survey of Pach~\cite{pach2013beginnings} on geometric and topological graphs.

In the current paper, we study two questions about the local and global number of pairs of disjoint edges. For a geometric graph \( G \), let \(DJ(G)\) be the set of pairs of disjoint edges of geometric graphs. For an edge \(uv\in E(G)\), let \(DJ(uv)\) be the set of edges in \(G\) disjoint from \(uv\). Clearly, we have the equality
\[
|DJ(G)| = \frac12 \sum_{uv\in E(G)} |DJ(uv)|.
\]

These are the main problems of the paper.
\begin{problem}
    For integers \(n>0\) and \(m\geq0\), determine the greatest number \(e(n,m)\) such that a geometric graph \(G\) on \(n\) vertices has at most \(e(n,m)\) edges provided that \(|DJ(uv)|\leq m\) for any \(uv\in E(G)\).
\end{problem}

\begin{problem}
    For positive integers \(n\) and \(e\), determine the smallest number \(dj(n,e)\) such that for any geometric graph \(G \) with \(n\) vertices and \(e\) edges, we have \(|DJ(G)|\geq dj(n,e)\).
\end{problem}

In the current paper, we solve these problems for \textit{locally convex graphs}. To define these graphs, recall that the \textit{neighborhood} \(N(v)\) of a vertex \(v\in V(G)\) is the set of vertices adjacent to \( v \). A vertex is called \textit{convex} if it lies outside of the convex hull of its neighborhood. A locally convex graph is a geometric graph such that any of its vertices is convex. Clearly, any convex graph is locally convex as well.

The goal of this paper is to prove the following two theorems.
\begin{theorem}\label{theorem:main1}
Let \(m\) be a non-negative integer and \(G\) be a geometric graph such that \( |DJ(uv)|\leq m\) for any edge \( uv\in E(G) \). Then
\[
|E(G)|\leq \max\left(|V(G)|\left(\sqrt{1+8m}+3\right)/4, |V(G)| + 3m-1\right).
\] 

\end{theorem}

\begin{theorem}\label{theorem:main2}
For a locally convex graph \( G \) with \( 2|E(G)|\geq |V(G)| \), we have
\[
|DJ(G)| \geq \frac{|V(G)|}{2} \cdot \binom{d(G)}{3},
\]
where \(d(G)=2|E(G)|/|V(G)|\) is the average degree of \(G\).
\end{theorem}

Note that Theorem~\ref{theorem:main1} is a strengthening of a result mentioned above.
\begin{theorem}[Hopf and Pannwitz~\cite{hopf1934}, Erd\H{o}s~\cite{Erdos46}]\label{erdos}
If every edge of a geometric graph \( G \) intersects all other edges of \(G\), then
\(|E(G)|\leq |V(G)|\).
\end{theorem}

The rest of the paper is organized as follows. In Section~\ref{section:preliminaries}, we prove auxiliary lemmas. In Sections~\ref{section:proof1} and~\ref{section:proof2}, we prove Theorems~\ref{theorem:main1} and~\ref{theorem:main2}, respectively. In Section~\ref{section:discussion}, we show that these theorems are tight for an infinite family of graphs. Also, in this section, we discuss open problems related to strengthenings of our main results.


\section{Preliminaries}
\label{section:preliminaries}

Throughout the next three sections, we denote by \( n \) and \(e\) the number of vertices and edges of a geometric graph \(G\), respectively, that is, \(n=|V(G)|\) and \(e=|E(G)|\). In this section, we assume that \( G \) is a locally convex graph such that every vertex has degree at least two.

For distinct points \(x,y,z\in \mathbb R^2\) in general position, by the \textit{oriented angle} \( \angle xyz \) we mean the angle in \( (-\pi, \pi) \) starting at the ray \(yx\) and ending at the ray \(yz\), measured counterclockwise. By this definition, we have that \( \angle xyz=-\angle zyx\). For a vertex \( v\in V(G)\), choose \( x,y\in N(v)\) such that
\begin{equation}
    \label{equation:max_angle}
\angle xvy =\max\left\{\angle avb: a,b \in N(v)\right\}.
\end{equation}
Set \( r_v: = x \) and \( \ell_v:=y \). The edges \( v\ell_v \) and \( vr_v \) are called the \textit{leftmost edge} and the \textit{rightmost edge} of \( v \), respectively. For \( v \in V(G) \), let \( DJ_\ell(v) \) be the set of edges incident to one of the vertices of \( N(v) \) and disjoint from the leftmost edge \( v\ell_v \). Analogously, we denote by \(DJ_r(v) \) the set of edges incident to one of the vertices of \( N(v) \) and disjoint from the rightmost edge \( vr_v \).  Clearly, \( DJ_\ell(v)\subseteq DJ(v\ell_v)\), \(DJ_r(v)\subseteq DJ(vr_v) \), and thus, we have \(|DJ(v\ell_v)| \geq |DJ_\ell(v)|\) and \( |DJ(vr_v)| \geq |DJ_r(v)|\).  

For a vertex \(v\in V(G)\), denote by \(\mathcal L(v)\) the set of edges \(\ell_vx\in E(G)\) such that the angle \(\angle x\ell_v v\) is positive. Analogously, denote by \(\mathcal R(v)\) the set of edges \(r_vv\in E(G)\) such that the angle \(\angle xr_vv\) is negative. Remark that if \(\ell_v x\in \mathcal L(v)\) or \(r_vx\in \mathcal R(v)\), then \(x\not\in N(v)\).

\begin{lemma}
\label{lemma:simple?}
For any vertex \( v\in V(G) \), we have
\begin{equation}
\label{equation: first lemma}
    | DJ_\ell (v) | + | DJ_r (v) | \geq \sum_{w\in N(v)\setminus\{\ell_v, r_v\}} (\deg w -1) + |\mathcal L(v)| + |\mathcal R(v)|,
\end{equation}
where \( \deg w \) is the degree of vertex \(w\in V(G)\).
\end{lemma}
\begin{proof}
To prove this lemma, we apply the so-called discharging method. Let us assign a charge to every edge \(wt\in E(G)\) as follows:
\begin{itemize}
    \item[1.] If the vertex \(v\) is incident to \(wt\), then the charge of \(wt\) is 0.
    \item[2.] If \(wt\in \mathcal L(v)\cup \mathcal R(v)\), then the charge of \(wt\) is 1.
    \item[3.] If \(wt\not\in \mathcal L(v)\cup \mathcal R(v)\) and \(v\) is not incident to \(wt\), then the charge of \(wt\) is \(|\{w,t\}\cap N(v)\setminus\{\ell_v,r_v\}|\).
\end{itemize}

\begin{figure}[H]
\label{figure1}
\centering

\begin{subfigure}[t]{0.3\textwidth}
\centering

\begin{tikzpicture}[line cap=round,line width = 1pt]
\draw (0,0) node [below] {\( v \)} -- (-2,2) node [left] {\( \ell_v \)};
\draw (0,0) -- (2,2) node [right] {\( r_v \)};
\draw (0,0) -- (0,3) node [above] {\( w \)};
\draw (0,3) -- (2,1) node [below] {\( t \)};

\filldraw (0,0) circle (2pt);
\filldraw (2,2) circle (2pt);
\filldraw (-2,2) circle (2pt);
\filldraw (0,3) circle (2pt);
\filldraw (2,1) circle (2pt);
\end{tikzpicture}
\caption{}
\label{figure1:a}
\end{subfigure}
\hfill
\begin{subfigure}[t]{0.3\textwidth}
\centering

\begin{tikzpicture}[line cap=round,line width = 1pt
\draw (0,0) node [below] {\( v \)} -- (-2,2) node [left] {\( \ell_v \)};
\draw (0,0) -- (2,2) node [right] {\( r_v \)};
\draw (0,0) -- (0,3) node [above] {\( w \)};
\draw (0,3) -- (2,2);

\filldraw (0,0) circle (2pt);
\filldraw (2,2) circle (2pt);
\filldraw (-2,2) circle (2pt);
\filldraw (0,3) circle (2pt);

\end{tikzpicture}
\caption{}
\label{figure1:b}
\end{subfigure}
\hfill
\begin{subfigure}[t]{0.3\textwidth}
\centering

\begin{tikzpicture}[line cap=round,line width = 1pt]
\draw (0,0) node [below] {\( v \)} -- (-2,2) node [left] {\( \ell_v \)};
\draw (0,0) -- (2,2) node [right] {\( r_v \)};
\draw (0,0) -- (-1,3) node [above] {\( w \)};
\draw (0,0) -- (1,3) node [above] {\( t \)};
\draw (1,3) -- (-1,3);

\filldraw (0,0) circle (2pt);
\filldraw (2,2) circle (2pt);
\filldraw (-2,2) circle (2pt);
\filldraw (1,3) circle (2pt);
\filldraw (-1,3) circle (2pt);
\end{tikzpicture}
\caption{}
\label{figure1:c}
\end{subfigure}


\caption{An edge \(wt\) incident to a vertex of \(N(v)\setminus\{r_v,\ell_v\}\).}
\end{figure}

Remark that the charge of an edge is well-defined, and the sum of charges of all edges equals the right-hand side of the desired inequality. Hence it is enough to show that if an edge \(wt\in E(G)\) has charge 1 or 2, then it is disjoint from one or two of the edges \(vr_v\) and \(v\ell_v\), respectively. There are the following possible cases:
    \begin{itemize}
        \item[1.] If \(wt\in \mathcal R(v)\), then it has charge 1 and is disjoint from \(v\ell_v\).
        \item[2.] If \(wt \in \mathcal L(v)\), then it has charge 1 and is disjoint from \( vr_v\).
        \item[3.] If the edge \( wt \) connects a vertices in \(N(v)\setminus\{r_v,\ell_v\}\) with a vertex in \(V(G)\setminus (\{v\}\cup N(v)\setminus\{r_v,\ell_v\})\), then \(wt\) has charge 1 and is disjoint from at least one of the edges \(v\ell_v\) or \(vr_v\). See Figures~\ref{figure1:a} and~\ref{figure1:b}.
        \item[4.] If the edge \(wt\) connects two vertices from \(N(v)\setminus\{r_v,\ell_v\}\), then \(wt\) has charge 2 and lies inside of the angle \(r_vv\ell_v\), and thus, it is disjoint from the edges \(v\ell_v\) and \(vr_v\). See Figure~\ref{figure1:c}.
    \end{itemize}
Since any other edge has charge 0, we are done.
\end{proof}

For \( v \in V(G) \), denote by \( \alpha_{\ell}(v) \) the number of vertices \( w\in N(v) \) with \( v=\ell_w \). Analogously, denote by \( \alpha_r(v) \) the number of vertices \( w\in N(v) \) with \( v=r_w \). Since any vertex has exactly one leftmost edge and exactly one rightmost edge, we get 
\[
    \label{equation:sumofalpha}
    \sum_{ v\in V(G) }   \alpha_\ell(v)=\sum_{v\in V(G)}\alpha_r(v)=n.
\]
Also, we use the standard equality
\[
\label{equation:sumofdegrees}
\sum_{w\in V(G)}\deg w=2e.
\]
\begin{corollary}
\label{corollary:summation}
We have
\begin{gather}
\sum_{v\in V(G)} \Big( | DJ_\ell (v) | + | DJ_r (v) | \Big) \geq \sum_{w\in V(G)} \deg^2 w  -
\\ 
 \sum_{w\in V(G)}(\alpha_\ell(w) + \alpha_r(w))\deg w - 2(e -n) + \sum_{v\in V(G)} |\mathcal L(v)| + \sum_{v\in V(G)}|\mathcal R(v)|
\end{gather}
\end{corollary}
\begin{proof}
Summing up the inequality from Lemma~\ref{lemma:simple?} over all vertices of \(G\), we obtain that
\begin{gather}
\sum_{v\in V(G)} \Big( | DJ_\ell (v) | + | DJ_r (v) | \Big) \geq \sum_{v\in V(G)} \sum_{w\in N(v)} (\deg w - 1)-
\\\sum_{w\in V(G)} (\alpha_\ell(w)+\alpha_r(w))(\deg w -1)+\sum_{v\in V(G)} |\mathcal L(v)| + \sum_{v\in V(G)}|\mathcal R(v)|.
\end{gather}
By~\eqref{equation:sumofalpha} and~\eqref{equation:sumofdegrees}, we are done.
\end{proof}

For a vertex \(v\), let \(\mathcal L'(v)\) be a subset of \(\mathcal L(v)\) consisting of edges \(\ell_vw\) such that \(\ell_w= \ell_v\). Analogously, let \(\mathcal R'(v)\) be a subset of \(\mathcal R(v)\) consisting of edges \(r_vw\) such that \(r_w= r_v\). 

\begin{lemma}
\label{lemma:discharging!}
For a vertex \(v\in V(G)\), the following equalities hold
\[
    \sum_{v\in V(G)}|\mathcal L'(v)| = \sum_{v\in V(G)}\frac{\alpha_\ell(v)(\alpha_\ell(v)-1)}{2}
\text{\ \ and\ \ }
    \sum_{v\in V(G)} |\mathcal R'(v)| = \sum_{v\in V(G)} \frac{\alpha_r(v)(\alpha_r(v)-1)}{2}.
\]
\end{lemma}


\begin{proof}
Remark that if we prove
\[
\label{equality1}
    \sum_{v\in V(G): \ell_v=w} |\mathcal L'(v)|=\frac{\alpha_\ell(w)(\alpha_\ell(w)-1)}{2}
\]
for any vertex \( w\in V(G) \), the first desired inequality follows. Analogously, one can show the second inequality.

Since \eqref{equality1} is trivial if \(\alpha_\ell(w)=0 \), we may assume \(\alpha_\ell(w)=k>0\). Let \( u_1, \dots, u_k\in N(w) \) be distinct vertices with \(\ell_{u_i}=w\). Without loss of generality, assume that among \(wu_1, \dots, wu_k\), the edge \(wu_1\) is the leftmost edge, the edge \( wu_2 \) is the second leftmost edge, etc., that is, the angles \(\angle u_iwu_j\) for \( 1\leq i<j\leq k \) are positive. Therefore, \(|\mathcal L'(u_i)| = k-i\) for \(1\leq i\leq k\). Summing up all these equalities, we obtain~\eqref{equality1}. 
\end{proof}

Denote by \( n_\ell\) the number of vertices \( v\in V(G) \) such that for every \(w\in N(v)\) we have \( v=\ell_w \). Analogously, denote by \( n_r \) the number of vertices \( v\in V(G) \) such that for every \( w\in N(v) \) we have \( v = r_w\). 

For a vertex \(v\in V(G)\), put \(\delta_\ell(v)=1\) if there is an edge \(\ell_vx\) such that \(\angle x\ell_v v\) is positive and \(\ell_x\ne \ell_v\), otherwise put \( \delta_\ell(v)=0 \). Analogously, we define \(\delta_r(v)\). Remark that \(\delta_\ell(v)=1\) if and only if the set \( \mathcal L(v)\setminus\mathcal L'(v)\) is not empty. Clearly, we have
\[
\label{sum:ahaha}
    |\mathcal L(v)|\geq |\mathcal L'(v)|+\delta_\ell(v) \text{ and } |\mathcal R(v)|\geq |\mathcal R'(v)|+ \delta_r(v).
\]

\begin{corollary}
\label{maincorollary}
The following inequality holds
\[
\sum_{v \in V(G)}\Big( |DJ_\ell(v)|+ |DJ_r(v)|\Big) \geq \frac{(2e-n)^2}{2(n -  n_\ell)} + \frac{(2e-n)^2}{2(n - n_r)} - (2e - n)+\sum_{v\in V(G)}(\delta_\ell(v)+\delta_r(v)).
\]
\end{corollary}
\begin{proof}
By Corollary~\ref{corollary:summation}, Lemma~\ref{lemma:discharging!} and \eqref{sum:ahaha}, we obtain
\begin{gather}
    \sum\limits_{v \in V(G)}\Big( |DJ_\ell(v)|+ |DJ_r(v)|\Big) \geq     \sum_{w\in V(G)} \Big( \frac{\deg w^2}{2}-\alpha_\ell(w)\deg w + \frac{\alpha_\ell(w)(\alpha_\ell(w)-1)}{2}+
    \\
    \frac{\deg w^2}{2}-\alpha_r(w)\deg w + \frac{\alpha_r(w)(\alpha_r(w)-1)}{2}\Big)-2(e-n)+\sum_{v\in V(G)}\big(\delta_\ell(v)+\delta_r(v)\big)\label{lastsum}
\end{gather}
By~\eqref{equation:sumofalpha} and~\eqref{equation:sumofdegrees}, we have
\begin{gather}
    \sum_{w\in V(G)} \Big( \frac{\deg w^2}{2}-\alpha_\ell(w)\deg w + \frac{\alpha_\ell(w)(\alpha_\ell(w)-1)}{2}\Big)=\\
 \sum_{w\in V(G)}\frac{(\deg w - \alpha_\ell(w))^2}{2} -\frac{n}{2}
    \geq \frac{(2e-n)^2}{2(n-n_\ell)} - \frac{n}{2},
\end{gather}
where to prove the last inequality, we use that the number of vanishing terms \(\deg w-\alpha_\ell(w)\) is equal to \(n_\ell\).

Analogously, we show that
\[
    \sum_{w\in V(G)} \Big( \frac{\deg w^2}{2}-\alpha_r(w)\deg w + \frac{\alpha_r(w)(\alpha_r(w)-1)}{2}\Big)\geq \frac{(2e-n)^2}{2(n-n_r)} - \frac{n}{2}.
\]
Substituting these two inequalities in \eqref{lastsum}, we finish the proof of the corollary.
\end{proof}


\begin{corollary}\label{theorem1corollary} The following inequality holds
\[
\sum\limits_{v \in V(G)}\Big( |DJ(v\ell_v)| + |DJ(vr_v)|\Big) \geq n\left(\frac{2e}{n}-1\right)\left(\frac{2e}{n}-2\right).
\]
\end{corollary}
\begin{proof}
By the definition of \( DJ_r(v) \) and \( DJ_\ell(v)\), we have \( |DJ(v\ell_v)| \geq |DJ_\ell(v)| \) and \( |DJ(vr_v)| \geq |DJ_r(v)|\), and therefore, \cref{maincorollary} yields
\begin{gather}
    \sum\limits_{v \in V(G)}\Big( |DJ(v\ell_v)| + |DJ(vr_v)|\Big) \geq
\frac{(2 e-n)^2}{n} - (2e - n)= n\left(\frac{2e}{n}-1\right)\left(\frac{2e}{n}-2\right),
\end{gather}
which finishes the proof.

\end{proof}
\section{Proof of \cref{theorem:main1}}
\label{section:proof1}

Consider two possible cases. 

\textit{Case 1.} Let \( G \) be a locally convex graph. Since \( (\sqrt{1+8m}+3)/4\geq 1\), we may assume that \( G \) does not contain vertices of degree 0 or 1; otherwise we can delete such a vertex and use induction on the number of vertices. Hence we can apply results of Section~\ref{section:preliminaries}. Combining \cref{theorem1corollary} together with \( |DJ(v\ell_v)| \leq m\) and \( |DJ(vr_v)| \leq m \), we obtain
\[
    2mn \geq n\left(\frac{2e}{n}-1\right)\left(\frac{2e}{n}-2\right)=n\left(\left(\frac{2e}{n} -\frac32\right)^2 - \frac14\right),
\]
which finishes the proof of the first case.

\textit{Case 2.} Let \( G \) have a non-convex vertex \( v \). Hence, there are vertices \( v_1, v_2, v_3 \in N(v) \) such that \( v \) lies in the convex hull of \( v_1, v_2,\) and \( v_3 \). Remark that any edge that is not incident to \( v \) is disjoint from at least one of the edges \( vv_1, vv_2, vv_3 \). Since each of the edges \( vv_1, vv_2, \) and \( vv_3\) is disjoint from at most \( m \) edges, we have that there are at most \( 3m + \deg v \) edges in \( G \). The inequality \( \deg v < n \) finishes the proof of the second case. 


\section{Proof of \cref{theorem:main2}}
\label{section:proof2}

The proof is by induction on \( e \). 

\textit{Base of induction.} Assume that \( e \leq 3n/2 \), and thus, \( d(G)=2e/n\leq 3\).

If \(1\leq d(G) \leq 2\), the desired inequality trivially follows from \(\binom{d(G)}{3}\leq 0\).

If \(2<d(G)\leq 3\), then consider a graph \( G' \) obtained from \( G \) by deleting one edge in every pair of disjoint edges. Clearly, \( |E(G')| \geq  e - |DJ(G)| \) and edges in \( G' \) are pairwise intersecting. By \cref{erdos}, we have \( |E(G')| \leq n \). Thus,
\[
    |DJ(G)| \geq  e - n = \frac{n(d(G)-2)}{2} \geq \frac{n}{2} \binom{d(G)}{3}.
\]

\textit{Induction step.} Assume that \( e > 3n/2 \), and thus, \(d(G)>3\).

First, we show that we may assume that \( G \) does not contain vertices of degree 0 or~1. Indeed, let 
\[
    F(G) := \frac{|V(G)|}{2} \binom{d(G)}{3}
\]
and suppose that \( G \) has a vertex of degree 0 or 1. Let \( G' \) be a graph obtained from \( G \) by removing this vertex. Then \(|DJ(G)| \geq |DJ(G')|\) and 
\begin{gather}
    F(G') \geq \frac{n-1}{2} \binom{\frac{2e-2}{n-1}}{3} =
    \frac{2e-2n}{12}  \left(\frac{2e-2}{n-1}\right)\left(\frac{2e-n-1}{n-1}\right) \overset{(*)}{>} \\
    \frac{2e-2n}{12}  \left(\frac{2e-2}{n-1}\right)\left(\frac{2e-n-1}{n-1}\right)\left(\frac{e(n-1)}{(e-1)n}\right)\left(\frac{(2e-n)(n-1)}{(2e-n-1)n}\right)=\\
     \frac{2e(2e-n)(2e-2n)}{12n^2} = F(G).
\end{gather}
Here in \( (*) \) we use that 
\[
\frac{e(n-1)}{(e-1)n} < 1 \text{  and  } 
\frac{(2e-n)(n-1)}{(2e-n-1)n} < 1.
\]
Both of these inequalities follow from the fact that \( e > n > 1 \). Since \(d(G')>d(G)>3\), we may apply induction on the number of vertices and obtain the desired inequality. Therefore, without loss of generality we assume that all the vertices of \( G \) have degree at least 2, and thus, we can apply results of Section~\ref{section:preliminaries}.
\medskip

By  \cref{maincorollary}, we may assume without loss of generality that
\[
\label{equation of corollary}
\sum\limits_{v \in V(G)}\ncrlsetcard{v} \geq \frac{(2 e-n)^2}{2(n -  n_\ell) } -e +\frac{n}{2} + \sum_{v\in V(G)}\delta_\ell(v).
\]

Let \(G'\) be a graph obtained from \(G\) by deleting all leftmost edges and all vertices \(v\in V(G)\) with \(\alpha_\ell(v)=\deg v\), and thus, \(|V(G')|=n-n_\ell\) and \(|E(G')|=e-n+t_\ell\), where \(t_\ell\) is the number of double leftmost edges in \(G\). An edge \(uv\in E(G)\) is \textit{double leftmost} if \(u=\ell_v\) and \(v=\ell_u\). Before we apply the induction hypothesis for the graph \(G'\), let us prove a few auxiliary facts.
\medskip 

First, notice that 
\begin{equation}
\label{equation:djg}
|DJ(G)| \geq |DJ(G')| + \sum\limits_{v \in  V(G)} |DJ_\ell(v)| - |N_\ell(G)|, 
\end{equation}
where \(N_\ell(G)\) is the set of pairs of leftmost edges \(v\ell_v, u\ell_u\in E(G)\) such that \(vu\) is an edge in \(G\). Remark that each such pair correspond to an edge in \(E(G')\) in the following way: for every edge \(uv \in E(G)\), the leftmost edges \(u\ell_u, v\ell_v\in E(G)\) are disjoint if and only if \(uv\in E(G')\). Therefore, \(|N_\ell(G)|=|E(G')|=e-n+t_\ell\).

Second, let us show
\[
\label{equation:the new inequality}
    \sum_{v\in V(G)}\delta_\ell(v)+n_\ell \geq 2t_\ell\geq n_\ell.
\]
Indeed, for any double leftmost edge \(uv\in E(G)\) we have
\[
\delta_\ell(v)+\delta_\ell(u)+\beta_\ell(v)+\beta_\ell(u)= 2,
\]
where for every \(w\in V(G)\) put \(\beta_\ell(w)=1\) if \(\deg w = \alpha_\ell(w)\) and otherwise \(\beta_\ell(w)=0\). Summing up this equality over all double leftmost edges in \(G\) and using that a vertex is incident to at most one double leftmost edge, we easily obtain \eqref{equation:the new inequality}.

Third, by~\eqref{equation:the new inequality}, we have
\[
\label{equation:newavarage}
    d(G') = \frac{2(e-n+t_\ell)}{n -  n_\ell}\geq \frac{2e-n}{n-n_\ell}-1\geq d(G)-2> 1,
\]
and thus, we can apply the induction hypothesis for \(G'\).
\medskip

By the induction hypothesis, \eqref{equation:djg}, \eqref{equation:newavarage}, and \eqref{equation of corollary}, we obtain
\[
|DJ(G)|\geq \frac{(n -  n_\ell)}{2} \cdot\binom{\frac{2e-n}{n-n_\ell} - 1}{3} + \frac{(2e-n)^2}{2(n -  n_\ell)} -e+\frac{n}{2}+\sum_{v\in V(G)}\delta_\ell(v)- e + n - t_\ell.
\]
By~\eqref{equation:the new inequality}, we obtain
\begin{gather}
|DJ(G)|\geq 
\frac{n -  n_\ell}{2} \cdot\binom{\frac{2e-n}{n-n_\ell} - 1}{3} + \frac{(2e-n)^2}{2(n -  n_\ell) } - (2e-n) + \frac{n-n_\ell}{2} =
\\ 
\frac{n-n_\ell}{2}\cdot \Bigg(\binom{\frac{2e-n}{n-n_\ell}-1}{3}+\left(\frac{2e-n}{n-n_\ell}-1\right)^2\Bigg)=\\
\frac{2e-n}{12}\cdot \Bigg(\left(\frac{2e-n}{n-n_\ell}\right)^2-1\Bigg)\geq
\frac{2e-n}{12}\cdot \bigg(\left(\frac{2e-n}{n}\right)^2-1\bigg)=\frac{n}{2}\binom{\frac{2e}{n}}{3},
\end{gather}
which finishes the proof of the theorem.

\section{Discussion}
\label{section:discussion}

\subsection{Tightness of the theorems.} Let \( n, k \) be integers of different parity such that \( n-2 > k>2 \). Let \(G_{n,k}\) be a convex graph whose vertices are denoted \(x_1,\dots, x_n\) in cyclic order and edges are \(x_{i}x_{j}\) for \(j-i\equiv\frac{n-k-1}{2},\dots,\frac{n+k+1}{2} (\mathrm{mod}\ n)\); see Figure \ref{figure:example}. 

It is not difficult to verify that the number of edges of \(G_{n,k}\) is \(n(k+2)/2\). Moreover,
 \[
 |DJ(G_{n,k})| = \frac{n}{2} \cdot \binom{k+2}{3} \text{ and }
 |DJ(uv)| \leq \frac{k(k+1)}{2} \text{ for any edge } uv\in E(G_{n,k}).
 \]
Therefore, for the graph \(G_{n,k}\), the bounds in Theorems~\ref{theorem:main1} and~\ref{theorem:main2} are tight. 

\begin{figure}[h]

\begin{subfigure}[b]{0.45\textwidth}
\begin{tikzpicture}[line cap=round,line width = 1pt, x = 3.03085cm, y = 3.03085cm]
\draw (1.0, 0.0) node  [right]{\(x_1\)};
\draw (0.8412535328311812, 0.5406408174555976)  node  [right]{\( x_2 \)};
\draw (0.41541501300188644, 0.9096319953545183)  node  [right]{\( x_3 \)};
\draw (-0.142314838273285, 0.9898214418809328)  node  [right]{\( x_4 \)};
\draw (-0.654860733945285, 0.7557495743542583)  node  [above right]{\( x_5 \)};
\draw (-0.9594929736144974, 0.28173255684142967)  node  [above]{\( x_6 \)};
\draw (-0.9594929736144975, -0.2817325568414294)  node  [above left]{\( x_7 \)};
\draw (-0.6548607339452852, -0.7557495743542582)  node  [left]{\( x_8 \)};
\draw (-0.14231483827328523, -0.9898214418809327)  node  [left]{\( x_9 \)};
\draw (0.41541501300188605, -0.9096319953545186)  node  [right]{\(x_{10}\)};
\draw (0.8412535328311812, -0.5406408174555974)  node  [right]{\( x_{11}\)};

\filldraw (1.0, 0.0) circle (2pt);
\filldraw (0.8412535328311812, 0.5406408174555976)  circle (2pt);
\filldraw (0.41541501300188644, 0.9096319953545183) circle (2pt);
\filldraw (-0.142314838273285, 0.9898214418809328)  circle (2pt);
\filldraw (-0.654860733945285, 0.7557495743542583)  circle (2pt);
\filldraw (-0.9594929736144974, 0.28173255684142967)  circle (2pt);
\filldraw (-0.9594929736144975, -0.2817325568414294)  circle (2pt);
\filldraw (-0.6548607339452852, -0.7557495743542582)  circle (2pt);
\filldraw (-0.14231483827328523, -0.9898214418809327)  circle (2pt);
\filldraw (0.41541501300188605, -0.9096319953545186)  circle (2pt);
\filldraw (0.8412535328311812, -0.5406408174555974)  circle (2pt);

\draw (1.0, 0.0)--(-0.654860733945285, 0.7557495743542583);
\draw (1.0, 0.0)--(-0.9594929736144974, 0.28173255684142967);
\draw (1.0, 0.0)--(-0.9594929736144975, -0.2817325568414294);
\draw (1.0, 0.0)--(-0.6548607339452852, -0.7557495743542582);
\draw (0.8412535328311812, 0.5406408174555976)--(-0.9594929736144974, 0.28173255684142967);
\draw (0.8412535328311812, 0.5406408174555976)--(-0.9594929736144975, -0.2817325568414294);
\draw (0.8412535328311812, 0.5406408174555976)--(-0.6548607339452852, -0.7557495743542582);
\draw (0.8412535328311812, 0.5406408174555976)--(-0.14231483827328523, -0.9898214418809327);
\draw (0.41541501300188644, 0.9096319953545183)--(-0.9594929736144975, -0.2817325568414294);
\draw (0.41541501300188644, 0.9096319953545183)--(-0.6548607339452852, -0.7557495743542582);
\draw (0.41541501300188644, 0.9096319953545183)--(-0.14231483827328523, -0.9898214418809327);
\draw (0.41541501300188644, 0.9096319953545183)--(0.41541501300188605, -0.9096319953545186);
\draw (-0.142314838273285, 0.9898214418809328)--(-0.6548607339452852, -0.7557495743542582);
\draw (-0.142314838273285, 0.9898214418809328)--(-0.14231483827328523, -0.9898214418809327);
\draw (-0.142314838273285, 0.9898214418809328)--(0.41541501300188605, -0.9096319953545186);
\draw (-0.142314838273285, 0.9898214418809328)--(0.8412535328311812, -0.5406408174555974);
\draw (-0.654860733945285, 0.7557495743542583)--(1.0, 0.0);
\draw (-0.654860733945285, 0.7557495743542583)--(-0.14231483827328523, -0.9898214418809327);
\draw (-0.654860733945285, 0.7557495743542583)--(0.41541501300188605, -0.9096319953545186);
\draw (-0.654860733945285, 0.7557495743542583)--(0.8412535328311812, -0.5406408174555974);
\draw (-0.9594929736144974, 0.28173255684142967)--(1.0, 0.0);
\draw (-0.9594929736144974, 0.28173255684142967)--(0.8412535328311812, 0.5406408174555976);
\draw (-0.9594929736144974, 0.28173255684142967)--(0.41541501300188605, -0.9096319953545186);
\draw (-0.9594929736144974, 0.28173255684142967)--(0.8412535328311812, -0.5406408174555974);
\draw (-0.9594929736144975, -0.2817325568414294)--(1.0, 0.0);
\draw (-0.9594929736144975, -0.2817325568414294)--(0.8412535328311812, 0.5406408174555976);
\draw (-0.9594929736144975, -0.2817325568414294)--(0.41541501300188644, 0.9096319953545183);
\draw (-0.9594929736144975, -0.2817325568414294)--(0.8412535328311812, -0.5406408174555974);
\draw (-0.6548607339452852, -0.7557495743542582)--(1.0, 0.0);
\draw (-0.6548607339452852, -0.7557495743542582)--(0.8412535328311812, 0.5406408174555976);
\draw (-0.6548607339452852, -0.7557495743542582)--(0.41541501300188644, 0.9096319953545183);
\draw (-0.6548607339452852, -0.7557495743542582)--(-0.142314838273285, 0.9898214418809328);
\draw (-0.14231483827328523, -0.9898214418809327)--(0.8412535328311812, 0.5406408174555976);
\draw (-0.14231483827328523, -0.9898214418809327)--(0.41541501300188644, 0.9096319953545183);
\draw (-0.14231483827328523, -0.9898214418809327)--(-0.142314838273285, 0.9898214418809328);
\draw (-0.14231483827328523, -0.9898214418809327)--(-0.654860733945285, 0.7557495743542583);
\draw (0.41541501300188605, -0.9096319953545186)--(0.41541501300188644, 0.9096319953545183);
\draw (0.41541501300188605, -0.9096319953545186)--(-0.142314838273285, 0.9898214418809328);
\draw (0.41541501300188605, -0.9096319953545186)--(-0.654860733945285, 0.7557495743542583);
\draw (0.41541501300188605, -0.9096319953545186)--(-0.9594929736144974, 0.28173255684142967);
\draw (0.8412535328311812, -0.5406408174555974)--(-0.142314838273285, 0.9898214418809328);
\draw (0.8412535328311812, -0.5406408174555974)--(-0.654860733945285, 0.7557495743542583);
\draw (0.8412535328311812, -0.5406408174555974)--(-0.9594929736144974, 0.28173255684142967);
\draw (0.8412535328311812, -0.5406408174555974)--(-0.9594929736144975, -0.2817325568414294);
\end{tikzpicture}
\subcaption{\( n = 11, k = 2\)}
\end{subfigure}
\begin{subfigure}[b]{0.45\textwidth}
\begin{tikzpicture}[line cap=round,line width = 1pt, x=3cm,y=3cm]


\draw (1.0, 0.0) node [right] {\( x_1 \)};
\draw (0.8660254038, 0.5) node [right] {\( x_2\)};
\draw (0.5, 0.8660254038) node [right] {\(x_3\)};
\draw (0.0, 1.0) node [right] {\( x_4 \)};
\draw (-0.5, 0.8660254038) node [above right] {\( x_5 \)};
\draw (-0.8660254038, 0.5) node [above right] {\( x_6 \)};
\draw (-1.0, 0.0) node [above] {\( x_7 \)};
\draw (-0.8660254038, -0.5) node [above left] {\( x_8 \)};
\draw (-0.5, -0.8660254038) node [above left] {\( x_9 \)};
\draw (0.0, -1.0) node [left] {\( x_{10} \)};
\draw (0.5, -0.8660254038) node [right] {\( x_{11} \)};
\draw (0.8660254038, -0.5) node [right] {\( x_{12} \)};

\filldraw (1.0, 0.0) circle (2pt);
\filldraw (0.8660254038, 0.5) circle (2pt);
\filldraw (0.5, 0.8660254038) circle (2pt);
\filldraw (0.0, 1.0) circle (2pt);
\filldraw (-0.5, 0.8660254038) circle (2pt);
\filldraw (-0.8660254038, 0.5) circle (2pt);
\filldraw (-1.0, 0.0) circle (2pt);
\filldraw (-0.8660254038, -0.5) circle (2pt);
\filldraw (-0.5, -0.8660254038) circle (2pt);
\filldraw (0.0, -1.0) circle (2pt);
\filldraw (0.5, -0.8660254038) circle (2pt);
\filldraw (0.8660254038, -0.5) circle (2pt);

\draw (1.0 ,  0.0 ) -- ( -0.5 ,  0.8660254038 );
\draw ( 1.0 ,  0.0 ) -- ( -0.8660254038 ,  0.5 );
\draw ( 1.0 ,  0.0 ) -- ( -1.0 ,  0.0 );
\draw ( 1.0 ,  0.0 ) -- ( -0.8660254038 ,  -0.5 );
\draw ( 1.0 ,  0.0 ) -- ( -0.5 ,  -0.8660254038 );
\draw ( 0.8660254038 ,  0.5 ) -- ( -0.8660254038 ,  0.5 );
\draw ( 0.8660254038 ,  0.5 ) -- ( -1.0 ,  0.0 );
\draw ( 0.8660254038 ,  0.5 ) -- ( -0.8660254038 ,  -0.5 );
\draw ( 0.8660254038 ,  0.5 ) -- ( -0.5 ,  -0.8660254038 );
\draw ( 0.8660254038 ,  0.5 ) -- ( 0.0 ,  -1.0 );
\draw ( 0.5 ,  0.8660254038 ) -- ( -1.0 ,  0.0 );
\draw ( 0.5 ,  0.8660254038 ) -- ( -0.8660254038 ,  -0.5 );
\draw ( 0.5 ,  0.8660254038 ) -- ( -0.5 ,  -0.8660254038 );
\draw ( 0.5 ,  0.8660254038 ) -- ( 0.0 ,  -1.0 );
\draw ( 0.5 ,  0.8660254038 ) -- ( 0.5 ,  -0.8660254038 );
\draw ( 0.0 ,  1.0 ) -- ( -0.8660254038 ,  -0.5 );
\draw ( 0.0 ,  1.0 ) -- ( -0.5 ,  -0.8660254038 );
\draw ( 0.0 ,  1.0 ) -- ( 0.0 ,  -1.0 );
\draw ( 0.0 ,  1.0 ) -- ( 0.5 ,  -0.8660254038 );
\draw ( 0.0 ,  1.0 ) -- ( 0.8660254038 ,  -0.5 );
\draw ( -0.5 ,  0.8660254038 ) -- ( -0.5 ,  -0.8660254038 );
\draw ( -0.5 ,  0.8660254038 ) -- ( 0.0 ,  -1.0 );
\draw ( -0.5 ,  0.8660254038 ) -- ( 0.5 ,  -0.8660254038 );
\draw ( -0.5 ,  0.8660254038 ) -- ( 0.8660254038 ,  -0.5 );
\draw ( -0.8660254038 ,  0.5 ) -- ( 0.0 ,  -1.0 );
\draw ( -0.8660254038 ,  0.5 ) -- ( 0.5 ,  -0.8660254038 );
\draw ( -0.8660254038 ,  0.5 ) -- ( 0.8660254038 ,  -0.5 );
\draw ( -1.0 ,  0.0 ) -- ( 0.5 ,  -0.8660254038 );
\draw ( -1.0 ,  0.0 ) -- ( 0.8660254038 ,  -0.5 );
\draw ( -0.8660254038 ,  -0.5 ) -- ( 0.8660254038 ,  -0.5 );

\end{tikzpicture}
\subcaption{\( n = 12, k = 3 \)}
\end{subfigure}
\caption{Graph \(G_{n,k}\).}
\label{figure:example}
\end{figure}
\subsection{Open problems and conjectures.}
Unfortunately, Theorem~\ref{theorem:main2} becomes wrong if one replaces the bound
\[
\frac{n}{2}\binom{d(G)}{3}\quad \text{by}\quad
\frac{1}{2}\sum_{v \in V(G)}\binom{\deg v}{3}.
\]
Indeed, consider a convex graph \(G\) on \(2n+2\) vertices consisting of two disjoint copies of a star \( S_n \)\footnote{A star \(S_k\) is a graph on \( k + 1 \) vertices with one vertex of degree \( k \) and \( k \) vertices of degree \( 1 \).}. For \( n\geq 9\), this graph \(G\) does not satisfy the desired inequality because of
\[
\frac{1}{2}\sum_{v \in V(G)}\binom{\deg v}{3} = \binom{n}{3} > n^2= DJ(G).
\]

We believe that the following conjectures hold.
\begin{conjecture}
\label{conjecture:main}
Let \(m\) be a non-negative integer and \(G\) be a geometric graph such that \( |DJ(uv)|\leq m\) for any edge \( uv\in E(G) \). Then
\[ 
    |E(G)|\leq \frac{\sqrt{1+8m}+3}{4}\cdot |V(G)|.
\]
\end{conjecture}
\begin{conjecture}
For any geometric graph \( G \) with \(2|E(G)|\geq |V(G)|\), we have
\[
|DJ(G)| \geq \frac{n}{2} \cdot \binom{d(G)}{3}.
\]
\end{conjecture}
At last, remark that Conjecture~\ref{conjecture:main} is proved if a geometric graph \( G\) has at least \(\frac{3(\sqrt{1+8m}-3)m}{2(m-1)}\) vertices.

\bibliographystyle{amsalpha}

2021-11-11T02:03:01.000
2111
2111.05425
en
https://arxiv.org/abs/2111.05425
A geometric graph is a graph drawn in the plane so that its vertices and edges are represented by points in general position and straight line segments, respectively. A vertex of a geometric graph is called pointed if it lies outside of the convex hull of its neighbours. We show that for a geometric graph with $n$ vertices and $e$ edges there are at least $\frac{n}{2}\binom{2e/n}{3}$ pairs of disjoint edges provided that $2e\geq n$ and all the vertices of the graph are pointed. Besides, we prove that if any edge of a geometric graph with $n$ vertices is disjoint from at most $ m $ edges, then the number of edges of this graph does not exceed $n(\sqrt{1+8m}+3)/4$ provided that $n$ is sufficiently large.These two results are tight for an infinite family of graphs.
Combinatorics (math.CO); Computational Geometry (cs.CG)
Disjoint edges in geometric graphs
Qwen/Qwen-72B
1. YES
2. YES