TITLE: Let $f: [0, 1] \to \mathbb{R}$ s.t $f(0)=f(1)=0$ then measure of $A = \{h \in [0, 1] \mid \exists x \text{ such that }f(x+h) =f(x)\} \geq 1/2$.
QUESTION [5 upvotes]: Let $f:[0,1]\to\mathbb R$ be a continuous function s.t. $f(0)=f(1)=0$. Let $$A = \{h \in [0, 1] \mid \exists x \text{ such that }f(x+h) =f(x)\}.$$ Show that set $A$ has Lebesgue measure $\geq 1/2$.

I have no clue to prove the claim. Can anyone give me some detail hints? Thank you in advance.

REPLY [2 votes]: First let's show that $A$ is Borel. Given $\epsilon>0$, let $A_\epsilon=\left\{h\in[0,1]:\exists x\in[0,1-h]\text{ such that }|f(x)-f(x+h)|<\epsilon\right\}$. Since $f$ is continuous, we can consider only rational numbers in the definition of $A_\epsilon$, that is, if $\left\{q_n:n=1,2,\ldots\right\}$ denote the rationals in $[0,1]$, we have
\begin{align*}
A_\epsilon&=\left\{h\in[0,1]:\exists n\text{ s.t. }q_n+h\leq 1\text{ and }|f(q_n)-f(q_n+h)|<\epsilon\right\}\\
&=\bigcup_{n=1}^\infty\left\{h\in[0,1-q_n]:|f(q_n)-f(q_n+h)|<\epsilon\right\}
\end{align*}
Each set in the union in the RHS is Borel (because $h\mapsto f(q_n+h)$ is continuous), so each $A_\epsilon$ is Borel, and thus $A=\bigcap_{k=1}^\infty A_{1/k}$ is Borel.
Now extend $f$ to $[0,2]$ by setting $f(x)=f(x-1)$ for each $x\in[0,2]$. Let $M\in[0,1]$ be a point of maximum for $f$ and $m\in[0,1]$ be a point of minimum for $f$ (so they are also points of maximum and minimum for the extension of $f$).
Given $h\in[0,1]$, we have $f(M+h)\leq f(M)$ and $f(m+h)\geq f(m)$, so by Intermediate Value Theorem there exists a point $x\in[0,1]$ between $M$ and $m$ such that $f(x+h)=f(x)$. We have two cases:

If $x+h\in[0,1]$, then $h\in A$.
If $x+h\not\in[0,1]$, i.e., $x+h\in[1,2]$. Denote $y=x+h-1$, so that $y\in[0,1]$, $y+(1-h)=x\in[0,1]$, and $f(y+(1-h))=f(x)=f(x+h)=f(x+h-1)=f(y)$, therefore $1-h\in A$.

Anyway, for each $h\in[0,1]$ we have either $h\in A$ or $1-h\in A$. Denoting by $\chi_B$ the characteristic function of a set $B$, this implies that $\chi_{[0,1]}(h)\leq \chi_A(h)+\chi_{A}(1-h)$. Integrating this over $[0,1]$ yields $1<2\lambda(A)$ (to integrate the last term use invariance of $\lambda$ under the map $h\mapsto(1-h)$), which is what we wanted.

If $f$ is positive, then we indeed have $A=[0,1]$. Indeed, in this case, for each $h\in[0,1]$ we have $f(0)\leq f(h)$ and $f(1-h)\geq f(1)$, so again there is some point $x$ between $0$ and $1-h$ for which $f(x)=f(x+h)$, so $h\in A$.
An example to see that the inequality $\lambda(A)\geq 1/2$ is optimal in the general case is $f(x)=\sin(2\pi x)$, in which case $A=[0,1/2]$.


TITLE: To find the equation of the plane.
QUESTION [0 upvotes]: Let $a= (3,1,-2), v_1 = (1,-1,2),v_2=(1,0,-1)$ and consider the set $V = \{ a+c_1v_1+c_2v_2, c_1,c_2 \in \Bbb{R}\}$. Note that the set is a plane. We have to find the equation of the plane.
Let $u_1 = v_1-a = (-2,-2,4)$ and $u_2 = v_2 -a= (-2,-1,1)$. Now $u_1 \times u_2 = (2,-6,-2)$ is the normal to the plane. Thus the equation of plane passing through $a= (3,1,-2)$ and normal to $(2,-6,-2)$ is given by:
$$2(x-3)-6(y-1)-2(z+2) = 0 \implies x-3y-z-2=0$$
Is the solution to the problem correct?

REPLY [1 votes]: What you derived is the plane containing the three given points, which is not what the question asks.
From the set defined by
$$V = \{ a+c_1v_1+c_2v_2 \}$$
you have, for each coordinate,
$$x=3+c_1+c_2$$
$$y=1-c_1$$
$$z=-2+2c_1-c_2$$
Eliminate $c_1$ and $c_2$ to obtain the plane
$$x+3y+z-4=0$$
This is the plane containing the point $a$ and parallel to that formed by the vectors $\vec{v}_1$ and $\vec{v}_2$.


TITLE: find the limit of one sequence $\lim_{ n \to \infty } \cos(\frac{\pi}{2n + 1})\cos(\frac{2\pi}{2n + 1})...\cos(\frac{n\pi}{2n + 1}) $
QUESTION [3 upvotes]: I want to find the limit of this below Sequence.
the first sentence of this sentence n approaches infinity they approaches to 1 but not same for last sentence. How can we solve it.
$\lim_{ n \to \infty } \cos(\frac{\pi}{2n + 1})\cos(\frac{2\pi}{2n + 1})\cos(\frac{3\pi}{2n + 1})...\cos(\frac{n\pi}{2n + 1}) $
Is it possible to help me?
I'm sorry for bad English.
Thanks.

REPLY [4 votes]: Each factor in the product lies between $0$ and $1.$ Thus the product lies between $0$ and the last factor, which is $\cos \pi(n/(2n+1)).$ As $n\to \infty,$ this factor $\to \cos (\pi/2) =0.$ Therefore the product converges to $0.$


TITLE: Is a bounded linear operator, which is bijective between dense subspaces, an isomorphism?
QUESTION [1 upvotes]: Suppose that we have Banach spaces $X$ and $Y$ and a bounded linear operator $T\colon X\to Y$ that maps a dense subspace $D_{X}\subset X$ bijectively into a dense subspace $D_{Y}\subset Y$. Can we conclude that $T$ is an isomorphism?
Here is what I tried for proving surjectivity: Pick any $y\in Y$. Then there is a sequence $D_{Y}\ni y_{n}\to y$. By assumption there is a (unique) $x_{n}\in D_{X}$ such that $y_{n}=T(x_{n})$. Now I tried to prove that $x_{n}$ is Cauchy, so that it has a limit $x\in X$, and then I was hoping that $y=T(x)$. But I cannot find an estimation of the form $\|x_{i}-x_{j}\|\leq C\|T(x_{i})-T(x_{j})\|$.
Any help would be greatly appreciated!

REPLY [2 votes]: Not even true when $X=Y$ is a Hilbert space. Any injective compact operator on an infinite-dimensional Hilbert space is an example.
For instance, take $X=Y=\ell^2(\mathbb N)$ and $$Tx=\big(x_1,\tfrac{x_2}2,\tfrac{x_3}3,\ldots\big),$$ on the dense subspace $$c_{00}=\{x\in X:\ \text{ finite support }\}.$$
The necessary and sufficient condition for $T$ to extend to an invertible operator on the full space is that $T^{-1}$ is bounded.


TITLE: Sum of two subspaces is a subspace
QUESTION [4 upvotes]: I am wondering if someone can check my proof that the sum of two subspaces is a subspace:
1) First show that $0 \in W_1 + W_2$:
Since $W_1, W_2$ are subspaces, we know that $0 \in W_1, W_2$.
So if $w_1, w_2 = 0, w_1 + w_2 = 0 + 0 = 0 \in W_1 + W_2$.
2) Show that $cu+v \in W_1 + W_2$.
Let $W = W_1 + W_2$
Let $cu \in W$. We can find some $u_1 \in W_1, u_2 \in W_2, c \in \mathbb{F}$ such that $cu = u_1 + u_2$.
Similarly, since $v \in W$, we can find $v_1, v_2 \in W_1, W_2$ such that $v = v_1 + v_2$.
So $cu+v = c(u_1 + u_2) + (v_1 + v_2)$
$= cu_1 + cu_2 + v_1 + v_2$
$= cu_1 + v_1 + cu_2 + v_2$
And so $cu_1 + v_1 \in W_1$ and $cu_2 + v_2 \in W_2$, and therefore $cu+v \in W_1 + W_2$.
Is my proof correct? Please let me know!

REPLY [3 votes]: Your proof is not rigorously correct.
The first part 1) is perfect.
For the part 2), there are some points that can be improved.

Your started with "let $cu\in W$". You need to start with "let $u\in W$." Why can you conclude that $cu\in W$, for any $c\in\mathbb{F}$?
Your conclusion $cu+v=cu_1+v_1+cu_2+v_2$ is correct. But why $cu_1+v_1\in W_1$ and $cu_2+v_2\in W_2$?

You should focus in these details in order to obtain a logically correct proof.

Minor detail: the notation $v_1,v_2\in W_1,W_2$, despite well understable, is not standard. It is better to write $w_1\in W_1$ and $w_2\in W_2$.


text:
\begin{document}
\pagestyle{plain}
\maketitle
\begin{sloppypar}
\begin{abstract}
A strong clique in a graph is a clique intersecting all inclusion-maximal stable sets. Strong cliques play an important role in the study of perfect graphs. We study strong cliques in the class of diamond-free graphs, from both structural and algorithmic points of view.
We show that the following five {\sf NP}-hard or {\sf co-NP}-hard problems remain intractable when restricted to the class of diamond-free graphs: Is a given clique strong? Does the graph have a strong clique? Is every vertex contained in a strong clique? Given a partition of the vertex set into cliques, is every clique in the partition strong? Can the vertex set be partitioned into strong cliques?

On the positive side, we show that the following two problems whose computational complexity is open in general can be solved in linear time in the class of diamond-free graphs: Is every maximal clique strong? Is every edge contained in a strong clique? These results are derived from a characterization of diamond-free graphs in which every maximal clique is strong, which also implies an improved

Erd\H{o}s-Hajnal property for such graphs.

\end{abstract}
\end{sloppypar}

\begin{sloppypar}
\keywords{maximal clique, maximal stable set, diamond-free graph, strong clique, simplicial clique, CIS graph, NP-hard problem, linear-time algorithm, Erd\H{o}s-Hajnal property}\\
\end{sloppypar}

\section{Introduction}\label{sec:intro}

\paragraph{Background and motivation.}

\begin{sloppypar}
Given a graph $G$, a \emph{clique} in $G$ is a set of pairwise adjacent vertices, and a \emph{stable set} (or \emph{independent set}) is a set of pairwise non-adjacent vertices. A clique (resp., stable set) is \emph{maximal} if it is not contained in any larger clique (resp., stable set). A clique is \emph{strong} if intersects all maximal stable sets and a strong stable set is defined analogously. The concepts of strong cliques and strong stable sets in graphs play an important role in the study of perfect graphs (see, e.g.,~\cite{MR778744}) and were studied in a number of papers (see, e.g.,~\cite{HUJDUROVIC20192738,MR1301855,S0012365X0900547020100101, MR1344757,BOROS201478, S009589560400028020040101, MR3278773, S0166218X1000397520110101, MR1212874,BOROS201747, HMR2018,MR2080087, MR3623393,MR3474710,e6c81804d9c9450c946b6f3cece46881,alcon2019characterization}).

Several algorithmic problems related to strong cliques and stable sets in graphs are
{\sf NP}-hard
or {\sf co-NP}-hard, in particular:

\begin{itemize}
\item {\sc Strong Clique}: Given a clique $C$ in a
graph $G$, is $C$ strong?
\item {\sc Strong Clique Existence}:
Given a graph $G$, does $G$ have
a strong clique?
\item {\sc Strong Clique Vertex Cover}:
Given a graph $G$, is every vertex
contained in a strong clique?
\item {\sc Strong Clique Partition}:
Given a graph $G$ and a partition of its vertex set into cliques, is every clique in the partition strong?
\item {\sc Strong Clique Partition Existence}:
Given a graph $G$, can its vertex set be partitioned into strong cliques?
\end{itemize}
The first problem in the above list is {\sf co-NP}-complete (see~\cite{MR1344757}), the second one is {\sf NP}-hard (see~\cite{MR1301855}), and the remaining three are {\sf co-NP}-hard (see~\cite{HUJDUROVIC20192738} for the third and the fourth problem\footnote{In~\cite{HUJDUROVIC20192738}, the authors state that the two problems are {\sf NP}-hard, but their proof actually shows {\sf co-NP}-hardness.} and~\cite{MR1217991,MR1161178,HMR2018} for the fifth one).\end{sloppypar}

\begin{sloppypar}
Another interesting property related to strong cliques is the one defining CIS graphs. A graph is said to be \emph{CIS} if every maximal clique is strong, or equivalently, if every maximal stable set is strong, or equivalently, if every maximal clique intersects every maximal stable set. Although the name CIS (Cliques Intersect Stable sets) was suggested by Andrade et al.~in a recent book chapter~\cite{e6c81804d9c9450c946b6f3cece46881}, this concept has been studied under different names
since the 1990s~\cite{MR1344757,S0012365X0900547020100101,BOROS201478,MR3278773,
S009589560400028020040101,
S0166218X1000397520110101,
MR2234986} (see~\cite{MR1344757} for a historical overview).
Several other graph classes studied in the literature can be defined in terms of properties involving strong cliques (see, e.g., \cite{MR1212874,BOROS201747, HMR2018, HUJDUROVIC20192738, MR3623393}).
\end{sloppypar}

There are several intriguing open questions related to strong cliques and strong stable sets,
for instance: (i) What is the complexity of determining whether every edge of a given graph is contained in a strong
clique?
(See, e.g.,\cite{MR3474710}.)
(ii) What is the complexity of recognizing CIS graphs?
(See, e.g.,\cite{e6c81804d9c9450c946b6f3cece46881}.)
(iii) Is there some $\varepsilon>0$ such that every $n$-vertex CIS graph has either a clique or a stable set of size at least $n^\varepsilon$?
(See~\cite{alcon2019characterization}.)

The main purpose of this paper is to study strong cliques in the class of diamond-free graphs. The \emph{diamond} is the graph obtained by removing an edge from the complete graph on four vertices, and a graph $G$ is said to be \emph{diamond-free} if no induced subgraph of $G$ is isomorphic to the diamond. Our motivation for focusing on the class of diamond-free graphs comes
from several sources. First, no two maximal cliques in a diamond-free graph share an edge, which makes interesting the question to what extent this structural restriction is helpful for understanding strong cliques.
Second, structural and algorithmic questions related to strong cliques in particular graph classes were extensively studied in the literature (see, e.g.,\cite{MR3474710,alcon2019characterization,HUJDUROVIC20192738,HMR2018,MR3278773,BOROS201478,MR2080087}), so this work represents a natural continuation of this line of research. Finally, this work furthers the knowledge about diamond-free graphs. In 1984, Tucker proved the Strong Perfect Graph Conjecture, now Strong Perfect Graph Theorem, for diamond-free graphs \cite{TUCKER1987313}, and more recently there has been an increased interest regarding the coloring problem and the chromatic number of diamond-free graphs and their subclasses (see, e.g., \cite{BRANDSTADT2012471, DABROWSKI2017410, Karthick:2018:CNP:3238799.3238823, KLOKS2009733}). Diamond-free graphs also played an important role in a recent work of Chudnovsky et al.~\cite{CHUDNOVSKY202045} who proved
that there are exactly $24$ 4-critical $P_6$-free graphs.

\begin{sloppypar}
\paragraph{Our contributions.}

Our study of strong cliques in diamond-free graphs is done from several interrelated points of view.
First, we give an efficiently testable characterization of diamond-free CIS graphs. A vertex $v$ in a graph $G$ is \emph{simplicial} if its closed neighborhood is a clique in $G$. Any such clique will be referred to as a \emph{simplicial clique}.

We say that a graph $G$ is \emph{clique simplicial} if every maximal clique in $G$ is simplicial. The characterization is as follows.
\end{sloppypar}

\begin{restatable}[]{theorem}{thmMain}
\label{thm:main}
Let $G$ be a connected diamond-free graph. Then $G$ is CIS if and only if
$G$ is either clique simplicial, $G\cong K_{m,n}$ for some $m,n\ge 2$, or
$G\cong L(K_{n,n})$ for some $n\ge 3$.
\end{restatable}

Second, we derive several consequences of Theorem~\ref{thm:main}. A graph class $\mathcal{G}$ is said to satisfy the \emph{Erd\H{o}s-Hajnal property} if there exists some $\varepsilon>0$ such that every graph $G\in \mathcal{G}$ has either a clique or a stable set of size at least $|V(G)|^\varepsilon$. The well-known Erd\H{o}s-Hajnal Conjecture~\cite{MR1031262} asks whether for every graph $F$, the class of $F$-free graphs has the Erd\H{o}s-Hajnal property. The conjecture is still open, but it has been confirmed for graphs $F$ with at most $4$ vertices (see, e.g.,~\cite{MR3150572}).
In the case when $F$ is the diamond, a simple argument shows that the inequality holds with $\varepsilon = 1/3$ (see~\cite{MR1425208}), but it is not known whether this value is best possible.
Theorem~\ref{thm:main} implies the following improvement for the diamond-free CIS graphs.

\begin{restatable}[]{theorem}{thmEH}
\label{}
Let $G$ be a diamond-free CIS graph. Then $\alpha(G)\cdot \omega(G) \ge |V(G)|$.
Consequently, $G$ has either a clique or a stable set of size at least $|V(G)|^{1/2}$.
\end{restatable}

\begin{sloppypar}
Next, we develop a linear-time algorithm to test if every edge of a given diamond-free graph is in a simplicial clique. This leads to the following algorithmic consequence of Theorem~\ref{thm:main}.
\end{sloppypar}

\begin{restatable}[]{theorem}{thmRecognition}
\label{thm:diamond-free-recognition}
There is a linear-time algorithm that determines whether a given diamond-free graph $G$ is CIS.
\end{restatable}

Theorem~\ref{thm:diamond-free-recognition} implies a linear-time algorithm for testing if every edge of a given diamond-free graph is contained in a strong clique. Furthermore, as a consequence of Theorem~\ref{thm:diamond-free-recognition} and other results in the literature, we report on the following partial progress on the open question about the complexity of recognizing CIS graphs.

\begin{sloppypar}
\begin{restatable}[]{theorem}{corFfree}
\label{thm:F-free}
For every graph $F$ with at most $4$ vertices, it can be determined in polynomial time whether a given $F$-free graph is CIS.

\end{restatable}
\end{sloppypar}

\begin{sloppypar}
Finally, we complement the above efficient characterizations with hardness results about several problems related to strong cliques when restricted to the class of diamond-free graphs. More specifically, using reductions from the {\sc $3$-Colorability} problem in the class of triangle-free graphs we show the following.
\end{sloppypar}

\begin{sloppypar}
\begin{restatable}[]{theorem}{thmHard}
\label{}
When restricted to the class of diamond-free graphs,
the {\sc Strong Clique}, {\sc Strong Clique Existence}, {\sc Strong Clique Vertex Cover}, and {\sc Strong Clique Partition} problems are {\sf co-NP}-complete, and the {\sc Strong Clique Partition Existence} problem is {\sf co-NP}-hard.
\end{restatable}
\end{sloppypar}

\ifarxiv\else
Due to space restrictions, most proofs are omitted and will appear in the full version of this work.

\fi

\section{Preliminaries}\label{sec:prelim}

We consider only graphs that are finite and undirected. We refer to simple graphs as graphs and to graphs with multiple edges allowed as multigraphs. Let $G=(V,E)$ be a graph with vertex set $V(G)=V$ and edge set $E(G)=E$. For a subset of vertices $X\subseteq V(G)$, we will denote by $G[X]$ the subgraph of $G$ induced by $X$, that is, the graph with vertex set $X$ and edge set $\{\{u,v\}\mid\{u,v\}\in E(G);\; u,v\in X\}$. We denote the complete graph, the path, and the cycle graph of order $n$ by $K_n$, $P_n$, and $C_n$, respectively. The graph $K_3$ will be also referred as a \emph{triangle}. By $K_{m,n}$  we denote the complete bipartite graph with parts of size $m$ and $n$. The fact that a graph $G$ is isomorphic to a graph $H$  will be denoted by $G\cong H$. We say that $G$ is $H$-\emph{free} if no induced subgraph of $G$ is isomorphic to $H$.

The \emph{neighborhood} of a vertex $v$ in a graph $G$, denoted by $N_G(v)$ (or just $N(v)$ if the graph is clear from the context), is the set of vertices adjacent to $v$ in $G$. The cardinality of $N_G(v)$ is the \emph{degree} of $v$ in $G$, denoted by $d_G(v)$ (or simply $d(v)$). The \emph{closed neighborhood}, $N(v)\cup\{v\}$, is denoted by $N[v]$. Given a graph $G$ and a set $X\subseteq V(G)$, we denote by $N_G(X)$ the set of vertices in $V(G)\setminus X$ having a neighbor in $X$. The \emph{line graph} of a graph $G$, denoted with $L(G)$, is the graph with vertex set $E(G)$ and such that two vertices in $L(G)$ are adjacent if and only if their corresponding edges in $G$ have a vertex in common. A \emph{matching} in a graph $G$ is a set of pairwise disjoint edges. A matching is \emph{perfect} if every vertex of the graph is an endpoint of an edge in the matching. Given a graph $G$, we denote by $\alpha(G)$ the maximum size of a stable set in $G$ and by $\omega(G)$ the maximum size of a clique in $G$.

We first recall
a
basic property of CIS graphs (see, e.g.,~\cite{e6c81804d9c9450c946b6f3cece46881}). An induced $P_4$, $(a,b,c,d)$, in a graph $G$ is said to be \emph{settled} (in $G$) if $G$ contains a vertex $v$ adjacent to both $b$ and $c$ and non-adjacent to both $a$ and $d$.

\begin{proposition}\label{prop:CIS-properties}\mbox{}

In every CIS graph each induced $P_4$ is settled.\label{CIS:settled}

\end{proposition}

\ifarxiv
We will also use the following characterization of diamond-free graphs (see, e.g.,~\cite{FELLOWS20112}).

\begin{lemma}\label{lem:maximal-cliques-diamond-free}
A graph $G$ is diamond-free if and only if every edge is in a unique maximal clique.
\end{lemma}
\fi

The following statements are consequences of Lemma~\ref{lem:maximal-cliques-diamond-free}.

\begin{corollary}\label{cor:maximal-cliques-diamond-free}
A diamond-free graph $G= (V,E)$ has at most $|E|$ maximal cliques.
\end{corollary}

\begin{corollary}
\label{vNotInMaxClique}
Let $G$ be a diamond-free graph, let $C$ be a maximal clique in $G$ and let $u\in V(G)\setminus C$.
Then $|N(u)\cap C|\leq 1$.
\end{corollary}

Given a clique $C$ in $G$ and a set $S\subseteq V(G)\setminus C$, we say that clique $C$ is \emph{dominated by $S$} if every vertex of $C$ has a neighbor in $S$. Using this notion, simplicial cliques can be characterized as follows.

\begin{lemma}\label{lem:simplicial-cliques}
A clique $C$ in a graph $G$ is not simplicial if and only $C$ is dominated by $V(G)\setminus C$.
\end{lemma}

\begin{proof}
Note that $C$ is simplicial if and only if there exists a vertex $v\in C$ such that $C = N[v]$.
However, since $C$ is a clique, we have $C\subseteq N[v]$ for all vertices $v\in C$.
It follows that $C$ is simplicial if and only if there exists a vertex $v\in C$ such that $N(v)\subseteq C$. Equivalently,
$C$ is not simplicial if and only every vertex in $C$ has a neighbor outside $C$, that is, $C$ is dominated by $V(G)\setminus C$.
\qed\end{proof}

\begin{sloppypar}
A similar characterization is known for strong cliques (see, e.g., the remarks following~\cite[Theorem 2.3]{HMR2018}).
\end{sloppypar}

\begin{lemma}\label{lem:strong-cliques}
A clique $C$ in a graph $G$ is not strong if and only if it is dominated by a stable set $S \subseteq V(G)\setminus C$.
\end{lemma}

Since every simplicial clique is strong (cf.~Lemmas~\ref{lem:simplicial-cliques} and~\ref{lem:strong-cliques}), we obtain the following.

\begin{fact}\label{obs:clique simplicial}
Every clique simplicial graph is CIS.
\end{fact}

For the algorithmic results in Section~\ref{sec:algo}, we will need the following lemma, which appears as an exercise in~\cite{MR2063679}.

\begin{lemma}\label{lemma:list-sort}
There is a linear-time algorithm that takes as input a multigraph $G = (V,E)$ given by adjacency lists and a linear ordering $\sigma = (v_1,\ldots, v_n)$ of its vertex set, and computes the adjacency lists of $G$ in which the neighbors of each vertex are sorted increasingly with respect to~$\sigma$.
\end{lemma}

\section{A characterization of diamond-free CIS graphs}\label{sec:diamond-free-CIS}

\begin{sloppypar}

We first derive a property of diamond-free graphs in which every induced $P_4$ is settled.
\end{sloppypar}

\begin{restatable}[]{lemma}{EdgeMaxClique}
\label{EdgeMaxClique}
Let $G$ be a connected diamond-free graph in which every induced $P_4$ is settled.
Then, either $G$ is complete bipartite, or

each edge $e\in E(G)$ that is a maximal clique in $G$ is also

a simplicial clique.

\end{restatable}

\begin{proof}
 Suppose that $G$ is not complete bipartite.
 Suppose that there is an edge $uv\in E(G)$ such that $\{u,v\}$ is a non-simplicial maximal clique in $G$. Then, by Lemma~\ref{lem:simplicial-cliques}, $N(v)\setminus\{u\}\neq\emptyset$ and $N(u)\setminus\{v\}\neq\emptyset$. If $x\in N(u)\setminus\{v\}$ and $y\in N(v)\setminus\{u\}$, then $xy\in E(G)$ otherwise the path $(x,u,v,y)$ is a non-settled induced $P_4$ in $G$, which is a contradiction. Moreover, since $G$ is diamond-free, for any two different vertices $x,x'\in N(u)\setminus\{v\}$ and two different vertices $y,y'\in N(v)\setminus\{u\}$ we have $xx',yy'\notin E(G)$. This, together with the fact that $N(u)\cap N(v)=\emptyset$ implies that $N(u)$ and $N(v)$ are stable sets. Then, neither $u$ nor $v$ are contained in a triangle. Hence, $G[N[u]\cup N[v]]$ is complete bipartite.
  Since $G$ is connected and not complete bipartite, we can assume without loss of generality that there is a vertex $w\in V(G)\setminus(N[u]\cup N[v])$ such that $wx\in E(G)$ for some $x\in N(u)\setminus\{v\}$. Then, $(v,u,x,w)$ is a non-settled induced $P_4$ in $G$, a contradiction.
\qed\end{proof}

\begin{sloppypar}
Next, we analyze the global properties of an induced subgraph $H$ in a connected diamond-free CIS graph $G$ such that
$H\cong L(K_{n,n})$ for some $n\geq3$.

\begin{restatable}[]{lemma}{lemgridinCISgraph}
\label{lem:grid-in-CIS-graph}
Let $G$ be a connected diamond-free CIS graph. Suppose that $G$ contains an induced subgraph $H$ such that $H\cong L(K_{n,n})$ for some $n\geq3$. Then, either all the $2n$ copies of $K_n$ in $H$ are maximal cliques in $G$ or none of them is a maximal clique in $G$. Furthermore, if all the $2n$ copies of $K_n$ are maximal cliques in $G$, then $G=H$.
\end{restatable}
\end{sloppypar}

\begin{proof}
Let $V(H)=\{(i,j)\mid 1\leq i\leq j\leq n\}$ and $E(H)=\{(i,j)(k,l)\mid \mbox{either }i=k\;\mbox{ or\; $j=l$},$ $\mbox{but not both}\}$. For each $i\in\{1,\dots,n\}$ let $R_i=\{(i,j)\mid 1\leq j\leq n\}$ and for each
$j\in\{1,\dots,n\}$, let $L_j=\{(i,j)\mid 1\leq i\leq n\}$. Hence, for each $i,j\in\{1,\dots, n\}$, we have $G[R_i]\cong G[L_j]\cong K_n$.
Observe that for any two $i,j\in\{1,\dots,n\}$ we have that $R_i\cap L_j=\{(i,j)\} $. Suppose that there is a copy of $K_n$ in $H$ which is a maximal clique in $G$, without loss of generality let $L_1$ be such a clique.
Now, we show that for each $i\in\{1,\dots,n\}$ we have that $R_i$ is also a maximal clique in $G$. For this, suppose the contrary and let, without loss of generality, $R_1$ be a non-maximal clique in $G$. Consider a maximal clique $R_1'$ in $G$ such that $R_1\subset R_1'$ and let $v\in R'_1\setminus R_1$. Note that $v \notin V(H)$. Observe that for any $i,j\in\{2,\dots,n\}$, if $(i,j)\in N_G(v)$ then $G[\{(1,j-1),(1,j),(i,j), v\}]$ is a diamond, a contradiction. Therefore, for all $j\in\{1,\dots,n\}$ we have $N_G(v)\cap L_j=\{(1,j)\}$, implying that $\{v,(2,2), (3,3),\dots, (n,n)\}$ is a stable set in $G- L_1$ dominating $L_1$, a contradiction by Lemma \ref{lem:strong-cliques}. Therefore, all the cliques $R_i$ are also maximal cliques in $G$. By symmetry, under the same argument, we conclude that for all $j\in\{1,\dots,n\}$ the cliques $L_j$ are also maximal cliques in $G$.

Now, suppose that for all $i,j\in\{1,\dots,n\}$, $R_i$ and $L_j$ are maximal cliques in $G$ and that $G\neq H$. Since $G$ is connected, there exists a vertex $u\in V(H)$ and a vertex $v\in V(G)\setminus V(H)$ such that $uv\in E(G)$. Without loss of generality let $u=(1,1)$. By Corollary~\ref{vNotInMaxClique}, we have that $N_G(v)\cap (R_1\cup L_1)=\{u\}$, and for all $i,j\in\{2,\dots, n\}$ we have $|N_G(v)\cap R_i|\leq1$ and $|N_G(v)\cap L_j|\leq 1$. Let $U=(N_G(v)\cap V(H))$. Hence, $U$ is a stable set in $(H -L_1) -R_1 \cong L(K_{n-1,n-1})$, which corresponds to a matching $M$ in $K_{n-1,n-1}$. By  K\" onig's Theorem \cite{Konig1916}, every $k$-regular bipartite graph has a perfect matching. Hence there exists $U' \subseteq V(H) \setminus (L_1 \cup R_1 \cup U)$, which corresponds to a perfect matching in $K_{n-1,n-1} -M$, implying $U'$ is a stable set in $G$ of size $n-1$. Hence, the set $\{v\} \cup U'$ is a stable set in $G - L_1$ dominating $L_1$, which is a contradiction by Lemma~\ref{lem:strong-cliques}.
\qed\end{proof}

We will also need the following technical lemma about diamond-free graphs.

\begin{restatable}[]{lemma}{lknnstablediagonal}
\label{lknn_stable_diagonal}
Let $G$ be a diamond-free graph. Let $C'=\{v_{1},v_{2},\ldots,v_{\ell}\}$ be a clique in $G$ and let $C_1,\ldots,C_\ell$ be maximal cliques in $G$ such that for every $i\in\{1,\ldots,\ell\}$ we have $C_i \cap C'=\{v_{i}\}$, $2\leq \ell=|C'|\leq |C_i|$ and  $C_i \cap C_j = \emptyset$ for any $j \neq i$. Then,  there exists a stable set $S\subseteq \bigcup_{i=1}^\ell C_i$ in $G-C'$ of size $\ell-1$ such that $|N_G(S)\cap C'|=|S|$. Furthermore, if $\max_{i=1}^\ell |C_i| > \ell$, then there exists a stable set $S\subseteq \bigcup_{i=1}^\ell C_i$ in $G-C'$
such that $|S| = \ell$ and $S$ dominates $C'$.
\end{restatable}

\begin{proof}
Without loss of generality let $|C_1| \leq |C_2| \leq \ldots \leq |C_{\ell}|$.
By Corollary~\ref{vNotInMaxClique} for any $i,j\in\{1,\ldots,\ell\}$ with $j\neq i$, each vertex from $C_i\setminus C'$ is adjacent to at most one other vertex in $C_j\setminus C'$.
Let $S_0=\emptyset$ be our starting stable set that we are going to build up.
In the $j$-th step ($1\leq j<\ell $), since $|(C_j\setminus C') \cap N_G(S_{j-1})| \leq |S_{j-1}|=j-1<\ell-1\leq|C_j|-1$, there is a vertex $u_j\in C_j\setminus C'$ such that $N_G(S_{j-1})\cap\{u_j\}=\emptyset$. Let $S_j=S_{j-1} \cup \{u_j\}$. Hence, $S_j\subseteq \bigcup_{i=1}^j C_i$ is a stable set in $G-C'$ of size $j$ dominating $\{v_1,\dots,v_j\}$. If $|C_{\ell}|=\ell$, then $S_{\ell-1}\subseteq \bigcup_{i=1}^{\ell-1} C_i$ is a stable set in $G-C'$ of size $\ell-1$ dominating $\{v_1,\dots,v_{\ell-1}\}$ and such that $|N_G(S_{\ell-1})\cap C'|=|S_{\ell-1}|$.
If $|C_{\ell}|>\ell$, then $|(C_\ell\setminus C') \cap N_G(S_{\ell-1})| \leq |S_{\ell-1}|=\ell-1 <|C_\ell|-1$, implying that there is a vertex $u_\ell\in(C_\ell\setminus C')$ such that $N_G(S_{\ell-1})\cap\{u_\ell\}=\emptyset$. Let $S_\ell=S_{\ell-1} \cup \{u_\ell\}$.
Hence, $S_\ell$ is a stable set of size $\ell$ in $G-C'$ dominating $C'$.
\qed\end{proof}

We can now characterize the connected diamond-free CIS graphs. The result shows that, apart from the clique simplicial diamond-free graphs, there are only two highly structured infinite families of connected diamond-free CIS graphs.

\thmMain*

\begin{proof}
Each of the three conditions is sufficient for $G$ to be CIS. Complete bipartite graphs are $P_4$-free, and every $P_4$-free graph is CIS (see~\cite{MR818265}). Graphs of the form $L(K_{n,n})$ are also CIS
(see, e.g.,~\cite[Proposition 3.3]{MR3278773}). By Fact~\ref{obs:clique simplicial}, every clique simplicial graph is CIS.

To prove that there are no other connected diamond-free CIS graphs, let $G$ be a connected diamond-free CIS graph such that $G$ is not clique simplicial, $G\ncong K_{m,n}$ (with $m,n\geq2$), and $G\ncong L(K_{n,n})$ (with $n\geq3$). Among all maximal non-simplicial cliques in $G$, pick one with the smallest size and name it $C$. Observe that, by Proposition~\ref{prop:CIS-properties} and Lemma~\ref{EdgeMaxClique}, $k\geq3$. Let $C=\{v_{1},\ldots,v_{k}\}$. For each vertex $v_{i}\in C$ fix a maximal clique $C_i$ containing $v_{i}$ such that $C_i\neq C$, and let $A_i=C_i\setminus\{v_{i}\}$. Hence, for each $i\in\{1,\dots,k\}$ we have $A_i\neq\emptyset$.
 Let $H$ be the subgraph of $G$ induced by $\bigcup_{j=1}^kC_j$. Note that for all $i$, if $C_i$ is simplicial in $H$, then $C_i=N_H(x_i)$ for some $x_i\in A_i$. Let $\ell$ denote the number of cliques among all $C_i$'s such that $|C_i|\geq k$. Without loss of generality let $C_1,\ldots,C_\ell$ be  such that $k\leq|C_1|\leq\ldots\leq|C_\ell|$. Then, by minimality of $C$, for every $\ell<i\leq k$ we have $C_i$ is a simplicial clique in $G$. For each $\ell<i\leq k$ let $u_i\in C_i$ be a simplicial vertex in $G$, hence $u_i\in A_i$.
 If $\ell=0$, then $S=\{u_i\mid 1\leq i\leq k\}$ is a stable set in $G-C$ dominating $C$, implying by Lemma~\ref{lem:strong-cliques} that $C$ is not strong, a contradiction. If $\ell=1$ then, $S=\{u_i\mid 2\leq i\leq k\}\cup\{u\}$ is a stable set in $G-C$ dominating $C$, for any $u\in A_1$, a contradiction.
 Hence, $\ell\geq2$.
 Let $C'=\{v_{1},v_{2},\dots,v_{\ell}\}$. Then, the cliques $C',C_1,\dots, C_\ell$ satisfy the hypothesis of Lemma~\ref{lknn_stable_diagonal}. Hence, if $\ell<k$, there is a stable set $S\subseteq\bigcup_{i=1}^{\ell}A_i$ in $G-C'$ dominating $C'$. Hence, $S\cup\{u_{\ell+1},\dots, u_k\}$ is a stable set in $G-C$ dominating $C$, a contradiction. Therefore, $\ell=k$. Moreover, if $|C_k|>k$ by Lemma~\ref{lknn_stable_diagonal} we have a stable set in $G-C$ of size $k$ dominating $C$, a contradiction. Hence, $|C_k|=k$ implying that $|C_i|=k$ for any $i\in\{1,\dots,k\}$.

Suppose there exist a vertex $v \in A_i$, $i \in \{1,\ldots,k\}$ with $N_H(v) \cap A_j=\emptyset$ for some $j \in \{1,\ldots,k\} \setminus \{i\}$. Without loss of generality let $i=1$ and $j=k$. Apply Lemma \ref{lknn_stable_diagonal} to the first $k-1$ $C_i$'s to construct a stable set $S\subseteq\left(\bigcup_{i=2}^{k-1}A_i\right)\cup\{v\}$ in $G-C$ of size $k-1$ in such a way that $S_1=\{v\}$, that is, $v$ is the first vertex selected in the construction of the stable set $S$. This way we get a stable $S$ disjoint from $A_k$. Moreover, by Corollary~\ref{vNotInMaxClique} and since $N_G(v) \cap A_k = \emptyset$ we have $|N_H(S) \cap A_j|\leq |S|-1=(k-1)-1=k-2$. This implies there exists a vertex $u \in A_j $ disjoint from $S$ that is not adjacent to $S$. Hence $S\cup\{u\}$ is a stable set in $G-C$ of size $k$ that dominates $C$, a contradiction.

Therefore, for each $i\in\{1,\dots,k\}$ and any vertex $v\in A_i$ we have $|N_H(v)\cap A_j|=1$ for any $j \in \{1,\ldots,k\} \setminus \{i\}$. Observe that if for any $i\in\{1,\dots,k\}$ and any $x\in A_i$ we have $N_G(x)\cap\left(\bigcup_{j\neq i}A_j\right)\cong K_{k-1}$, then $H\cong L(K_{k,k})$ implying, by Lemma~ \ref{lem:grid-in-CIS-graph}, that $G\cong L(K_{k,k})$, a contradiction.
Hence, there are three different numbers $i,j,j'\in\{1,\dots,k\}$  and three vertices $u,v,w$ such that $u\in A_i$, $v\in A_j$, $w\in A_{j'}$, $u,v\in N(w)$ and $uw\notin E(G)$.
By symmetry, let us assume that $i=1$, $j=2$ and $j'=k$. Use the proof of Lemma \ref{lknn_stable_diagonal} to generate a stable set $S$ of size $k-1$ in such a way that $S_1=\{u\}$, $S_2=\{u,v\}$ and $S_{k-1}\subseteq\bigcup _{i'=1}^{k-1}A_{i'}$.
Since $N_G(\{u,v\}) \cap A_k=\{w\}$ we must have $|N_G(S_{k-1}) \cap A_k|\leq |S_{k-1}|-1=(k-1)-1=k-2$. This implies that there exist a vertex $v' \in A_k$ that is not adjacent to $S_{k-1}$. Hence, $S_{k-1} \cup \{v'\}$ is a stable set in $G-C$ dominating $C$, a contradiction.
\qed\end{proof}

\section{Consequences}
\label{sec:consequences}

We now discuss several consequences of Theorem~\ref{thm:main}.

\subsection{Large cliques or stable sets in diamond-free CIS graphs}\label{sec:EH}

Recall that every diamond-free graph $G$ has either a clique or a stable set of size at least
$|V(G)|^{1/3}$. For diamond-free CIS graphs, Theorem~\ref{thm:main} leads to an improvement of the exponent to $1/2$.

\begin{restatable}[]{lemma}{lemcliquesimplicialalphaomega}
\label{lem:clique simplicial-alpha-omega}
Let $G$ be a clique simplicial graph. Then $\alpha(G)\cdot \omega(G) \ge |V(G)|$.
\end{restatable}

\begin{proof}
Let $C_1,\ldots, C_k$ be all the maximal cliques of $G$. Since $G$ is clique simplicial, each $C_i$ is a simplicial clique. Selecting one simplicial vertex from each $C_i$ gives a stable set $S$ of size $k$, and
since every vertex is in some simplicial clique, we infer that $|V(G)|\le \sum_{i = 1}^k|C_i|\le |S|\cdot \omega(G) \le \alpha(G)\cdot \omega(G)$.
\qed\end{proof}

\thmEH*

\begin{proof}
First we show that it suffices to prove the statement for connected graphs. Let $G$ be a disconnected diamond-free CIS graph, let $C$ be a component of $G$ and let $G' = G-V(C)$. Then $C$ and $G'$ are diamond-free CIS graphs,
and by induction on the number of components we may assume that
$\alpha(C)\cdot \omega(C) \ge |V(C)|$ and $\alpha(G')\cdot \omega(G') \ge |V(G')|$.
Since  $\alpha(G) = \alpha(C)+\alpha(G')$ and $\omega(G) = \max\{\omega(C),\omega(G')\}$,
we obtain $|V(G)| = |V(C)|+|V(G')|\le \alpha(C)\cdot \omega(G)+ \alpha(G')\cdot \omega(G) = \alpha(G)\cdot \omega(G)$.

Now let $G$ be a connected diamond-free CIS graph. By Theorem~\ref{thm:main}, $G$ is either clique simplicial, $G\cong K_{m,n}$ for some $m,n\ge 2$, or $G\cong L(K_{n,n})$ for some $n\ge 3$. If $G$ is clique simplicial, then Lemma~\ref{lem:clique simplicial-alpha-omega} yields $|V(G)|\le \alpha(G)\cdot \omega(G)$. If $G\cong K_{m,n}$ for some $m,n\ge 2$, then $|V(G)| = m+n\le 2\cdot\max\{m,n\} = \omega(G)\cdot \alpha(G)$. Finally, if $G\cong L(K_{n,n})$, then $\alpha(G)$ equals the maximum size of a matching in $K_{n,n}$, that is, $\alpha(G) = n$,
and $\omega(G)$ equals the maximum degree of a vertex in $K_{n,n}$, that is, $\omega(G) = n$.
Thus, in this case equality holds, $|V(G)| = n^2 = \alpha(G)\cdot \omega(G)$.
\qed\end{proof}

\subsection{Testing the CIS property in the class of diamond-free graphs}\label{sec:algo}

\begin{sloppypar}
Our next consequence is a linear-time algorithm for testing the CIS property in the class of diamond-free graphs.
The bottleneck to achieve linearity is the recognition of the clique simplicial property.
Instead of checking this property directly, we check whether the graph is \emph{edge simplicial}, that is, every edge is contained in a simplicial clique.
Clearly, every clique simplicial graph is edge simplicial.
While the converse implication fails in general, the two properties are equivalent in the case of diamond-free graphs, where every edge is in a unique maximal clique
\ifarxiv
(cf.~Lemma~\ref{lem:maximal-cliques-diamond-free})
\fi
.
\end{sloppypar}

\ifarxiv
\begin{fact}\label{obs:cs-es}
A diamond-free graph is clique simplicial if and only if it is edge simplicial.
\end{fact}
\fi

Recognizing if a general graph $G = (V,E)$ is edge simplicial can be done in time $\O(|V|\cdot|E|)$ (see~\cite{MR2302164,MR727924}).
The algorithm is based on the observation that within a simplicial clique, every vertex of minimum degree is a simplicial vertex (see~\cite{MR992923}). We show that in the case of diamond-free graphs, the running time can be improved to $\O(|V|+|E|)$.

\ifarxiv
To describe the algorithm, we need to introduce some terminology.
\fi
Given a graph $G$ and a linear ordering $\sigma=(v_1,\ldots, v_n)$ of its vertices, the $\sigma$\textit{-greedy stable set} is the stable set $S$ in $G$ computed by repeatedly adding to the initially empty set $S$ the smallest $\sigma$-indexed vertex as long as the resulting set is still stable. A \textit{degree-greedy stable set} is any $\sigma$-greedy stable set where $\sigma=(v_1,\ldots, v_n)$ satisfies $d(v_i)\leq d(v_j)$ for $i<j$. Note that a degree-greedy stable set does not need to coincide with a stable set computed by the greedy algorithm that iteratively selects a minimum degree vertex and deletes the vertex and all its neighbors: to compute a degree-greedy stable set, the vertex degrees are only considered in the original graph $G$, and not in the subgraphs obtained by deleting the already selected vertices and their neighbors.

Our first lemma analyzes the structure of a degree-greedy stable set in a graph in which the simplicial cliques cover all the vertices. In particular, it applies to edge simplicial graphs.

\begin{restatable}[]{lemma}{lemS}
\label{lem:S}
Let $G$ be a graph in which every vertex belongs to a simplicial clique and let $S$ be a degree-greedy stable set in $G$.
Then, $S$ consists of simplicial vertices only, one from each simplicial clique.

\end{restatable}

\begin{proof}
Let $\sigma=(v_1,\ldots, v_n)$ be a linear ordering of $V(G)$ with  $d(v_i)\leq d(v_j)$ if $i<j$ and such that $S$ is the $\sigma$-greedy stable set. Let $C$ be a simplicial clique in $G$ and let $v_i$ be the simplicial vertex in $C$ with the smallest index.
Then, all neighbors of $v_i$ have indices larger than $i$ and therefore $v_i$ is selected to be in $S$.
This shows that $S$ contains a vertex from $C$. Clearly, $S$ cannot contain two vertices from $C$ since $S$
is stable and $C$ is a clique. Thus, $S$ contains exactly one vertex from every simplicial clique in $G$.
Finally, suppose that $S$ contains some non-simplicial vertex $v$. By assumption on $G$, vertex $v$ belongs to some simplicial clique $C$. Let $w$ be the vertex from $C$ contained in $S$. Then $w$ is simplicial and thus $w\neq v$. This means that $S$ contains two adjacent vertices $v$ and $w$, which is in contradiction with the fact that $S$ is a stable set. Thus, every vertex in $S$ is simplicial.
\qed\end{proof}

Using Lemma~\ref{lem:S} we now show the importance of degree-greedy stable sets for testing if a given diamond-free graph is edge simplicial. The characterization is based on the following auxiliary construction. Given a graph $G=(V,E)$ and a stable set $S$ in $G$, we define the multigraph $G_S$ where $V(G_S)=V\setminus S$ and the multiset of edges is given by $$E(G_S)=\bigcup_{v\in S}\{xy\mid x\neq y \text{ and } x,y \in N_G(v)\}\,.$$
Note that since $S$ is a stable set in $G$, every edge in $E(G_S)$ indeed has both endpoints in $V\setminus S = V(G_S)$.

\begin{restatable}[]{lemma}{lemmaGSGS}
\label{lemma:G-S=G_S}
Let $S$ be a degree-greedy stable set in a diamond-free graph $G$. Then $G$ is edge simplicial if and only if $G_S=G-S$.
\end{restatable}

\begin{proof}
Suppose $G$ is edge simplicial. Each edge is therefore part of at least one simplicial clique and, since $G$ is diamond-free, each edge is in fact in exactly one simplicial clique. By Lemma~\ref{lem:S}, $S$ consists of simplicial vertices only, one from each simplicial clique. We need to show that the multigraphs $G_S$ and $G-S$ are equal.
The vertex sets $V(G_S)$ and $V(G-S)$ are equal by definition.
Since $G$ is a simple graph, so is $G-S$. Suppose that $G_S$ has a duplicate edge $xy$. Then there must exist two distinct vertices $v_1,v_2 \in S$ such that $\{v_1x,v_1y,v_2x,v_2y\} \subseteq E(G)$. Since $S$ is a stable set we have $v_1v_2\not\in E(G)$ and since $v_1$ is a simplicial vertex in $G$, vertices $x$ and $y$ are adjacent in $G$. But now $G$ contains an induced diamond on the vertices
$\{v_1,v_2,x,y\}$, a contradiction. Thus, $G_S$ is a simple graph.
Consider an edge $xy \in E(G-S)$. Since $G$ is edge simplicial, Lemma~\ref{lem:S} implies the existence of a vertex $v\in S$ such that $\{x,y,v\}$ is a clique in $G$, implying that $x,y\in N_G(v)$ and thus $xy\in E(G_S)$. Therefore $E(G-S)\subseteq E(G_S)$. Consider now an edge $xy\in E(G_S)$. By the definition of $G_S$, there exists a vertex $v\in S$ such that $\{x,y\}\subseteq N_G(v)$. Since $v\in S$, vertex $v$ is simplicial in $G$ and hence $xy\in E(G-S)$. Therefore $E(G-S)\supseteq E(G_S)$ and $G-S=G_S$.

Now we show the reverse implication by contraposition. Suppose that $G$ is not edge simplicial. Then there exists an edge $xy\in E(G)$ that is not contained in any simplicial clique of $G$. In particular, since every vertex in $S$ is simplicial in $G$, vertices $x$ and $y$ cannot belong to $S$. Thus $xy\in E(G-S)$. Furthermore, there does not exist a vertex $s \in S$ such that $x,y \in N_G(s)$. Hence the edge $xy$ is not in $E(G_S)$ but it is in $E(G-S)$. It follows that $G_S\neq G-S$.
\qed\end{proof}

The condition given by Lemma~\ref{lemma:G-S=G_S} can be tested in linear time
\ifarxiv
.
\else
, see Algorithm~\ref{alg:DFESR2}. Together with Theorem~\ref{thm:main}, this leads to the following.

\thmRecognition*
\fi

\ifarxiv
\begin{restatable}[]{proposition}{propdiamondfreerecognition}
\label{prop:diamond-free-recognition2}

Algorithm~\ref{alg:DFESR2} runs in time $\mathcal{O}(|V|+|E|)$ and correctly determines whether a given diamond-free graph $G=(V,E)$ is edge simplicial.
\end{restatable}
\fi

\begin{algorithm}[!h]
\caption{Diamond-Free Edge Simplicial Recognition}\label{alg:DFESR2}
 \hspace*{\algorithmicindent} \textbf{Input:} A diamond-free graph $G$ given by adjacency lists $(L_v:v\in V(G))$.\\% of the vertices $v \in V$.\\
 \hspace*{\algorithmicindent} \textbf{Output:} ``Yes'' if $G$ is edge simplicial, ``No'' otherwise.
\begin{algorithmic}[1]
 \State compute a linear order $\sigma = (v_1,\ldots, v_n)$ of the vertices of $G$ such that \hbox{ $d(v_1)\leq \ldots \leq d(v_n)$};
 \State sort the adjacency list of each vertex in increasing order with respect to $\sigma$;
 \State set $S = \emptyset$, all the vertices are unmarked;
 \For{$i=1,\ldots, n$}
     \If {$v_i$ is not marked}
         \State mark all vertices in $N(v_i)$, $S=S\cup\{v_i\}$;
     \EndIf
 \EndFor
 \State compute the adjacency lists $L^-_w$ of $G-S$ based on the order of $V\setminus S$ induced by $\sigma$;
 \If {$\sum_{v \in S}{d(v)+1 \choose 2}>|E(G)|$}
     \State \Return ``No'';
 \EndIf
 \For{$w \in V\setminus S$}
     \State $L'_w=\text{empty list}$;
 \EndFor
 \For{$v \in S$}
     \For{$w \in N_G(v)$}
         \State append each element of $N_G(v)\setminus\{w\}$ at the end of $L'_w$;
     \EndFor
 \EndFor
 \For{$w \in V\setminus S$}
 		\If{$\text{length}(L'_w)\neq \text{length}(L^-_w)$}
 				\State \Return  ``No'';
 		\EndIf
 \EndFor

 \State sort the adjacency lists $L'_w$ based on the linear order of $V\setminus S$ induced by $\sigma$;
 \For{$w \in V\setminus S$}
		 \If{$L'_w\neq L^-_w$}
 				\State \Return  ``No'';
		 \EndIf
 \EndFor
 \State \Return ``Yes'';
 \end{algorithmic}
 \end{algorithm}
\ifarxiv

\begin{proof}
Let us first describe the algorithm informally. In lines 1--6, Algorithm~\ref{alg:DFESR2} computes a degree-greedy stable set $S$ of $G$.
In line 7, it computes the adjacency lists $L_w^-$ of the graph $G-S$.
In lines 8--9 it checks that a necessary condition for $G$ to be edge simplicial holds. (This check is only needed to achieve a linear running time.) In lines 10--14, the algorithm computes the adjacency lists $L_w'$ of the multigraph $G_S$.
Finally, in lines 15--21, the algorithm tests if $G_S = G-S$.

\begin{sloppypar}
We prove that the algorithm is correct by analyzing each of the possible outcomes.
Suppose first that the algorithm returned ``No'' at line 9. Then $\sum_{v\in S}{d(v)+1 \choose 2} > |E(G)|$. Suppose for a contradiction that $G$ is edge simplicial. By Lemma~\ref{lem:S}, $S$ consists of simplicial vertices only, one from each simplicial clique. Since $G$ is diamond-free, Lemma~\ref{lem:maximal-cliques-diamond-free} implies that every edge is in a unique maximal clique. Thus, for two different vertices $v,w\in S$, the cliques $N[v]$ and $N[w]$ are edge-disjoint. In particular, this implies that the value of $\sum_{v \in S}{d(v)+1 \choose 2}$, which counts the total number of edges
in these simplicial cliques, cannot exceed $|E(G)|$.
Hence, if $\sum_{v \in S}{d(v)+1 \choose 2} > |E(G)|$, then $G$ is indeed not edge simplicial.
Suppose next that the algorithm returned ``No'' at line 17 or 21. Then, the graphs $G_S$ and $G-S$ are not the same and by Lemma~\ref{lemma:G-S=G_S}, we can say that $G$ is not edge simplicial.
Finally, if the algorithm returns ``Yes'', then $G_S = G-S$ and thus $G$ is edge simplicial
by Lemma~\ref{lemma:G-S=G_S}.
\end{sloppypar}

Next we analyze the time complexity of the algorithm. We denote by $m$ the number of edges of $G$. Sorting the vertices with respect to their degrees in line 1 can be done in time $\O(n+m)$ using counting sort.
A further sorting of the adjacency lists in line 2 can be done in $\O(n+m)$ using Lemma \ref{lemma:list-sort}.
Line 3 takes $\O(n)$ time.
Lines 4--6 take altogether $\O(n+m)$ time. Line 7 takes $\O(n+m)$ time.
Lines 8--9 take $\O(|S|) = \O(n)$ time.
Lines 10--11 take $\O(n)$ time.
Lines 12--14 take time proportional to $\sum_{v\in S}(d(v)(d(v)-1)) \le 2\cdot \sum_{v\in S}{d(v)+1\choose 2}$, which is in $\O(m)$ since otherwise the algorithm would have returned ``No'' at line 9.
Lines 15--17 take $\O(n)$ time.
Since the algorithm performs line 18 only if
$\text{length}(L'_w) = \text{length}(L^-_w)$ for all $w\in V\setminus S$,
sorting of the adjacency lists in line 18 can be done using Lemma \ref{lemma:list-sort}
in time proportional to
$\O(n+\sum_{w\in V\setminus S}|L'_w|) =
\O(n+\sum_{w\in V\setminus S}|L^-_w|) = \O(n+m)$.
Similarly, the time needed to perform a check in line 20 is bounded by $\O(d_{G-S}(w)) = \O(d_G(w))$ for each iteration,
hence the total time needed for lines 19--21 is again $\O(n+m)$. Line 22 takes $\O(1)$ time.
We conclude that altogether, the algorithm runs in linear time.
\qed\end{proof}

\fi

\ifarxiv
Theorem~\ref{thm:main}, Fact~\ref{obs:cs-es}, and

Proposition~\ref{prop:diamond-free-recognition2}
imply the following.

\thmRecognition*
\fi

\begin{proof}
Let $G=(V,E)$ be a diamond-free graph. Since a graph is CIS if and only if all of its components are CIS (see, e.g.,~\cite{e6c81804d9c9450c946b6f3cece46881}),

we may assume that $G$ is connected.

By Theorem~\ref{thm:main}, it suffices to check if $G$ is isomorphic to either $K_{m,n}$ for some $m,n\ge 2$, or $L(K_{n,n})$ for some $n\ge 3$, or if $G$ is clique simplicial. We can check if $G$ is a complete bipartite graph in linear time as follows. We run breadth-first search from any fixed vertex $v$ to test if $G$ is bipartite and to compute the sets $X$ and $Y$ of vertices at distance one and two from $v$, respectively. Assuming $G$ is bipartite, we only need to check if $|V| = 1+|X|+|Y|$, and verify that the vertex degrees are what they should be (namely, $d_G(x) = |Y|+1$ for all $x\in X$ and $d_G(y) = |X|$ for all $y\in Y$).

To check if $G$ is isomorphic to the line graph of $K_{n,n}$ for some $n\ge 3$, we can first check in linear time whether $G$ is a line graph, using the algorithm of Roussopoulos~\cite{MR0424435}  or Lehot~\cite{MR0347690}. If $G$ is indeed a line graph, the algorithm will also compute a graph $H$ such that $G = L(H)$. As shown by Whitney~\cite{MR1506881}, if such a graph $H$ exists, then $H$ is unique, provided that $G$ is connected and has at least four vertices (which we may assume). It remains to check if $H\cong K_{n,n}$ for some $n\ge 3$, which can also be done in linear time, as explained above.

Finally, to check if $G$ is clique simplicial in linear time, we use Proposition~\ref{prop:diamond-free-recognition2} and Fact~\ref{obs:cs-es}.

\qed\end{proof}

A graph $G=(V,E)$ is \emph{general partition} if there exists a set $U$ and an assignment of vertices $x\in V$ to sets $U_x\subseteq U$ such that $xy\in E$ if and only if $U_x\cap U_y \neq\emptyset$ and for each maximal stable set $S$ in $G$, the sets $U_x$, $x\in S$ form a partition of $U$.
It is known that $G$ is a general partition graph if and only if every edge of $G$ is contained in a strong clique (see~\cite{MR1212874}).
Clearly, every CIS graph is a general partition graph, and the two properties are equivalent in the class of diamond-free graphs.

Therefore, Theorem~\ref{thm:diamond-free-recognition} implies the following.

\begin{corollary}
There is a linear-time algorithm that determines whether every edge of a given diamond-free graph $G$ is in a strong clique.
\end{corollary}

\subsection{Testing the CIS property in classes of $F$-free graphs}\label{sec:F-free}

\begin{sloppypar}
No good characterization or recognition algorithm for CIS graphs is known. Recognizing CIS graphs is believed to be {\sf co-NP}-complete~\cite{MR1344757}, conjectured to be {\sf co-NP}-complete~\cite{MR2234986}, and conjectured to be polynomial~\cite{e6c81804d9c9450c946b6f3cece46881}. Using Theorem~\ref{thm:diamond-free-recognition} together with some known results from the literature (on strong cliques, resp.~CIS graphs~\cite{HMR2018,alcon2019characterization,e6c81804d9c9450c946b6f3cece46881} along with~\cite{alekseev1991number,MR984569,MR1405872,MR476582}) implies

that the CIS property can be recognized in polynomial time in any class of $F$-free graphs where $F$ has at most $4$ vertices.
\end{sloppypar}

\corFfree*

\begin{sloppypar}

\begin{proof}
Let $F$ be a graph with at most $4$ vertices. Clearly, it suffices to consider the case when $F$ has exactly four vertices. Furthermore,
since a graph is CIS if and only if its complement is CIS

, if there is a polynomial-time algorithm to determine whether a given $F$-free graph is CIS, then there is also a polynomial-time algorithm to determine whether a given $\overline{F}$-free graph is CIS.
Thus, since there are $11$ graphs with $4$ vertices, $5$ pairs of complementary graphs $\{F$, $\overline{F}\}$, and one self-complementary graph, the $P_4$, we consider $6$ cases.

First, consider the case when $F\in \{K_4$, $\overline{K_4}\}$. If $G$ is a $K_4$-free graph, then $G$ has $\O(|V(G)|^3)$ maximal cliques, and hence one can test if $G$ is CIS simply by enumerating all the maximal cliques and testing, for each of them, if it is strong. By Lemma~\ref{lem:strong-cliques}, a clique $C$ in a graph $G$ is strong if and only if there is no stable set $S \subseteq V(G)\setminus C$ such that $|S|\le |C|$ and every vertex in $C$ has a neighbor in $S$. Since we only need to check this for cliques of constant size, we obtain a polynomial-time algorithm.

Second, suppose that $F$ is the diamond or its complement. In this case, Theorem~\ref{thm:diamond-free-recognition} applies.

Third, suppose that $F$ is the $C_4$ or its complement. A clique in a $C_4$-free graph is strong if and only if it is simplicial (see~\cite{HMR2018}), and hence a $C_4$-free graph is CIS if and only if it is clique simplicial. Every $C_4$-free graph $G$ has at most $\O(|V(G)|^2)$ maximal cliques (see~\cite{alekseev1991number,MR984569,MR1405872}, and they can be enumerated in polynomial time (e.g., by applying the algorithm of Tsukiyama et al.~\cite{MR476582} to the complement of $G$). Thus, we can test
in polynomial time if a given $C_4$-free graph is CIS by enumerating its maximal cliques and checking if they are all simplicial.

Fourth, suppose that $F$ is the paw (that is, a graph obtained from $K_3$ by adding to it a new vertex of degree $1$) or its complement.
By Proposition~\ref{prop:CIS-properties}, in every CIS graph each induced $P_4$ is settled. Thus, if a CIS graph $P_4$,  $(a,b,c,d)$, then it also contains an induced paw, on the vertex set $\{a,b,c,v\}$, where $v$ is any vertex that settles the $P_4$ (that is, $v$ is adjacent to both $b$ and $c$ and non-adjacent to both $a$ and $d$). It follows that a paw-free graph is CIS if and only if it is $P_4$-free. A polynomial-time recognition algorithm to determine whether a given paw-free graph is CIS follows.

Fifth, suppose that $F$ is the claw (that is, the complete bipartite graph $K_{1,3}$) or its complement.
A polynomial-time algorithm for recognizing claw-free CIS graphs was given in~\cite{alcon2019characterization}.

Finally, suppose that $F$ is the $P_4$. In this case, the recognition algorithm is trivial, since every $P_4$-free graph is CIS (see, e.g.,\cite{e6c81804d9c9450c946b6f3cece46881}).
\qed\end{proof}
\end{sloppypar}

\section{Hardness results}\label{sec:hardness}

\begin{sloppypar}
We consider five more decision problems related to strong cliques: {\sc Strong Clique}, {\sc Strong Clique Existence}, {\sc Strong Clique Vertex Cover}, {\sc Strong Clique Partition}, and {\sc Strong Clique Partition Existence} (see Section~\ref{sec:intro} for definitions). These problems were studied by Hujdurovi\'c et al.~in~\cite{HUJDUROVIC20192738}, who determined the computational complexity of these problems in the classes of chordal graphs, weakly chordal graphs, line graphs and their complements, and graphs of maximum degree at most three.
\end{sloppypar}

\begin{sloppypar}
In contrast with the problems of verifying whether every maximal clique is strong, or whether every edge is in a strong clique, we prove that all the above five problems are {\sf co-NP}-hard in the class of diamond-free graphs.
The hardness proofs are obtained using a reduction from the {\sc $3$-Colorability} problem in the class of triangle-free graphs:
Given a triangle-free graph $G$, can $V(G)$ be partitioned into three stable sets?
As shown by Kami\'{n}ski and Lozin in~\cite{MR2291884}, this problem is {\sf NP}-complete.
Furthermore, it is clear that the problem remains {\sf NP}-complete if we additionally assume that the input graph has at least five vertices and minimum degree at least three. Let $\mathcal{G}$ denote the class of all triangle-free graphs with at least five vertices and minimum degree at least $3$.
\end{sloppypar}

\begin{theorem}\label{thm:3-col}
The {\sc $3$-Colorability} problem is {\sf NP}-complete in the class $\mathcal{G}$.
\end{theorem}

The reductions are based on the following construction. Given a graph $G\in \mathcal{G}$, we associate to it two diamond-free graphs $G'$ and $G''$, defined as follows. The vertex set of $G'$ is $V(G)\times\{0,1,2,3\}$.
For every $v\in V(G)$, the set of vertices of $G'$ with value $v$ in the first coordinate forms a clique (of size $4$); we will refer to this clique as $C_v$. The set of vertices of $G'$ with value $0$ in the second coordinate forms a clique $C$ (of size $|V(G)|$).
For every $i\in \{1,2,3\}$ and every two distinct vertices $u,v\in V(G)$, vertices $(u,i)$ and $(v,i)$ are adjacent in $G'$ if and only if $u$ and $v$ are adjacent in $G$. There are no other edges in $G'$. The graph $G''$ is obtained from the graph $G'$ by adding, for each vertex $w\in V(G')\setminus C$, a new vertex $w'$ adjacent only to $w$. See Figure~\ref{fig:reduction} for an example.

\begin{figure}[h]
  \centering
  \includegraphics[width=\linewidth]{reductionK33.pdf}
  \caption{Transforming $G$ into $G'$ and $G''$.}
  \label{fig:reduction}
\end{figure}

\begin{restatable}[]{proposition}{propreductions}\label{prop:reductions}
Let $G\in \mathcal{G}$ and let $G'$ and $G''$ be the graphs constructed from $G$ as described above.
Then, $G'$ and $G''$ are diamond-free and the following statements are equivalent.
\begin{enumerate}
  \item $G$ is not $3$-colorable.
  \item $C$ is a strong clique in $G'$.
  \item $G'$ has a strong clique.
  \item $C$ is a strong clique in $G''$.
  \item Every vertex of $G''$ is contained in a strong clique.
  \item Every clique from the following collection of cliques in $G''$ is strong: $$\{C\}\cup \{\{w,w'\}\mid w\in V(G')\setminus C\}\,.$$
  \item The vertex set of $G''$ can be partitioned into strong cliques.
\end{enumerate}
\end{restatable}

\begin{proof}
First we show that $G'$ is diamond-free, or, equivalently, that every edge of $G'$ is in a unique maximal clique (Lemma \ref{lem:maximal-cliques-diamond-free}). Consider an edge $e$ of $G'$ and let $(u,i)$ and $(v,j)$ be its endpoints. Then either $u = v$ or $i = j$. If $u = v$, then $C_u$ is the only maximal clique of $G'$ containing
$e$. If $i = j = 0$, then $C$ is the only maximal clique of $G'$ containing $e$. If $i = j \in \{1,2,3\}$, then $uv\in E(G)$ and since $G$ is triangle-free, $e$ itself is a maximal clique in $G'$.
We infer that $G'$ is diamond-free. Similarly, it can be seen that $G''$, too, is diamond-free.

We now prove the implication $1\Rightarrow 2$. Suppose that $C$ is not strong in $G'$. Then, by Lemma \ref{lem:strong-cliques}, there is a stable set $S'\subseteq V(G')\setminus C$ dominating $C$. Since $S'$ dominates $C$, for each $v\in V(G)$ there exists some $i\in \{1,2,3\}$ such that $(v,i)\in S'$. Furthermore, since the set of all vertices in $G'$ having the same first coordinate is a clique and $S'$ is a stable set in $G'$, we infer that $S'$ cannot contain two vertices with the same first coordinate. This means that for each $v\in V(G)$ there is a unique $i\in \{1,2,3\}$ such that $(v,i)\in S'$. For each $i\in \{1,2,3\}$, let $S_i=\{v\in V(G)\mid (v,i)\in S'\}$.
By the construction of $G'$, each $S_i$ is a stable set in $G$.
Moreover, due to the above uniqueness property, $\{S_1,S_2,S_3\}$ is a partition of $V(G)$ into three stable sets, implying that $G$ is 3-colorable.

Next we prove the implication $2\Rightarrow 1$. Suppose that $G$ is $3$-colorable and let $\{S_1,S_2,S_3\}$ be a partition of $V(G)$ into three stable sets. For $i\in \{1,2,3\}$, let $S_i' = S_i\times\{i\}$. Then $S = S_1'\cup S_2'\cup S_3'$ is a stable set in $G'-C$ dominating $C$. By Lemma \ref{lem:strong-cliques}, $C$ is not strong in $G'$.
See Figure~\ref{fig:reduction-2}.

\begin{figure}[h]
  \centering
  \includegraphics[scale=0.8]{reduction-2.pdf}
  \caption{Mapping a $3$-coloring of $G$ to a stable set in $G'-C$ dominating $C$.}
  \label{fig:reduction-2}
\end{figure}

The implication $2\Rightarrow 3$ is immediate. Next we prove the implication $3\Rightarrow 2$. For this, we show that no maximal clique $C'$ in $G'$ other than $C$ is  strong. Let $C'\neq C$ be a maximal clique in $G'$. Since $G$ is triangle-free it follows that either $C'= \{(u,i),(v,i)\}$ for some $uv\in E(G)$ and $i\in\{1,2,3\}$ or $C'=C_v$ for some $v\in V(G)$. In the first case, suppose without loss of generality that $i=1$, then $C'=\{(u,1),(v,1)\}$ for some $uv\in E(G)$. Then, $\{(u,2),(v,3)\}$ is a stable set in $G'-C'$ dominating $C'$. Hence, $C'$ is not strong. Now, let $C'=C_v$ for some $v\in V(G)$. Let $u_1,u_2,u_3$ be three different neighbors of $v$ in $G$  and let $u_0\in V(G)\setminus \{v,u_1,u_2,u_3\}$.
(Recall that such vertices exist since $G\in \mathcal{G}$.) Then, $\{(u_i,i)\mid i\in \{0,1,2,3\}\}$ is a stable set in $G'-C'$ dominating $C'$. Hence, $C'$ is not strong.

Next we prove that statements 2 and 4 are equivalent. By Lemma \ref{lem:strong-cliques}, it suffices to show that there is a stable set in $G'-C$ dominating $C$ if and only if there is a stable set in $G''-C$  dominating $C$. But these two conditions are clearly equivalent, since
$G'[N_{G'}[C]] = G''[N_{G''}[C]] =G'$.

Before proving the remaining implications, let us note that for any vertex $v\in V(G)$ and $i\in \{1,2,3\}$, the clique $\{(v,i),(v,i)'\}$
is a simplicial clique in $G''$. In particular, $\{\{w,w'\}\mid w\in V(G')\setminus C\}$ is a collection of strong cliques in $G''$.
This immediately implies that statements 4 and 6 are equivalent.

Clearly, statement 6 implies statement 7 and statement 7 implies statement 5. Finally, we prove the implication $5\Rightarrow 4$. Suppose that every vertex of $G''$ is contained in a strong clique. Note that for every vertex $v\in V(G)$, the sets $C_v$ and $C$ are the only maximal cliques in $G''$ containing vertex $(v,0)$. Observe that $\{(v,i)'\mid i\in\{1,2,3\}\}\cup\{(u,0)\}$ where $u\in V(G)\setminus\{v\}$ is a stable set in $G''-C_v$ dominating $C_v$. By Lemma \ref{lem:strong-cliques}, $C_v$ is not strong in $G''$. Thus, since $(v,0)$ is contained in a strong clique, we infer that $C$ is a strong clique in $G''$.
\qed\end{proof}

Using Proposition~\ref{prop:reductions} we derive the following hardness results.

\thmHard*
\begin{sloppypar}
\begin{proof}
First we establish membership in {\sf co-NP} of the first four problems.

{\sc Strong Clique} is in {\sf co-NP} when restricted to any class of graphs. Given a \noinstance~to the problem, consisting of a graph $G$ and a clique $C$ in $G$, a short certificate of the fact that $C$ is not a strong clique in $G$ is given by any stable set $S$ in $G-C$ that dominates $C$ (such a stable set exists by Lemma~\ref{lem:strong-cliques}).

{\sc Strong Clique Existence} is in {\sf co-NP} when restricted to the class of diamond-free graphs. Given a \noinstance~to the problem, consisting of a diamond-free graph $G$ in which no clique is strong, a short certificate of this fact is a collection of  stable sets $S_C$, one for each maximal clique $C$ in $G$, such that each $S_C$ is a stable set in $G-C$ dominating $C$. Such a collection of stable sets exists by Lemma~\ref{lem:strong-cliques}, and it is of polynomial size by Corollary~\ref{cor:maximal-cliques-diamond-free}.

{\sc Strong Clique Vertex Cover} is in {\sf co-NP} when restricted to the class of diamond-free graphs. Consider a \noinstance~to the {\sc Strong Clique Vertex Cover} problem, consisting of a diamond-free graph $G$ in which not all vertices are contained in a strong clique. In this case, a short certificate consists of a vertex $v\in V(G)$ that is not contained in any strong clique and a collection of stable sets $S_C$, one for each maximal clique $C$ containing $v$, such that $S_C$ is a stable set in $G-C$ dominating $C$. Such a collection of stable sets exists by Lemma~\ref{lem:strong-cliques}, and it is of polynomial size by Corollary~\ref{cor:maximal-cliques-diamond-free}.

{\sc Strong Clique Partition} is in {\sf co-NP} in any class of graphs. A \noinstance~to the {\sc Strong Clique Partition} problem consists of a graph $G$ and a partition of its vertex set into cliques such that not all cliques in the partition are strong. A short certificate of the fact that this is indeed a \noinstance~consists of a clique $C$ from the given collection that is not strong and a stable set in $G-C$ dominating $C$. (Such a stable set exists by Lemma~\ref{lem:strong-cliques}.)

We prove hardness of all the five problems in the class of diamond-free graphs using a reduction from the {\sc $3$-Colorability} problem in the class $\mathcal{G}$, which is {\sf NP}-complete by Theorem~\ref{thm:3-col}. Note that by Proposition~\ref{prop:reductions}, the derived graphs $G'$ and $G''$ are diamond-free. Clearly, they can be computed in polynomial time from $G$.
Hardness of the {\sc Strong Clique} problem follows from the fact that $G$ is $3$-colorable if and only if $C$ is not a strong clique in $G'$. Hardness of the {\sc Strong Clique Existence} problem follows from the fact that $G$ is $3$-colorable if and only if $G'$ does not have any strong cliques. Hardness of the {\sc Strong Clique Vertex Cover} problem follows from the fact that $G$ is $3$-colorable if and only if not every vertex of $G''$ is contained in a strong clique.
Consider now the {\sc Strong Clique Partition} problem. By Proposition~\ref{prop:reductions}, $G$ is $3$-colorable if and only if not every clique from the following collection of cliques in $G''$ is strong: $\{C\}\cup \{\{w,w'\}\mid w\in V(G')\setminus C\}\,.$ Note that the cliques in this collection form a partition of the vertex set of $G''$ and that they can be computed in polynomial time from $G$. Hardness of the {\sc Strong Clique Partition Existence} problem follows from the fact that $G$ is $3$-colorable if and only if the vertex set of $G''$ cannot be partitioned into strong cliques.
\qed\end{proof}
\end{sloppypar}

\section{Conclusion}

\begin{sloppypar}
We established the complexity of seven problems related to strong cliques in the class of diamond-free graphs. Five of these problems remain intractable and the remaining two become solvable in linear time.
Our work refines the boundaries of known areas of tractability and intractability of algorithmic problems related to strong cliques in graphs. Besides the open problems of the complexity of testing whether every maximal clique is strong, or whether every edge is contained in a strong clique, many other interesting questions remain. For example, it is still open whether there exists a polynomial-time algorithm to recognize the class of strongly perfect graphs, introduced in 1984 by Berge and Duchet~\cite{MR778749} and defined as graphs in which every induced subgraph has a strong stable set. To the best of our knowledge, the recognition complexity of strongly perfect graphs is also open when restricted to the class of diamond-free graphs.
\end{sloppypar}

\subsection*{Acknowledgements}

\begin{sloppypar}
The authors are grateful to Ademir Hujdurovi\'c for helpful discussions and the anonymous reviewers for constructive remarks. The second named author has been supported by the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No.~734922, by Mexico's CONACYT scholarship 254379/438356, by Erasmus+ for practices (SMT) Action KA103 - Project 2017/2019, by MICINN from the Spanish Government under project PGC2018-095471-B-I00, and by AGAUR from the Catalan Government under project 2017SGR1087. The first and third named authors are supported in part by the Slovenian Research Agency (I0-0035, research programs P1-0285 and P1-0404, and research projects J1-9110, N1-0102). Part of this work was done while the third named author was visiting LAMSADE, University Paris-Dauphine; their support and hospitality is gratefully acknowledged.
\end{sloppypar}

\bibliographystyle{abbrv}
\bibliography{biblio}

\end{document}

config: arxiv


TITLE: if $g(t)=f(\frac {\cos (t)}t,\frac {\sin (t)}t)$ is a monotonic increasing function for $t>0$ then $\nabla f(0,0)=(0,0)$
QUESTION [0 upvotes]: Let $f:\mathbb R^2 \rightarrow \mathbb R $ be in $C^1$. suppose that $g(t)=f(\frac {\cos (t)}t,\frac {\sin (t)}t)$ is a monotonic increasing function for $t>0$. prove that $\nabla f(0,0)=(0,0)$.
I tried using the chain rule to acquire some information about $f$ but I'm not sure it is even the right direction. any hints?

REPLY [1 votes]: We can do this assuming only that $f$ is differentiable at $(0,0).$ Let $h(t) = g(1/t)=f(t\cos (1/t), t\sin (1/t)).$ Then $h$ is decreasing on $(0,\infty).$ Let $\nabla f(0,0) = (a,b).$ Then as $t\to 0,$
$$h(t)=f(0,0) + at\cos (1/t) + bt\sin (1/t) +o(t).$$
Thus $h(1/n\pi) = f(0,0) + a(-1)^n/n\pi +o(1/n).$ If $a\ne 0,$ this oscillates above and below $f(0,0)$ infinitely many times. This contradicts $h$ being decreasing. Hence $a=0.$ Same idea to get $b=0.$ Thus $\nabla f(0,0) = (0,0).$


TITLE: Solving equations with dozens of ceil and floor functions efficiently?
QUESTION [1 upvotes]: I am tackling a problem which uses lots of equations in the form of:
$$
q_i(x) = c_i(x) +
 \sum_{j=1}^N \left\lfloor \frac{q_i(x)}{P_j} \right\rfloor C_j
$$
where $q_i(x)$ is the only unknown, $c_i$, $C_j$, $P_j$ are always positive. $C_j < P_j$ for all $j$

How is this type of problems efficently solved especially when the number of iterations $N$ is between 20 - 100?

What I was doing is $q_i(x) - c_i(x)$ must be equal to the summation of integers. So i was doing an exhaustive search for $q_i(x)$ which satisfies both ends of the equation. Clearly this is computationally exhaustive even if I do the search on a parallel computer..

What if $c_i(x)$ is a floating point number, this will even make the problem even more difficult to find a real $q_i(x)$?

Thanks

REPLY [3 votes]: My proposal:
[For the sake of brevity the unknown $q_i(x)$ is denoted $Q$ and $c_i(x)$, $C$.] All constants can be real.
The right hand side is a sum of regular staircase functions, with the steps having width $P_j$ and height $C_j$. You can construct the resulting sum for increasing $Q$, from $Q=0$, by finding all discontinuities. The discontinuities occur at integer multiples of the widths, i.e. $k_jP_j$.

Maintain a vector with components $(k_j+1)P_j$, and a corresponding sum $S=C+\sum k_jC_j$. Initialize all $k_j=0$ and $S=C$. Now take the smallest of the $(k_j+1)P_j$ and increment $k_j$: $k_jP_j$ is increased by $P_j$, and $S$ by $C_j$.
Doing this repeatedly, you will enumerate all discontinuities, by increasing order. Between two successive discontinuities, let at $Q'$ and $Q''$, the sum is constant and equals the current S. You have a solution $Q=S$ every time that $Q'\le S\le Q''$.
For efficient implementation, the list of future discontinuities $(k_j+1)P_j$ is better organized as a priority queue.
Assuming that the first solution is found after the $M^{th}$ discontinuity, the running time will be $O(M\log N)$.
UPDATE:
Given that $x-1<\lfloor x\rfloor\le x$, we have this bracketing for $S$:
$$C+Q\sum_{j=1}^N\frac{C_j}{P_j}-\sum_{j=1}^NC_j<S=C+\sum_{j=1}^N\lfloor\frac Q{P_j}\rfloor C_j\le C+Q\sum_{j=1}^N\frac{C_j}{P_j}.$$
By equating the bounds (magenta and black lines) to $Q$ (green), you get a good estimate of the range where solutions can be found. (If you start from a nonzero $Q$, you can initialize $k_j=\lfloor\frac Q{P_j}\rfloor$.)


TITLE: Show that $(\mathbb{Z}*\mathbb{Z})/[\mathbb{Z}*\mathbb{Z},\mathbb{Z}*\mathbb{Z}]\cong \mathbb{Z}\oplus\mathbb{Z}$
QUESTION [5 upvotes]: Im trying to show that
$$(\mathbb{Z}*\mathbb{Z)}/[\mathbb{Z}*\mathbb{Z},\mathbb{Z}*\mathbb{Z}]\cong \mathbb{Z}\times\mathbb{Z}$$
and my first thought was to use the first isomorphism theorem. I've been trying to use the homomorphism
$$\phi:\mathbb{Z}*\mathbb{Z}\to \mathbb{Z}\times \mathbb{Z}$$ defined by
$$\phi(a^{n_1}b^{m_1}\cdots a^{n_k}b^{m_k})=(a^{n_1}\cdots a^{n_k},b^{m_1}\cdots b^{m_k})$$ Where we are considering $\mathbb{Z}*\mathbb{Z}$ to be the free product of two infinite cyclic groups generated by a and b respectively. I have shown that this is a homomorphism and is surjective, but i am really struggling to show that the commutator is the kernel. I have that the commutator is contained in the kernel but i cannot show the other containment. I am beginning to suspect that it is in fact not equal to the kernel, but if that is the case I am stumped on how to proceed. I was hoping someone would be able to shine some light on the problem.

REPLY [1 votes]: I ended up figuring out something using the first isomorphism theorem like I initially wanted to. Using the same homomorphism defined in my question, I was able to show that $[\mathbb{Z}*\mathbb{Z},\mathbb{Z}*\mathbb{Z}]=\ker(\phi)$. I did this using a lemma:
An element in $w\in\mathbb{Z}*\mathbb{Z}$, where
$$w=a^{n_1}b^{m_1}\cdots a^{n_k}b^{m_k}$$ is also an element of $[\mathbb{Z}*\mathbb{Z},\mathbb{Z}*\mathbb{Z}]$ if and only if
$$n_1+n_2+\cdots+n_k=0\,\,\,\text{and}\,\,\,m_1+m_2+\cdots+m_k=0$$
This lemma was fairly easy to prove using induction on the lengths of words where, to apply the induction step, you must multiply by some commutators to reduce the word length. Then with this tool it is easy enough to show that given some arbitrary $x\in \ker(\phi)$, we must have $x$ satisfying the right hand side of that iff and thus $\ker(\phi)=[\mathbb{Z}*\mathbb{Z},\mathbb{Z}*\mathbb{Z}]$. Then the first isomorphism theorem applies and yields the final result.


text:
\shrink
\section{The Primal View: Tight Moment Relaxation}
\label{sec:primalMoment}
\shrink
In this section, we develop dense (Section~\ref{sec:lasserreHierarchy}) and sparse (Section~\ref{sec:basisReduction}) convex moment relaxations to the POP~\eqref{eq:pop}. The dense relaxation is a standard application of Lasserre's hierarchy~\cite{Lasserre01siopt-LasserreHierarchy,lasserre10book-momentsOpt}, while the sparse relaxation is based on a basis reduction that leverages the structural properties in
Proposition~\ref{prop:pop}.

\subsection{Lasserre's Hierarchy}
\label{sec:lasserreHierarchy}

\optional{We first describe some definitions for stating Lasserre's hierarchy. Let $\mu_{\xextend}$ be any probability distribution supported on the feasible set $\calxextend$ of the POP~\eqref{eq:pop}, and let $\moments_\rorder = \{ \moment_{\valpha} \} \in \Real{\dimbasis{\dimxextend}{\rorder}}$ be the vector of \emph{moments} up to degree $\rorder$, where $\moment_{\valpha} \doteq \int \xextend^{\valpha} d\mu_{\xextend}$ for any $\xextend^{\valpha} \in [\xextend]_\rorder$. Clearly, $\moment_\zero = 1$. The \emph{moment matrix} $\MM_{\rorder}(\moments_{2\rorder}) \in \sym^{\dimbasis{\dimxextend}{\rorder}}$ is the assembly of $\moments_{2\rorder} \in \Real{\dimbasis{\dimxextend}{2\rorder}}$ into a symmetric matrix whose rows and columns are indexed by $\monoleq{\xextend}{\rorder}$, with the $(i,j)$-th entry being:
\bea
\left[  \MM_{\rorder}(\moments_{2\rorder}) \right]_{ij} = \moment_{\valpha_i + \valpha_j},
\eea
where $\valpha_i$ and $\valpha_j$ are the exponents of the $i$-th and the $j$-th monomials in $\monoleq{\xextend}{\rorder}$. Given a moment matrix $\MM_{\rorder}(\moments_{2\rorder})$ and a polynomial $q = \sum_{\vbeta} c(\vbeta) \xextend^{\vbeta} \in \polyringin{\xextend}$, define the \emph{localizing matrix} to be $\MM_\rorder(q \moments_{2\rorder}) \in \sym^{\dimbasis{\dimxextend}{\rorder}}$, whose $(i,j)$-th entry is:
\bea
\left[ \MM_\rorder(q \moments_{2\rorder}) \right]_{ij} = \sum_{\vbeta} c(\vbeta) \moment_{\valpha_i + \valpha_j + \vbeta}.
\eea}

The following theorem describes

Lasserre's hierarchy of dense moment relaxations for the POP~\eqref{eq:pop}.
\begin{theorem}[Dense Moment Relaxation~\cite{lasserre10book-momentsOpt}]\label{thm:denseMoment}
The dense moment relaxation at order $\rorder \; (\geq 2)$ for the POP~\eqref{eq:pop} is the following SDP:
\bea
p^\star_\rorder	 = \min_{\moments_{2\rorder} \in \Real{\dimbasis{\dimxextend}{2\rorder}} }& \sum_{\valpha \in \calF} c(\valpha) \moment_{\valpha} \label{eq:denseMoment} \\
\subject & \moment_{\zero} = 1, \MM_{\rorder}(\moments_{2\rorder}) \succeq 0, \nonumber \\
& \MM_{\rorder - 1}(h_j \moments_{2\rorder-2}) = \zero, j=1,\dots,\nrEq, \nonumber \\
& \MM_{\rorder - 1}(g_k \moments_{2\rorder-2}) \succeq 0, k = 1,\dots,\nrIneq. \nonumber
\eea
where $\moments_{2\rorder} = \{ \moment_{\valpha} \} \in \Real{\dimbasis{\dimxextend}{2\rorder}}$ is the vector of \emph{moments} up to degree $2\rorder$,
$c(\valpha)$ are the real coefficients of the objective function $f(\xextend)$ corresponding to monomials $\xextend^{\valpha}$ in~\eqref{eq:pop},
$\MM_{\rorder}(\moments_{2\rorder}) \in \sym^{\dimbasis{\dimxextend}{\rorder}}$ is the \emph{moment matrix}, and $\MM_{\rorder - 1}(h_j \moments_{2\rorder-2}),\MM_{\rorder - 1}(g_k \moments_{2\rorder-2}) \in \sym^{\dimbasis{\dimxextend}{\rorder-1}}$ are the \emph{localizing matrices}.\footnote{We refer the non-expert reader to~\cite{lasserre10book-momentsOpt} for a
comprehensive introduction to moment relaxations, and provide extra definitions and accessible examples in the \supp.\label{footnote2} }

 Let $\moments_{2\rorder}^\star$ be the optimal solution of~\eqref{eq:denseMoment}, then the following holds true:
\begin{enumerate}[label=(\roman*)]
\item (lower bound) $p_\rorder^\star$ is a lower bound for $f^\star$,~\ie~$p_\rorder^\star \leq f^\star,\forall \rorder \geq 2$;
\item (finite convergence) $p_{\rorder_1}^\star \leq p_{\rorder_2}^\star $ for any $\rorder_1 \leq \rorder_2$, and $p_\rorder^\star = f^\star$ at some finite $\rorder$;
\item \label{prop:dense-certificate} (optimality certificate) if $\rank{\MM_{\rorder}(\moments_{2\rorder}^\star)} = 1$, then $\moments_{\rorder}^\star = \monoleq{\xextend^\star}{\rorder}$, where $\xextend^\star$ is the unique global minimizer of the POP~\eqref{eq:pop}, and the relaxation is said to be \emph{tight};
\item \label{prop:dense-gap} (rounding and duality gap) if $\rank{\MM_{\rorder}(\moments_{2\rorder}^\star)} > 1$,
let $\hatxextend$ be a rounded estimate computed from a rank-1 approximation of $\MM_{\rorder}(\moments_{2\rorder}^\star)$,\footref{footnote2}
and
\optional{let $\hatxextend = {\proj_{\calxextend} (\vv_{\xextend})}$ where $\vv \in \Real{m(\rorder)}$ is the eigenvector of $\MM_{\rorder}(\moments_{2\rorder}^\star)$ corresponding to the largest eigenvalue, with the first entry normalized to 1, $\vv_{\xextend}$ extracts the sub-vector of $\vv$ at locations corresponding to $\xextend$ in $\monoleq{\xextend}{\rorder}$, and $\proj_{\calxextend}$ projects $\vv_{\xextend}$ to $\calxextend$

denote $\hatf = f(\hatxextend)$. }{denote $\hatf = f(\hatxextend)$.}
Then, $p_\rorder^\star \leq f^\star \leq \hatf$ and we say that the relative duality gap is $\eta_\rorder = (\hatf - p^\star_\rorder)/ \hatf$.
\end{enumerate}
\end{theorem}

Theorem~\ref{thm:denseMoment} is a standard application of Lasserre's hierarchy~\cite{Lasserre01siopt-LasserreHierarchy} and the finite convergence result~\cite{Nie14mp-finiteConvergenceLassere} to problem~\eqref{eq:pop}.
\optional{We remark that computing the rank of $\MM_{\rorder}(\moments_{2\rorder}^\star)$ is subject to numerical inaccuracy and instead we use the relative duality gap $\eta_\rorder$ as a metric for evaluating tightness. In Section~\ref{sec:experiments}, we show that the relaxation is
empirically tight at the minimum relaxation order $\rorder = 2$.}{\finalLC{Although Lasserre's hierarchy is guaranteed to be tight at some finite $\rorder$, the relaxation becomes computationally impractical for large $\rorder$. Therefore, it is desirable to obtain tight relaxations with small $\rorder$.} In the \supp, we show that the dense moment relaxation is
empirically tight at the \emph{minimum} relaxation order $\rorder = 2$ for Examples~\ref{eg:singleRotationAveraging}-\ref{eg:meshRegistration}, \finalLC{despite the fact that the POPs have both binary variables (a notoriously challenging setup~\cite{lasserre01ipco-lasserrehierarchybinary}) and non-convex constraints $\MR \in \SOthree$.} }

\subsection{Basis Reduction}
\label{sec:basisReduction}
Although the dense relaxation is tight at $\rorder = 2$, the size of the SDP~\eqref{eq:denseMoment} (\ie~the size of the moment matrix $\MM_{\rorder}(\moments_{2\rorder})$ for $\rorder=2$) is $\nchoosek{n+N+2}{2}$, which grows \emph{quadratically} in the number of measurements $N$ and quickly becomes intractable even for small $N$ (\eg~$N=20$). In this section, we exploit the \emph{monomial sparsity} of the POP~\eqref{eq:pop} and use basis reduction to construct a sparse moment relaxation whose size grows linearly with $N$.

\begin{theorem}[Sparse Moment Relaxation]\label{thm:sparseMoment}
\edit{Define $\rbasis{\xextend} \doteq [1,\vxx\tran,\vtheta\tran,\monoindeg{\vxx}{2}\tran,\vtheta\tran \kron \vxx\tran]\tran$ to be a reduced set of monomials, with $\rbasisset$ being the set of monomial exponents in $\rbasis{\xextend}$,~\ie~$\rbasisset \doteq \{\valpha \in \nnint^{\dimxextend}: \xextend^{\valpha} \in  \rbasis{\xextend} \}$. Similarly, define $\monoleq{\xextend}{\rbasisset_x} \doteq [1,\vxx\tran]\tran$ and let $\rbasisset_x$ be its set of exponents.
Let $2\rbasisset \doteq \{ \valpha \in \nnint^{\dimxextend}: \valpha = \valpha_1 + \valpha_2, \valpha_1,\valpha_2 \in \rbasisset \}$ (resp. $2\rbasisset_x$) be the Minkowski sum of $\rbasisset$ (resp. $\rbasisset_x$) with itself.

Define $\moments_{2\rbasisset} \in \Real{\dimbasis{}{2\rbasisset}}$ (resp. $\moments_{2\rbasisset_x} \in \Real{\dimbasis{}{2\rbasisset_x}} $) to be the vector of moments for all monomials in $\left[\xextend\right]_{2\rbasisset}$ (resp. $\monoleq{\xextend}{2\rbasisset_x}$), and $\MM_{\rbasisset}(\moments_{2\rbasisset}) \in \sym^{\dimbasis{}{\rbasisset}}$
(resp. $\MM_{\rbasisset_x}(\moments_{2\rbasisset_x}) \in \sym^{\dimbasis{}{\rbasisset_x}}$) to be the moment matrix that assembles $\moments_{2\rbasisset}$ (resp. $\moments_{2\rbasisset_x}$) in rows and columns indexed by $\rbasis{\xextend}$ (resp. $\monoleq{\xextend}{\rbasisset_x}$). }

Then, the sparse moment relaxation is:
\bea
p_{\rbasisset}^\star = \min_{\moments_{2\rbasisset} \in \Real{\dimbasis{}{2\rbasisset}}} & \sum_{\valpha \in \calF} c(\valpha) \moment_{\valpha} \label{eq:sparseMoment} \\
\subject & \moment_\zero = 1, \MM_{\rbasisset}(\moments_{2\rbasisset}) \succeq 0, \nonumber \\
& \MM_1(h \moments_2) = \zero, \forall h \in \vh^{x}; \quad \MM_{\rbasisset_x}(h \moments_{2\rbasisset_x}) = \zero, \forall h \in \vh^{\theta}, \nonumber \\
& \MM_1(g \moments_2) \succeq 0, \forall g \in \vg, \nonumber
\eea
where $\vh^x,\vh^{\theta},\vg$ are defined as in Proposition~\ref{prop:pop}. Moreover, we have $p^\star_{\rbasisset} \leq p^\star_2 \leq f^\star$ and properties~\ref{prop:dense-certificate}-\ref{prop:dense-gap} in Theorem~\ref{thm:denseMoment}
hold for the sparse relaxation~\eqref{eq:sparseMoment}.

\end{theorem}
The key idea behind Theorem~\ref{thm:sparseMoment} is to reduce the size of the SDP by only considering the reduced monomial basis $\rbasis{\xextend}$, which essentially removes all the monomials of the form $\theta_i\theta_j$ that do not appear in $f$ as per property \ref{prop:pop-objective} in Proposition~\ref{prop:pop}.

The size of the SDP~\eqref{eq:sparseMoment} (\ie~the size of $\MM_{\rbasisset}(\moment_{2\rbasisset})$) is $\dimbasis{}{\rbasisset} = \frac{(n+1)(n+2)}{2} + (1+n)N$, which grows linearly in $N$. In Section~\ref{sec:experiments}, we show that the sparse moment relaxation~\eqref{eq:sparseMoment} is also tight, even in the presence of a large amount of outliers. \finalLC{Although there exist  other efficient sparse variants~\cite{Waki06jopt-SOSSparsity,Weisser18mpc-SBSOS} of Lasserre's hierarchy that exploit correlative sparsity, in the \supp we show they break the tightness at the minimum relaxation order and produce poor estimates. Nevertheless, they can be used to bootstrap our dual certifiers (Section~\ref{sec:drs}).}


TITLE: Are the strong and the weak operator topology well defined in abstract C* and Von Neumann algebras?
QUESTION [1 upvotes]: If $A$ is an abstract $C^*$ algebra, then a $A$ is isometrically isomorphic to a subalgebra of bounded operators $B(H)$ for some Hilbert space $H$. We can restrict the weak operator toplogy and the strong operator topology of $B(H)$ to $A$.
Are these definitions independent of $H$? And what about the case of $A$ being an abstract Von Neummann Algebra (a $C^*$ algebra who has a predual)?

REPLY [2 votes]: No, the weak and strong operator topologies depend strongly on the chosen representation.
For example, if you represent $C([0,1])$ on $L^2([0,1])$ by multiplication operators, then the functions $$f_n(x) = x^n$$ converge strongly to zero.  However, if you take the direct sume of that representation with the one dimensional representation corresponding to the character
$$f\mapsto f(1),$$
then the $f_n$ do not converge strongly to any $f$ in $C([0,1])$.


TITLE: Generators of symmetric group
QUESTION [3 upvotes]: Hi
Let $n$ be an odd natural number (sufficiently large), and $ 1\leq t,k < n $. Let $A= \{ a_{1},a_{2},\ldots,a_{t} \} $, $B= \{ b_{1},b_ {2},\ldots,b_{n-t} \} $, $C= \{ c_{1},c_{2} \ldots,c_{k} \} $ and $D= \{ d_{1},d_{2},\ldots,d_{n-k} \} $ be subsets of  $ \{ 1,2,\ldots,n \} $ such that $A\cup B=C\cup D= \{ 1,2,\ldots,n \} $  and  $A\cap B=C\cap D=\phi$ and $A\neq C$ and $A\neq D$. What can we say about the subgroup generated by $(a_{1},a_{2},\ldots,a_{t})(b_{1},b_{2},\ldots,b_{n-t})$ and $(c_{1},c_{2},\ldots,c_{k})(d_{1},d_{2},\ldots,d_{n-k})$. I think that this subgroup is $S_{n}$. Is it true? Maybe there is a simple counterexample but I've not found it.
Clearly, $n$ should be odd. Otherwise, this group is a subgroup of $A_{n}$.

REPLY [7 votes]: Regarding the assertion that the result is true for prime $n$, here are counterexamples for every prime $n>3$.  A simple concrete example for $n=5$ is given by
$(1,2,3,4)(5)$ and $(1,3,5,4)(2)$, which generate an order-$20$ subgroup of $S_5$.  More generally, let $g$ be a generator of the multiplicative group of $\mathbb{F}_n$, and consider the permutations of $\mathbb{F}_n$ given by $x\mapsto gx$ and $x\mapsto gx+1$.  These two permutations generate the group of all permutations $x\mapsto ax+b$ with $a,b\in\mathbb{F}_n$ and $a\ne 0$, which has order $n(n-1)$.
But each of these two permutations has one fixed point and one $(n-1)$-cycle, and their fixed points are distinct.
Note that the reason $n=3$ is excluded is that this order $n(n-1)$ subgroup of $S_n$ equals $S_n$ when $n=3$.


TITLE: Is the weak form of a pde solvable without "essential" (Dirichlet) boundary conditions?
QUESTION [0 upvotes]: I have a non-linear form of the Poisson equation (with a diffusion coefficient that is a function of the derivatives of the dependent variable) that I'm trying to solve numerically (using FEM which requires the pde to be posed in its weak form).
$$ \nabla \cdot (\eta \nabla v) = G(x) $$
where $\eta = \sqrt{1/2 (\nabla v : \nabla v)}$ and $v = v(y,z)$.  Multiplying by a test function $\theta$ and integrating wrt the domain, $\Omega$, gives the weak form
$$ \oint_\Gamma \theta \cdot (\eta\nabla v \cdot \mathbf{n})d\Gamma - \int_\Omega \left( \eta\nabla v \cdot \nabla \theta + G \right) d\Omega = 0$$
However, none of my boundary conditions correspond to the Dirichelet type as I have $\partial_n v = v$ on three of the boundaries in a rectangular domain and $\partial_{n} v = 0$ on the other ($n$ is the normal vector to surface).
Is this problem actually solvable using FEM, or at all?  I have the solution to a simpler problem which might be a reasonable guess at the solution here.

REPLY [0 votes]: The former boundary condition corresponds to a Robin-type boundary condition and the latter corresponds to a Neumann-type boundary condition. Just split the boundary integral into the two sub-boundaries and apply the boundary conditions. The boundary term goes to zero on the Neumann part. On the Robin part you get an additional contribution to the nonlinear form. You end up with a nonlinear weak formulation which you can easily solve using a fixed-point or Newton's scheme.


TITLE: Find a basis for the space of quotients of polynomials over $\mathbb{R}$
QUESTION [3 upvotes]: $F$ is a field and define $F(t):=\lbrace \frac{p}{q} \mid p,q \in F[t], q\neq0 \rbrace$. Find a basis for $\mathbb{R}(t)$.

I know that the basis for the polynomials over $\mathbb{R}$ is $\lbrace 1,x,x^2,x^3,\ldots \rbrace$, so intuitively I guess the basis for $\mathbb{R}(t)$ is $\lbrace 1,x,x^2,\ldots,\frac{1}{x},\frac{1}{x^2},\ldots \rbrace$. Is this correct? If not, what is the right approach to find the basis?

REPLY [6 votes]: Some elements of response.
The family of vectors $\mathcal F = \{1,t,t^2, \dots, \frac{1}{t}, \frac{1}{t^2}, \dots\}$ is linearly independent. However $\mathcal F$ does not span $\mathbb R(t)$. If that was the case, you would be able to find $a_0, \dots, a_n, b_{-1}, \dots, b_{-m}$ such that for all $t \in \mathbb R$
$$\frac{1}{1+t^2}=a_0 + a_1 t + \dots + a_n t^n + \frac{a_{-1}}{t} + \dots + \frac{a_{-m}}{t^m} \tag{1}$$ As $$\lim\limits_{t \to +\infty} \frac{1}{1+t^2} = \lim\limits_{t \to +\infty} \frac{a_{-1}}{t} = \dots = \lim\limits_{t \to +\infty} \frac{a_{-m}}{t^m} = 0$$ $(1)$ implies $a_0=a_1= \dots = a_n=0$. Hence you have for all $t \in \mathbb R$ $$\frac{1}{1+t^2}=\frac{a_{-1}}{t} + \dots + \frac{a_{-m}}{t^m} \tag{2}$$ You will verify that such equality cannot hold for all $t \in \mathbb R$. Hence $\frac{1}{1+t^2}$ doesn't belong to the linear span of $\mathcal F$.
To find a basis, the partial fraction decomposition should be of interest. In particular, consider following subsets of $\mathbb R(t)$ $$\begin{cases}
A &= \{1, t, t^2, \dots \}\\
B &= \left\{\frac{1}{(t-a)^n} \, | \, a \in \mathbb R, \, n \in \mathbb N \right\}\\
C &=\left\{\frac{1}{(t^2+2bt+c)^n}, \frac{t}{(t^2+2bt+c)^n} \, | \, b,c \in \mathbb R, \, b^2-c <0, \,n \in \mathbb N \right\}
\end{cases}$$ According to partial fraction decomposition, $A \cup B \cup C$ should be a basis of  $\mathbb R(t)$ as the irreducible polynomials of $\mathbb R[t]$ are precisely the $t-a$ and $t^2+2bt+c$ with $a,b,c \in \mathbb R$ and $b^2-c <0$.


TITLE: Given that the two vectors 8a -b and 4a +3b are perpendicular and that |a |= 2|b |, determine the angle between a and b.
QUESTION [0 upvotes]: I understand you have to use the dot product rule, but I'm not sure where to take it from there.

REPLY [1 votes]: This is a bit of a sketchy problem. One of the properties of the dot product is that it's linear; scaling either vector scales the whole thing, so $(a\vec{v})\cdot\vec{w}=\vec{v}\cdot(a\vec{w})=a(\vec{v}\cdot \vec{w})$. Also, the projected components add, so $\vec{u}\cdot(\vec{w}+\vec{v})=(\vec{u}\cdot\vec{w})+(\vec{u}\cdot\vec{v})$. Of course, the history of the dot product is a lot more than just linearity. Also, by the Pythagorean theorem $|\vec{v}|=\sqrt{\vec{v}\cdot\vec{v}}$. Alternatively, $\vec{v}\cdot\vec{v}=|\vec{v}|^2$, the square of the magnitude.
So if $|\vec{a}|=2|\vec{b}|$, we can rewrite this as $|\vec{a}|^2=(2|\vec{b}|)^2$, $|\vec{a}|^2=4|\vec{b}|^2$, $\vec{a}\cdot\vec{a}=4\vec{b}\cdot\vec{b}$
Anyways plugging this into the expansion of $(8a-b)\cdot(4a+3b)$, which is $(8a)\cdot(4a)+(8a)\cdot(3b)+(-b)\cdot(4a)+(-b)\cdot(3b)=32(a\cdot a)+20(a\cdot b)-3(b\cdot b)=0$
$a\cdot b$ (which you'll need to solve for the cosine, since $\cos(\theta)=\frac{a\cdot b}{|a||b|}$) equals therefore
$\frac{3(b\cdot b)-32(a\cdot a)}{20}$
$=\frac{3(b\cdot b)-32(4b\cdot b)}{20}$
$=\frac{3(b\cdot b)-128(b\cdot b)}{20}$
$=\frac{-125(b\cdot b)}{20}$
$=\frac{-25(b\cdot b)}{4}$ (diving the top and bottom by 5)
and $\cos(\theta)=\frac{a\cdot b}{|a||b|}$ which also equals $\frac{\left(\frac{-25}{4}(b\cdot b)\right)}{(2|b|)|b|}=\frac{-25}{8}$, more or less.
However as $25>8$, and cosine is always a ratio between 0 and $\pm1$, you can never have a cosine that reaches this number - not with real numbers anyways.
On desmos, I've plotted this problem. Dragging the (draggable) dot, the red shape is the set of all possible positions of tips of vectors $\vec{b}$ that satisfy $(8a-b)\cdot(4a+3b)=0$ for a given vector $\vec{a}$, the draggable point. The black circle is to make clear the magnitude of $\vec{a}$, which does seem to always be less than $|\vec{b}|$, however the problem suggests that, since $|\vec{a}|=2|\vec{b}|$, the magnitude of $\vec{a}$ is always bigger (in fact, lmao, twice as big) as $|\vec{b}|$.
If you got this problem from a textbook, these things can happen from time to time to time. Of course you can just solve $\cos^{-1}\left(\frac{-25}{8}\right)$ over the complexes, but that's probably not what your teacher expects you to do. These things happen all the time, someone slips up and makes an impossible problem. For example, I remember once in school we given a non-right triangle to solve. If you just blindly solved it using the law of sines, you happened to get a perfectly reasonable answer. But if you tried it with the law of cosines, you actually got an imaginary number. That's because the person who made the problem had set up some sketchy impossible triangle, where the two smaller side lengths didn't add up to at least the longer side length. But yeah, it's an interesting question.
So yeah, I wouldn't have answered this if it weren't for Anurag A's comment, "The above hint will work in general. But if I were you, I would want to make sure that the data given is correct." When in doubt, if you've checked your work loads of times, you can think about and dig deeper into your answer to confirm that you're right and the problem isn't. Or you copied it wrong. But still, I think that's the amazing thing about math - that you can change one little thing and it changes the whole interpretation of the problem. But, if you did copy it wrong, then it's ok as long you still know how to solve the problem - after all, math is more than just copying things! The important part is figuring out how to solve the problem, and understanding the why of stuff. The rest is just computation. I'm sorry I couldn't help more.


TITLE: Multiple variables in derivative and finding the slope
QUESTION [3 upvotes]: I'm working on slope and geometrical differentiation. The problem is to find the slope of any point on the curve $$\frac{x^2}{3^2} + \frac{y^2}{2^2} = 1$$
I have found its derivative: $\frac{dy}{dx} = \frac{-4}{9} \frac{x}{y}$. The next requirement is to give the numerical value of the slope at x = 1. I obviously should give x the value of 1 in the derivative to calculate but how should I approach dealing with the value of y? Thanks in advance.

REPLY [4 votes]: Hint:
If $x = 1$, then:
$$\frac{1^{2}}{3^{2}} + \frac{y^{2}}{2^{2}} = 1$$
Can you use this to solve for all values of the $y$ coordinate?


TITLE: Optimizing the number of robots to be used for a certain task
QUESTION [3 upvotes]: We have $N$ buttons numbered $1$,$2$ .. $N$. Our aim is to press each of the buttons at least once in the minimum time possible. For that purpose we choose $m$ robots. These robots can press one of the buttons in each second. But when two or more robots try to press the same button at the same time, that button won't be pressed (the robots will know that the button couldn't be pressed). Under the restriction that all the robots should be coded identically (i.e. they should execute the same instructions), what value of $m$ will you choose and how will you code them?
For example, if we choose $m=1$ and instruct the robot to press the $i$th button in the $i$th second, it will take a total of $N$ seconds before all the buttons are pressed. If we choose $m=2$ and instruct the robots to press button $1$ or $2$ uniformly at random until they have successfully pressed one of those(if one of them is successful in pressing one, then the other is automatically successful in pressing the other), and then sequentially press every other button (for example, if the robot succeeded in pressing button $1$, then it will try(successfully) to press the buttons numbered $3$, $5$,.. in the next seconds), then it will take an average time of $2+\frac{N-2}{2}$ seconds before each button is pressed.

REPLY [1 votes]: For small $N$, the details of the optimal algorithm seem likely to be complicated; they're probably best determined by dynamic programming. However, for large $N$, the following algorithm covers all buttons in $3$ seconds asymptotically almost surely.
Take a very large number of robots, i.e. $m\gg N$, and let them press any of the buttons with probability $p=1/m$ each, and no button with probability $1-Np=1-N/m$. (This last probability is non-negative since $m\gg N$.) The probability that a particular button is pressed exactly once, and thus the expected fraction of buttons that get pressed exactly once, is
$$
mp(1-p)^{m-1}=m\cdot\frac1m\left(1-\frac1m\right)^{m-1}=\left(1-\frac1m\right)^{m-1}\to_{m\to\infty}\frac1{\mathrm e}\;.
$$
For large $N$, the distribution is sharply peaked around this expected value, so the fraction of buttons successfully pressed is almost certain to be greater than $1/3$. Now let the robots that successfully pressed a button press further buttons according to some predefined scheme. (For instance, let the robots plan their actions by virtually acting in succession in the order of the numbers of the buttons they pressed in the first second, and let each robot press the button with the lowest number that hasn't been pressed either in a previous second or in a previous planning step.)


TITLE: How to integrate this integral $\int(1-r)/(1+r)^2$??\
QUESTION [0 upvotes]: How to evaluate this integral
$$\int \frac{1-r}{(1+r)^2} \ \mathrm{d}r$$
I was trying to do by parts however it doesn't seems to work here.

REPLY [1 votes]: A simple substitution will work here. If $u=1+r$ then $\mathrm{d}u=\mathrm{d}r$. This gives
$$\begin{eqnarray*}
\int \frac{1-r}{(1+r)^2} \ \mathrm{d}r &=& \int \frac{2-u}{u^2} \ \mathrm{d}u \\ \\
&=& \int \frac{2}{u^2} - \frac{1}{u} \ \mathrm{d}u \\ \\
&=& -\frac{2}{u}-\ln|u|+c \\ \\
&=& -\frac{2}{1+r}-\ln|1+r|+c\end{eqnarray*}$$