Methods sec:methods

Analysis & Import of Grid Network Topology sec:analysis_import

As the underlying grid topologies support both the FLISR algorithms and the
simulation platform, extracting this information from the available data
served as a starting point for development. The data is derived from a
Geographical Information System (GIS) which maps the distribution network
through the use of geospatial data in addition to metadata related to each
individual asset, whether the entity is a pole, switch, substation or other
asset type. The properties contained depend on the asset type, including
connected poles, and phases (RST) which specifies if a pole is three phase
(MV) or single phase (LV). Additional properties include which poles are
equipped with Load Break Fault Make (LBFM) or Recloser circuit breakers and
which of these are configured as “Normally Open” and therefore serve as the
boundary between network lines. The work of transforming this data consisted
of four primary steps; mapping the base GIS data to a graph model, analysing
the key properties to include in the final dataset, determining a method of
approximating the number of connected customers to each pole and correlating
the identified properties to a consistent model.

Mapping of Relational Data to Graph Database Format sec:mapping

The original GIS dataset represents the distribution network topology in a
relational model. However, the inherent interconnectedness of power grids
lends itself more naturally to a graph representation. We employ Graph
Databases for their ontological view of relationships 8509057, allowing us to
represent the network as a connected graph $G(V,E)$, achieving several
benefits: a) Nodes ($V$): In our graph model, nodes represent individual
assets of the distribution network. This includes poles, transformers,
substations, feeder lines, switches and other relevant entities. Each node is
associated with properties extracted from the relational GIS dataset. b) Edges
($E$): Edges in our graph represent the physical connections between network
assets. These edges can be directed or undirected, depending on the nature of
the connection (e.g., power flow direction). The graph database is employed
utilizing “neo4j” graph as illustrated in [fig:graph_database]Fig.
fig:graph_database.

[width=0.5]Figures/fig_graph_database.pdf

Figure : Topology data ingested in graph database

###  Identification of Key Node Properties

The GIS dataset contains fifty tables, and was explored thoroughly to discern
useful data considering relevant assets and to organise it in such a way that
it could be efficiently loaded into the simulation platform and ingested by
the FLISR algorithms. A key table identified “InstSections” forms the hub of
the data schema and maps to a majority of other entities via the property
“SectionId”. In the context of the GIS system individual poles are referred to
as “nodes”, and therefore the properties “FromNodeId” and “ToNodeId” determine
how poles are connected, additionally the property “SectionPhases” specifies
whether a section is part of the MV or LV network, [fig:inst_section]Fig.
details a subset of the “InstSection” schema.

[width=0.32]fig_inst_section_schema.pdf

Figure : InstSection Schema

Geolocation data for nodes is found in the “Nodes” table, in Geographic
(latitude & longitude) coordinate format as shown in [fig:node_schema]Figure .

[width=0.3]fig_node_schema.pdf

Figure : Node Schema

Information on nodes with on pole equipment, are contained within the
“InstSwitches” table, which includes a number of properties as illustrated in
[fig:switch_schema]Fig. , most notably “SectionId” and “UniqueDeviceId” for
linking to the “InstSection” and “Node” entities, in addition to “SwitchType”
where LBFM circuit breakers are denoted as “Soules” and “SwitchIsOpen” which
specifies whether the asset is configured to be a normally open point.

[width=0.3]fig_inst_switches_schema.pdf

Figure : InstSwitches Schema

While Reclosers are denoted as circuit breakers, within the GIS dataset these
are denoted as an entity named “InstReclosers” with a number of properties as
described in [fig:recloser_schema]Figure . Similar to the previous entity, the
“InstReclosers” table contains the “SectionId” and “UniqueDeviceId”
properties. Where it differs is the inclusion of “Manufacturer” and “Model”,
the assets of interest are denoted as “Nu-Lec” model “N Series”. Reclosers
configured as normally open are specified by the “RecloserIsOpen” property.

[width=0.35]Figures/fig_inst_reclosers_schema.pdf

Figure : InstReclosers Schema

###  Estimating connected customers at each node

A key requirement of the simulation platform is to provide metrics based on
the outputs of the FLISR algorithms. As the GIS data is anonymised, it does
not contain fine-grained customer related data, therefore it was necessary to
derive some approximation of the amount of connected customers by identifying
properties that may aid in determining this data point. A table was identified
named “Loads”, described in [fig:loads_schema]Figure  which references
connected customers on each phase and links to the “InstSection” table via the
“SectionId” property. We introduce some formal notation to define our customer
estimation method: $L$ is the set of all load records in the Loads table. Each
load record $l$ in $L$ contains attributes section ID and number of customers
per phase. $C_{\phi,i}$ is the set of customers connected to a specific phase
($\phi\in{RST}$) within a network section $i$ and $S_{i}$ is the set of total
customers within network section $i$. To estimate the total customers in a
section, we take the union of customers across all phases which can be
mathematically represented as; S_i = ⋃_ϕ∈RST C_ϕ, i This means that the total
customers in a section $i$ is the combined count of customers connected to its
$R$-phase, $S$-phase, and $T$-phase.

[width=0.35]fig_inst_loads_schema.pdf

Figure : Loads Schema

By correlating and appending the “Phase$<$N$>$Customers” to each “InstSection”
it is possible to see an approximation of customers per section of network.
The word “approximation” is important to note here however, as specific
sections of network had a large number of customers, while viewing these
locations via satellite perspective showed a low number of buildings in the
area, one possibility is that these may be industrial, farming or other large
customers which are treated differently within the GIS system. Accounting for
these outliers, a total number of customers was added as a property to on pole
circuit breaker assets in the data, to allow for the collection of customer
and CML related metrics.

###  Definition of node model

For the Irish network, assets such as on pole circuit breakers are identified
with a unique SCADA identifier, LBFM switches are denoted with an “S”
identifier e.g., S514, with Reclosers denoted with an “R” e.g., R341. Assets
that communicate with the DSO SCADA system are given an additional identifier
which maps to their SCADA identification, named an ASDU (Application Service
Data Unit). The relevant properties ascertained from the entities included in
the GIS data, supplemented with the approximated customers and SCADA specific
identifiers, formed the properties of each object in the graph database. Here
we formulate a robust framework for Fault Detection for the FLISR platform;
Let $S$ be the set of all intelligent switching devices (ISDs) on the
distribution grid, also known as Fault Line Current Limiters (FLCLs) or
reclosers. These devices are equipped with Fault Passage Indicators (FPIs) and
Loss of Voltage Indicators (LVIs) to enable fault detection and isolation.
Let, $s\in S$ be an individual switch (ISD) belonging to the set of switches
$S$. Each switch $s$ is characterized by its current operational state (open
or closed), its configuration (normally open or normally closed), and the
status of its FPI and LVI indicators. $FPI(s)$ is a Boolean function that
returns True if the Fault Passage Indicator has been triggered on switch $s$,
indicating that the current flowing through the switch has exceeded a
predefined threshold, suggesting a fault on the line segment controlled by the
switch. Otherwise, the function returns False. $LVI(s)$ is a Boolean function
that returns True if the Loss of Voltage Indicator has been triggered on
switch $s$, signifying a voltage drop below a certain threshold on the line
segment controlled by the switch. This could be caused by a fault or other
grid disturbances. Otherwise, the function returns False. $NO(s)$ is a Boolean
function that returns True if the switch $s$ is configured as a normally open
point. The function returns False if the switch is configured as normally
closed. Using this notation, we can express the decision rules more formally:

  * •

Rule 1: Isolation of Faulted Section: This rule prioritizes isolating the
faulted section of the grid. If both the FPI and LVI are triggered on a switch
$s$, it signifies a high probability of a fault on the line segment controlled
by that switch. In this scenario, the decision rule instructs the system to
open the switch $s$ (Open($s$)), effectively isolating the fault and
preventing further propagation of the fault current. This can be formally
expressed as: ∀s ∈S, (FPI(s) ∧LVI(s)) Open(s)

  * •

Rule 2: Maintaining Power Delivery: The next rule ensures continuity of power
supply to healthy sections. If a Loss of Voltage (LVI) is detected on a switch
configured as a normally closed point ($\neg NO(s)$), it indicates a potential
fault downstream. However, opening the switch in this case could unnecessarily
isolate healthy loads. Therefore, the rule dictates that the switch s should
remain closed (Closed(s)) to maintain power delivery to healthy sections. This
is formally expressed as: ∀s ∈S, (LVI(s) ∧¬NO(s)) Closed(s)

  * •

Rule 3: Recloser Operation: The final rule addresses normally open switches
(NO(s)). If a Loss of Voltage (LVI) is detected on a normally open switch, the
rule instructs the system to close the switch (Close(s)) in anticipation of a
potential transient fault clearing. This is formally expressed as: ∀s ∈S,
(LVI(s) ∧NO(s)) Close(s)

##  Network Simulation Platform

The FLISR Edge simulation platform enables the simulation of fault events
serves to both test and evaluate the FLISR algorithms in lieu of actual
hardware, these simulations are based on the distribution grid topologies
obtained from the GIS dataset. The simulation platform leverages a micro-
service architecture, in addition these services are hosted within a
containerised environment to enable simple deployment on either local systems
or remote host [7436659]. [fig:sim_arch]Figure  describes the architecture
implemented for the simulation platform.

[width=0.5]fig_network_sim_platform.pdf

Figure : FLISR Edge simulation platform architecture

##  Overview of Trial Site Topologies

The distribution grids investigated throughout the development of the FLISR
Edge solution, are dispersed throughout Ireland, located in County Waterford,
County Kerry and County Westmeath and this section will describe these trial
sites in terms of their structure.

###  Trial site 1 topology

The distribution grid located in Waterford is complex, consisting of an
intricate mesh network as presented in [fig:waterford_site]Figure . This
network is fed by three substations, with a total of eighteen on pole circuit
breakers installed, consisting of fifteen LBFM switches and three Reclosers.
Taking into account the sites complexity and proximity to the coastline, there
is a higher likelihood of fault events due to inclement weather and as such
would be suitable candidate for testing a FLISR solution in the field.

[width=0.38]fig_waterford_trial.pdf

Figure : Waterford trial site circuitry

###  Trial site 2 topology

The distribution grid located in Kerry is situated by the coastline, fed at
both ends via substation, with a total of eight Recloser switches, the
circuitry and visualisation of this network is illustrated in
[fig:kerry_site]Figure . Due to the structure of this network, there is a
narrow scope to back feed supply in the event of a fault, and with its remote
nature it is likely that network connectivity is limited, particularly in
higher areas and mountainous valleys, making it a suitable use case for
installation of edge devices to provide distributed FLISR functionality.

[width=0.5]fig_inst_kerry_circuitry.pdf

Figure : Kerry trial site circuitry

###  Trial site 3 topology

The distribution network located in Mullingar consists of two substations, and
seven Recloser switches installed, [fig:mullingar_site]Figure  presents the
circuitry and visualisation of the site. Two of the Reclosers are located at
the boundary of the network and serve as normally open points, providing
opportunity for back feeding energy supply from adjoining networks. Its
location in the midlands likely leads to relatively strong network coverage
and a number of fault events that are more representative of the country at
large and therefore would serve as an ideal location to test the operation of
a FLISR solution in a less unpredictable network.

[width=0.35]fig_mullingar_trial.pdf

Figure : Mullingar trial site circuitry

##  FLISR Edge solution

The FLISR Edge solution consists of two applications of the FLISR concept, one
of which is a centralized implementation deployed in a remote location, such
as the DSOs own systems, with the second deployed on LBFM and Recloser assets
by equipping them with an additional edge device running the distributed
algorithm, which can act independently if necessary. This builds on the
previous related research by expanding the capabilities of the FLISR
algorithm, introducing bi-directional communication to directly control
assets. In contrast, the previous iteration was limited to a simple generated
email which was forwarded to DSO personnel [10.12688/openreseurope.14115.2].
The additional edge device will require compatible interfaces to link with
existing equipment on the pole, sufficient processing capability to run the
application and cellular connectivity to process data and control signals.
With the rising popularity of low-cost and Edge computing, coupled with the
growing rate of processing available to even low-power chips, the options
available to provision a low-cost Edge computing device is much higher than in
the previous decade [8016573]. When considering a network such as Waterford,
the cost of retrofitting existing LBFM switches with Reclosers to enable loop
automation, costs 61,900 euros per unit according to ESB Networks 2023
standard prices report [Networks_2023]. In comparison, exploring the
application of low-cost Edge computing devices to enable loop automation on
existing assets appears more financially feasible. Assets equipped with
switching hardware consist of a number of modules which allow for interfacing
with the DSOs SCADA system for data comms and enacting control operations on
the physical circuit breaker. At the core of this architecture is a Remote
Terminal Unit (RTU), which streams real-time status data to and from the
connected circuit breaker [6032722]. Communication with the DSOs SCADA system
conforms to the IEC 60870-5-101/104 protocol, based on TCP/IP communications
and enables basic control tasks between centralized control centers and
connected assets, through connection from the RTU to a IEC 101 Master & IEC
104 Server [6672100]. It is this IEC 104 server which provides the network
communications with the DSO SCADA system, as well as a number of interfaces to
connect external devices, including serial and Ethernet connectivity. It is
these physical ports that will enable connection with the edge device, allow
for the capture and parsing of the switch status messages without interfering
with the existing stream to the DSOs SCADA system. Within the context of the
FLISR Edge algorithms operation, the edge device will act as a relay to the
centralized FLISR algorithm. When network connectivity is available, switch
status messages are transmitted to the centralized algorithm via MQTT (Message
Queuing Telemetry Transport) a lightweight, bi-directional communication
protocol designed for resource constrained devices [7123563]. To enable this
interaction, an MQTT broker is deployed on the target system (e.g., DSO
systems) which connects to the centralized FLISR algorithm, with the edge
device exposing an outward MQTT interface. Control messages generated by the
centralized FLISR algorithm are captured by the edge device and relayed to the
RTU. In the event that network communication is unavailable, the edge device
will leverage the local FLISR algorithm and pass the generated control message
to the RTU directly through the IEC 104 connection, outlined in
[fig:rtu_interaction]Figure .

[width=0.4] fig_rtu_communication.pdf

Figure : Edge device interfaces & interaction

Switch status and control messages to define actions to take (i.e.,
opening/closing of the circuit breaker) contain a number of data points, an
example is given below in JSON format. [caption=Switch Example Status
Message,captionpos=b] ”LinkAdd”: 1, ”ASDU_CA”: 51908, ”TypeID”: 30, ”IOA”: 4,
”Value”: ”0(OFF)” The properties in this data are, “ASDU_CA” which is the
identifier used by the DSO SCADA system to link the switch to its SCADA
identifier, “IOA” (Information Object Address) which defines the specific
input/output referenced on the switch, for example, the status of the power
supply, and finally “Value” with, “0(OFF)” mapping to “False”, with a value of
“1(ON)” mapping to “True”. As a general rule, any switch which gives an FPI
and LVI signal, due to physical damage, should be opened, and therefore the
damaged line or lines are no longer “live”. The FPI and LVI message format for
both a LBFM and Recloser switch are given below in addition to the
corresponding control message to open or close the circuit breaker.

  * •

LBFM switch FPI, LVI & control structure

The FPI value for a LBFM switch map to IOA 4, meaning a “Fault Current” has
been detected. [caption=Switch fault current status,captionpos=b] ”LinkAdd”:
1, ”ASDU_CA”: 51908, ”TypeID”: 30, ”IOA”: 4, ”Value”: ”1(ON)” The LVI value
maps to IOA 2, which specifies “AC Supply Fail”. [caption=Switch AC supply
fail status,captionpos=b] ”LinkAdd”: 1, ”ASDU_CA”: 51908, ”TypeID”: 30, ”IOA”:
2, ”Value”: ”1(ON)” An IOA value of 8 is used to open (“1(ON)”) or close
(”0(OFF)”) the circuit breaker. [caption=Switch C/B control
instruction,captionpos=b] ”LinkAdd”: 1, ”ASDU_CA”: 51908, ”TypeID”: 30, ”IOA”:
8, ”Value”: ”1(ON)”

  * •

Recloser switch FPI, LVI & control structure

The FPI value for a Recloser switch maps to an IOA of 27, specifying a “End of
Protection Sequence”. [caption=Recloser End of Protection Sequence
status,captionpos=b] ”LinkAdd”: 1, ”ASDU_CA”: 23089, ”TypeID”: 30, ”IOA”: 27,
”Value”: ”1(ON)” The LVI value maps to IOA 34 “Controller Locked Out”.
[caption=Recloser Controller Locked Out status,captionpos=b] ”LinkAdd”: 1,
”ASDU_CA”: 23089, ”TypeID”: 30, ”IOA”: 34, ”Value”: ”1(ON)” Finally, IOA 4096
is utilised to open (“1(ON)”) or close (”0(OFF)”) the circuit breaker.
[caption=Recloser C/B control instruction,captionpos=b] ”LinkAdd”: 1,
”ASDU_CA”: 23089, ”TypeID”: 30, ”IOA”: 4096, ”Value”: ”1(ON)” Based on what is
received (FPI and/or LVI) and the characteristics of the pole, an appropriate
control message is generated by FLISR and returned for a particular on pole
circuit breaker. Both the centralized and distributed FLISR algorithms are
implemented as lightweight containerised software services. Both algorithms
are defined in the Go language, due to its suitability for building
lightweight micro-services, performance and efficiency. A study by Dymora et
al. remarked that for processing small amounts of data, Go surpassed
comparable languages in terms of performance, CPU and memory utilisation
[app10238521], making it an ideal candidate for implementation of the FLISR
algorithms where reaction speed is paramount.


# On stability of the Erdős-Rademacher Problem

József Balogh 111Department of Mathematics, University of Illinois at Urbana-
Champaign, Urbana, Illinois 61801, USA, and Moscow Institute of Physics and
Technology, Russian Federation. E-mail<EMAIL_ADDRESS>Research is
partially supported by NSF Grant DMS-1764123, Arnold O. Beckman Research Award
(UIUC Campus Research Board RB 18132) and the Langan Scholar Fund (UIUC).
Felix Christian Clemen 222Department of Mathematics, University of Illinois at
Urbana-Champaign, Urbana, Illinois 61801, USA, E-mail<EMAIL_ADDRESS>
###### Abstract

Mantel’s theorem states that an $n$-vertex graph with $n$ vertices and
$\lfloor\frac{n^{2}}{4}\rfloor+t\ (t>0)$ edges contains a triangle.
Determining the minimum number of triangles of such graphs are usually
referred as Erdős-Rademacher’s problem type problems. Lovász and Simonovits’
proved that there are at least $t\lfloor n/2\rfloor$ triangles. Katona and
Xiao considered the same problem under the additional condition that there are
no $s$ vertices covering all triangles. They settled the case $t=1$ and $s=2$.
Solving their conjecture, we determine the minimum number of triangles for
general $s$ and $t$. Additionally, solving another conjecture of Katona and
Xiao, we extend the theory for considering cliques instead of triangles.

##  1 Introduction

A classical result in extremal combinatorics is Mantel’s theorem [8]. It says
that every $n$-vertex graph with at least $\lfloor\frac{n^{2}}{4}\rfloor+1$
edges contains a triangle. There have been various extensions of Mantel’s
theorem. Turán [9] generalized this result for cliques: Every $n$-vertex graph
with at least $t_{r}(n)+1$ edges contains a clique of size $r+1$, where
$t_{r}(n)$ is the number of edges of the complete balanced $r$-partite graph
on $n$ vertices. A result of Rademacher (see [2]) says that every graph on $n$
vertices with $\lfloor\frac{n^{2}}{4}\rfloor+1$ edges contains at least
$\lfloor\frac{n}{2}\rfloor$ triangles and this is best possible. Erdős [2, 3]
conjectured that an $n$-vertex graph with $\lfloor\frac{n^{2}}{4}\rfloor+t$
edges for $t<\frac{n}{2}$ contains at least $t\lfloor\frac{n}{2}\rfloor$
triangles. This was proven by Lovász and Simonovits [7]. Xiao and Katona [10]
proved a stability type of result of the Lovász and Simonovits result for
$t=1$: If there is no vertex contained in all triangles, then there are at
least $n-2$ triangles in $G$. We will prove two extensions of this statement,
one verifying a conjecture by Xiao and Katona [10] and the other one is
proving a slight modification of their other conjecture.

For a graph $G$ denote $e(G)$ the number of edges of $G$ and $T_{r}(G)$ the
number of copies of $K_{r}$ in $G$. A $K_{r}$-_covering set_ in $V(G)$ is a
vertex set that contains at least one vertex of every copy of $K_{r}$ in $G$.
The $r$-_clique covering number_ $\tau_{r}(G)$ is the size of the smallest
$K_{r}$-covering set. A _triangle covering set_ is a $K_{3}$-covering set and
the _triangle covering number_ is the $3$-clique covering number. Given a
vertex partition $V(G)=V_{1}\cup V_{2}\cup\ldots\cup V_{r}$, we call an edge
$e\in E(G)$ _class-edge_ if $e\in e(G[V_{i}])$ for some $i$ and _cross-edge_
otherwise. A set of two vertices $\\{x,y\\}$ is a _missing cross-edge_ if
$xy\not\in E(G),x\in V_{i},y\in V_{j}$ for some $i\neq j$. Denote
$e(V_{1},V_{2},\ldots,V_{r})$ the number of cross-edges and
$e^{c}(V_{1},V_{2},\ldots,V_{r})$ the number of missing cross-edges.

######  Conjecture 1.1 (Xiao, Katona [10]).

Let $t,s\in\mathbb{N}$ such that $0<t<s$. Suppose the graph $G$ has $n$
vertices and $\lfloor\frac{n^{2}}{4}\rfloor+t$ edges satisfying
$\tau_{3}(G)\geqslant s$ and $n\geqslant n(s,t)$ is large. Then $G$ contains
at least

$\displaystyle(s-1)\left\lceil\frac{n}{2}\right\rceil+\left\lfloor\frac{n}{2}\right\rfloor-2(s-t)$

many triangles.

Xiao and Katona [10] proved their conjecture for $t=1$ and $s=2$ and that it
is best possible. However, their conjecture in full generality holds only up
to an additive constant. We will determine precisely the minimum number of
triangles a graph on $n$ vertices with $\lfloor n^{2}/4\rfloor+t$ edges and
$\tau_{3}(G)\geqslant s$ can have. Depending on $s,t$ and $n$ one of the
following two constructions will be an extremal example.
Construction 1: Let $G_{1}$ be the graph on $n$ vertices $V(G_{1})=A\cup B$
with

$\displaystyle|A|=\left\lceil\frac{n}{2}\right\rceil+a,\quad|B|=\left\lfloor\frac{n}{2}\right\rfloor-a,$

where $a$ is chosen later to minimize the number of triangles in this
construction. Pick $2(s-1)$ vertices $x_{1},y_{1},\ldots,x_{s-1},y_{s-1}$ in
$A$ and two vertices $u_{1},u_{2}$ in $B$. Add the edges $\\{x_{i},y_{i}\\}$
and $\\{u_{1},u_{2}\\}$ to $K_{|A|,|B|}$ and delete the edges
$\\{u_{1},x_{1}\\},\ldots,\\{u_{1},x_{\alpha}\\}$, where
$\alpha:=s-t-a^{2}-\mathds{1}_{\\{2\nmid n\\}}a$. Then, $G_{1}$ has
$\lfloor\frac{n^{2}}{4}\rfloor+t$ edges, triangle covering number
$\tau_{3}(G_{1})=s$ and

$\displaystyle T_{3}(G_{1})$
$\displaystyle=(s-1)\left(\left\lfloor\frac{n}{2}\right\rfloor-a\right)+\left(\left\lceil\frac{n}{2}\right\rceil+a\right)-2\left(s-t-a^{2}-\mathds{1}_{\\{2\nmid
n\\}}a\right).$ (1)

Now, choose $a\geqslant 0$ satisfying $\alpha\geqslant 0$ and minimizing (1).
Remark that $G_{1}$ is similar to the construction of Xiao and Katona [10]
resulting in Conjecture 1.1, except that the class sizes are different in some
cases.
Construction 2: Let $G_{2}$ be the graph on $n$ vertices with two sets
$V(G_{2})=A\cup B$ with

$\displaystyle|A|=\left\lceil\frac{n}{2}\right\rceil+a,\quad|B|=\left\lfloor\frac{n}{2}\right\rfloor-a,$

where $a$ is chosen later to minimize the number of triangles in this
construction. Pick $2s$ vertices $x_{1},y_{1},\ldots,x_{s},y_{s}\in A$ and one
vertex $u\in B$. Add the edges $\\{x_{i},y_{i}\\}$ to $K_{|A|,|B|}$ and delete
the edges $\\{u,x_{1}\\},\ldots,\\{u,x_{\alpha}\\}$, where
$\alpha:=s-t-a^{2}-\mathds{1}_{\\{2\nmid n\\}}a$. The graph $G_{2}$ has
$\lfloor\frac{n^{2}}{4}\rfloor+t$ edges, triangle covering number
$\tau_{3}(G_{2})=s$ and

$\displaystyle
T_{3}(G_{2})=s\left(\left\lfloor\frac{n}{2}\right\rfloor-a\right)-\left(s-t-a^{2}-\mathds{1}_{\\{2\nmid
n\\}}a\right).$ (2)

Now, choose $a\geqslant 0$ satisfying $\alpha\geqslant 0$ and minimizing (2)

######  Theorem 1.2.

Let $t,s\in\mathbb{N}$ such that $0<t<s$. Suppose the graph $G$ has $n$
vertices and $\lfloor\frac{n^{2}}{4}\rfloor+t$ edges, it satisfies
$\tau_{3}(G)\geqslant s$ and $n\geqslant n(s,t)$ is large. Then $G$ contains
at least $\min\\{T_{3}(G_{1}),T_{3}(G_{2})\\}$ triangles.

Note that both $G_{1}$ and $G_{2}$ are achieving this minimum for some values
of $s$ and $t$. Xiao and Katona [10] also conjectured what the minimum number
of copies of $K_{r+1}$ a graph on $n$ vertices with $t_{r-1}(n)+1$ edges and
$\tau_{r+1}(G)\geqslant 2$ could be. They conjectured the following graph to
be an extremal example.
Construction 3: Let $G_{3}$ be the $n$ vertex graph with vertex partition
$V(G_{3})=V_{1}\cup V_{2}\cup\ldots\cup V_{r}$ where
$|V_{1}|\geqslant|V_{2}|\geqslant\ldots\geqslant|V_{r}|$ and
$|V_{1}|-|V_{r}|\leqslant 1$. Let $v_{1},v_{2}$ be two vertices in $V_{1}$ and
$u_{1},u_{3}$ in $V_{2}$. The graph $G_{3}$ is constructed from the complete
$r$-partite graph with partition $V_{1},\ldots,V_{r}$ by removing the edge
$\\{v_{1}u_{1}\\}$ and adding the edges $\\{v_{1},v_{2}\\}$ and
$\\{u_{1},u_{2}\\}$. This graph satisfies $\tau_{r+1}(G_{3})=2$,
$e(G_{3})=t_{r}(n)+1$ and

$\displaystyle T_{r+1}(G_{3})=(|V_{1}|+|V_{2}|-2)\prod_{i=3}^{r}|V_{i}|.$

We will verify their conjecture.

######  Theorem 1.3.

If a graph $G$ on $n$ vertices has $t_{r}(n)+1$ edges and the copies of
$K_{r+1}$ have an empty intersection, then the number of copies of $K_{r+1}$
is at least as many as in $G_{3}$.

The key ingredient for proving Theorem 1.2 and Theorem 1.3 is the following
general structural result.

######  Theorem 1.4.

Let $r,t,s\in\mathbb{N}$ with $0<t<s$ and suppose the graph $G$ has $n$
vertices and $t_{r}(n)+t$ edges satisfying $\tau_{r}(G)\geqslant s$ and
$n\geqslant n(s,t,r)$ is sufficiently large. Denote $\mathcal{H}$ the family
of graphs $H$ on $n$ vertices with vertex partition $V(H)=V_{1}\cup
V_{2}\cup\ldots\cup V_{r}$ where

  * •

the class-edges form a matching of size $s$,

  * •

$e^{c}(V_{1},\ldots,V_{r})\leqslant s-t$,

  * •

all missing cross-edges are incident to one of the class-edges,

  * •

if the class-edges are not all in the same class, then each missing cross-edge
is incident to class-edges on both endpoints.

Then $T_{r+1}(G)\geqslant T_{r+1}(H)$ for some $H\in\mathcal{H}$.

Remark that since

$\displaystyle
t_{r}(n)+t=e(G)=\prod_{i=1}^{r}|V_{i}|-e^{c}(V_{1},V_{2},\ldots,V_{r})+\sum_{i=1}^{r}e(G[V_{i}]),$

we get

$\displaystyle\prod_{i=1}^{r}|V_{i}|\geqslant t_{r}(n)-s$

and thus $|V_{i}|=n/r-O(1)$. Hence, the family $\mathcal{H}$ is finite. An
optimization argument will reduce this family to $G_{1}$ and $G_{2}$ in the
case $r=3$ and to $G_{3}$ in the case $r>3,s=2,t=1$. A similar cleaning
potentially could be done in the general case, however the computational
effort needed seems not to be in relation with the outcome. Also, it is likely
that for some parameters $r,t,s$, the extremal family realizing the minimum
number of cliques of size $r+1$ contains several graphs.
As pointed out in [10], the condition $0<t<s$ is not a real restriction,
because for $t\geqslant s$, $\tau_{r+1}(G)=t$ is allowed. From a result of
Erdős [4], we know that the number of cliques of size $r+1$ is at least
$t\left(\frac{n}{r}\right)^{r-1}(1+o(1))$ and the graph $G_{4}$ constructed by
adding a matching of size $t$ to one of the classes of the complete balanced
$r$-partite graph on $n$ vertices satisfies $\tau_{r+1}(G_{4})=t$ and
$T_{r+1}(G_{4})=t\left(\frac{n}{r}\right)^{r-1}(1+o(1))$.
We could have extended our result when $s$ and $t$ is a function of $n$. In
particular, in the triangle case $r=3$, our proof allows $s$ to be linear in
$n$. However, the methods we use, especially our main tool Theorem 2.1 will
not give us the entire range of $s$ where our theorem should hold. Thus, we
decided not to optimize our proof with respect of the dependency of $n$ and
$s$.
Our main tool is a stability-supersaturation result by Balogh, Bushaw,
Collares, Liu, Morris and Sharifzadeh [1], which extends on the Erdős-
Simonovits stability theorem [5] and Füredi’s [6] proof’s of it. In Section 2
we prove Theorem 1.4, in Section 3 we conclude Theorem 1.2 and in Section 4 we
deduce Theorem 1.3.

##  2 Proof of Theorem 1.4

We say that a graph $G$ is $x$-_far from being $r$-partite_ if
$\chi(G^{\prime})>r$ for every subgraph $G^{\prime}\subset G$ with
$e(G^{\prime})>e(G)-x$. Balogh, Bushaw, Collares, Liu, Morris and Sharifzadeh
[1] proved that graphs which are $x$-far from being $r$-partite, contain many
cliques of size $r+1$.

######  Theorem 2.1 ([1]).

For every $n,t,r\in\mathbb{N}$, the following holds. Every graph $G$ on $n$
vertices which is $x$-far from being $r$-partite contains at least

$\displaystyle\frac{n^{r-1}}{e^{2r}r!}\left(e(G)+x-\left(1-\frac{1}{r}\right)\frac{n^{2}}{2}\right)$

copies of $K_{r+1}$.

###### Proof of Theorem 1.4.

Let $G$ be a graph on $n$ vertices and $t_{r}(n)+1$ edges such that the copies
of $K_{k}$ have an empty intersection and $n$ is large enough. If $G$ is
$2sr!e^{2r}$-far from being $r$-partite, then by applying Theorem 2.1, $G$
contains at least

$\displaystyle\frac{n^{r-1}}{r!e^{2r}}\left(t_{r}(n)+1+2sr!e^{2r}-\left(1-\frac{1}{r}\right)\frac{n^{2}}{2}\right)\geqslant
sn^{r-1}$

copies of $K_{r+1}$. For $H\in\mathcal{H}$, $T_{r+1}(H)\leqslant
sn^{r-1}\leqslant T_{r+1}(G)$, because each of the $s$ class-edges of $H$ is
contained in at most $n^{r-1}$ copies of $K_{r+1}$. Thus we can assume that
$G$ is not $2sr!e^{2r}$-far from being $r$-partite. Hence, there exists a
subgraph $G^{\prime}\subset G$ with $\chi(G^{\prime})\leqslant r$ and
$e(G^{\prime})>e(G)-2sr!e^{2r}s>t_{r}(n)-2sr!e^{2r}$. Let
$V(G^{\prime})=V_{1}\cup V_{2}\cup\ldots\cup V_{r}$ be a partition such that
$V_{1},V_{2},\ldots,V_{r}$ are independent sets in $G^{\prime}$ and
$|V_{1}|\geqslant|V_{2}|\geqslant\ldots\geqslant|V_{r}|$. We have
$|V_{1}|\leqslant n/r+\sqrt{n}$, because otherwise

$\displaystyle
t_{r}(n)-2sr!e^{2r}<e(G^{\prime})\leqslant\prod_{i=1}^{r}|V_{i}|\leqslant\left(\frac{n}{r}+\sqrt{n}\right)\left(\frac{n}{r}-\frac{\sqrt{n}}{r-1}\right)^{r-1}\leqslant
t_{r}(n)-2sr!e^{2r},$

a contradiction. Similarly, we have $|V_{r}|\geqslant n/r-\sqrt{n}$. Since
$G^{\prime}\subset G$, and $e(G^{\prime})>e(G)-2sr!e^{2r}$ there are at most
$2sr!e^{2r}$ class-edges. If the number of class-edges is less than $s$, then
there is a $K_{r+1}$\- covering set of size at most $s-1$, contradicting
$\tau_{r+1}(G)\geqslant s$. Now, assume that there are more than $s$ class-
edges. Each edge inside a class is contained in at least
$(\frac{n}{r}-\sqrt{n}-2sr!e^{2r})^{r-1}$ cliques of size $r+1$, because in
each class there are at least $\frac{n}{r}-\sqrt{n}-2sr!e^{2r}$ vertices not
incident to a missing cross-edge. Further, all these cliques are different. In
total we have

$\displaystyle
T_{r+1}(G)\geqslant(s+1)\left(\frac{n}{r}-\sqrt{n}-2sr!e^{2r}\right)^{r-1}\geqslant\left(s+\frac{1}{2}\right)\left(\frac{n}{r}\right)^{r-1},$

which is more than $T_{r+1}(H)$ for every $H\in\mathcal{H}$. Thus, we can
assume that the number of class-edges is $s$. These $s$ edges need to a form a
matching, otherwise there is a $K_{r+1}$-covering set of size $s-1$,
contradiction $\tau_{r+1}(G)\geqslant s$. Further,
$e^{c}(V_{1},\ldots,V_{r})\leqslant s-t$, because otherwise

$\displaystyle e(G)$
$\displaystyle=e(G[V_{1},V_{2},\ldots,V_{r}])+\sum_{i=1}^{r}e(G[V_{i}])\leqslant
t_{r+1}(n)-e^{c}(V_{1},V_{2},\ldots,V_{r})+s$
$\displaystyle<t_{r+1}(n)+t=e(G).$

Next, we assume that there is a missing cross-edge $uv\not\in E(G)$ not
incident to one of the class-edges. Take a cross-edge $xy\in E(G)$ which is
incident to exactly one class-edge. We will show that $T_{r+1}(G+uv-
xy)<T_{r+1}(G)$. Adding $uv$ to $G$ increases the number of cliques of size
$r+1$ by at most

$\displaystyle s\cdot\max|V_{i}|^{r-3}\leqslant
s(n/r+\sqrt{n})^{r-1}=O(n^{r-3}),$

because for each of the $s$ class-edges $e$ the number of cliques of size
$r+1$ containing $e$ is increased by at most $\max|V_{i}|^{r-3}$. Removing
$xy$ from $G+uv$ decreases the number of cliques of size $r+1$ by at least

$\displaystyle\min(|V_{i}|-s)^{r-2}\geqslant(n/r-\sqrt{n}-s)^{r-2}=\Omega(n^{r-2}),$

where we used that in each class $V_{i}$ the number of vertices incident to no
missing cross-edge is at least $V_{i}-s$. Thus, performing this edge flip
decreases the number of cliques of size $r+1$, i.e. $T_{r+1}(G+uv-
xy)<T_{r+1}(G)$. We repeat this process until we end up with a graph $H$ such
that $T_{r+1}(H)\leqslant T_{r+1}(G)$ and every missing cross-edge is incident
to a class-edge.
Now, assume that $G$ has the property that not all class-edges are in the same
class and there is a missing cross-edge not adjacent to class-edges on both
ends. Denote $G^{\prime}$ be the graph constructed from $G$ by adding all
missing cross-edges. This graph satisfies

$\displaystyle T_{r+1}(G^{\prime})$ $\displaystyle\leqslant
T_{r+1}(G)+\left(2e^{c}(V_{1},V_{2},\ldots,V_{r})-1\right)\left(\frac{n}{r}+\sqrt{n}\right)^{r-2}+se^{c}(V_{1},V_{2},\ldots,V_{r})\left(\frac{n}{r}\right)^{r-3}$
$\displaystyle\leqslant
T_{r+1}(G)+\left(2e^{c}(V_{1},V_{2},\ldots,V_{r})-1\right)\left(\frac{n}{r}\right)^{r-2}(1+o(1)),$

because for each class edge, the number of cliques of size $r+1$ increases by
at most

$\displaystyle
N\left(\frac{n}{r}+\sqrt{n}\right)^{r-2}+e^{c}(V_{1},V_{2},\ldots,V_{r})\left(\frac{n}{r}+\sqrt{n}\right)^{r-2},$

where $N$ is the number of incident edges being added. There is a set $M$ of
$e^{c}(V_{1},V_{2},\ldots,V_{r})\leqslant s-1$ cross-edges such that each
$e\in M$ is incident to class edges on both endpoints and every class edge is
incident to edges of $M$ on at most one endpoint. Denote $G^{\prime\prime}$
the graph constructed from $G^{\prime}$ by removing those edges. This graph
satisfies

$\displaystyle T_{r+1}(G^{\prime\prime})\leqslant
T_{r+1}(G^{\prime})-2e^{c}(V_{1},V_{2},\ldots,V_{r})\left(\frac{n}{r}-\sqrt{n}-s\right)^{r-2}\leqslant
T_{r+1}(G).$

$\blacksquare$

##  3 Proof of Theorem 1.2

###### Proof of Theorem 1.2.

By Theorem 1.4, we can assume that $G$ has a vertex partition $V(G)=A\cup B$
where $|A|\geqslant|B|$ and exactly $s$ edges are inside the classes. Let
$|A|=\lceil n/2\rceil+a,|B|=\lfloor n/2\rfloor-a$ for some $a\geqslant 0$. We
have

$\displaystyle\left\lfloor\frac{n^{2}}{4}\right\rfloor+t=e(G)=|A||B|-e^{c}(A,B)+s=\left(\left\lceil\frac{n}{2}\right\rceil+a\right)\left(\left\lfloor\frac{n}{2}\right\rfloor-a\right)-e^{c}(A,B)+s,$

and thus the number of missing cross-edges is

$\displaystyle e^{c}(A,B)=\begin{cases}s-t-a^{2},&\text{ iff }n\text{ is
even,}\\\ s-t-a-a^{2},&\text{ iff }n\text{ is odd.}\end{cases}$

Let $M_{A}$ be the matching of class-edges inside $A$ and $M_{B}$ be the
matching of class-edges inside $B$. Denote $G^{\prime}$ be the graph
constructed from $G$ by adding all missing cross-edges $e^{c}(A,B)$. The
number of triangles in this graph is $|M_{A}||B|+|M_{B}||A|$.
Case 1: $|M_{B}|>0$.
The number of triangles in $G$ is at least
$|M_{A}||B|+|M_{B}||A|-2e^{c}(A,B)$, because each missing cross-edge is in at
most two triangles in $G^{\prime}$. Since $|A|\geqslant|B|$, we get

$\displaystyle
T_{3}(G)\geqslant(s-1)\left(\left\lfloor\frac{n}{2}\right\rfloor-a\right)+\left(\left\lceil\frac{n}{2}\right\rceil+a\right)-2e^{c}(A,B).$

Hence,

$\displaystyle
T_{3}(G)\geqslant(s-1)\left(\left\lfloor\frac{n}{2}\right\rfloor-a\right)+\left(\left\lceil\frac{n}{2}\right\rceil+a\right)-2\left(s-t-a^{2}-\mathds{1}_{\\{2\nmid
n\\}}a\right)\geqslant T_{3}(G_{1}).$

Case 2: $|M_{B}|=0$.
The number of triangles in $G$ is at least $|M_{A}||B|-e^{c}(A,B)$, because
each missing cross-edge is in at most one triangle in $G^{\prime}$. Therefore

$\displaystyle T_{3}(G)$
$\displaystyle\geqslant|M_{A}||B|-e^{c}(A,B)=s\left(\left\lfloor\frac{n}{2}\right\rfloor-a\right)-\left(s-t-a^{2}-\mathds{1}_{\\{2\nmid
n\\}a}\right)\geqslant T_{3}(G_{2}).$

$\blacksquare$

##  4 Proof of Theorem 1.3

Let $n=rm+\ell$, where $0\leqslant\ell<r$. The number of cliques of size $r+1$
in $G_{3}$ is

$\displaystyle
T_{r+1}(G_{3})=(|V_{1}|+|V_{2}|-2)\prod_{i=3}^{r}|V_{i}|=\begin{cases}2m(m+1)^{\ell-2}m^{r-\ell}&,\text{
iff }2\leqslant\ell\leqslant r-1,\\\ \left(2m-1\right)m^{r-2}&,\text{ iff
}\ell=1,\\\ \left(2m-2\right)m^{r-2}&,\text{ iff }\ell=0.\\\ \end{cases}$

###### Proof of Theorem 1.3.

By applying Theorem 1.4 for $s=2$ and $t=1$, we can assume that
$G\in\mathcal{H}$ and thus has a vertex partition $V(G)=V_{1}\cup
V_{2}\cup\ldots\cup V_{r}$ where
$|V_{1}|\geqslant|V_{2}|\geqslant\dots\geqslant|V_{r}|$ with exactly two
class-edges $e_{1},e_{2}$ and at most one missing cross-edge. We have

$\displaystyle\prod_{i=1}^{r}|V_{i}|-e^{c}(V_{1},V_{2},\ldots,V_{r})+2=e(G)=t_{r}(n)+1,$

and thus $\prod_{i=1}^{r}|V_{i}|=t_{r}(n)-1+e^{c}(V_{1},V_{2},\ldots,V_{r})$.
This means we have two cases: $\prod_{i=1}^{r}|V_{i}|=t_{r}(n)$ or
$\prod_{i=1}^{r}|V_{i}|=t_{r}(n)-1$.
Case 1: $\prod_{i=1}^{r}|V_{i}|=t_{r}(n)-1$.
In this case there are no missing cross-edges, i.e.
$e^{c}(V_{1},V_{2},\ldots,V_{r})=0$. There are two types of combination of
class sizes.

  * •

Type 1: $|V_{1}|=m+2$, $|V_{2}|=\ldots=|V_{\ell-1}|=m+1$,
$|V_{\ell}|=\ldots=|V_{r}|=m$,

  * •

Type 2: $|V_{1}|=\ldots=|V_{\ell+1}|=m+1$, $|V_{\ell+2}|=\ldots=|V_{r-1}|=m$,
$|V_{r}|=m-1$.

Let the two class-edges be in $V_{\alpha}$ and $V_{\beta}$ for
$1\leqslant\alpha\leqslant\beta\leqslant r$. We have

$\displaystyle
T_{r+1}(G)=\prod_{i\neq\alpha}|V_{i}|+\prod_{i\neq\beta}|V_{i}|\geqslant
2\prod_{i=2}^{r}|V_{i}|\geqslant T_{r+1}(G_{3}).$

Case 2: $\prod_{i=1}^{r}|V_{i}|=t_{r}(n)$.
Remark that in this case the class sizes of $G$ and $G_{3}$ are the same.
Further, the number of missing cross-edges is exactly one. Now, we distinguish
two cases depending on where $e_{1}$ and $e_{2}$ are. Case $2$a is when both
class-edges are inside the same class. In Case $2$b, $e_{1}$ and $e_{2}$ are
in different classes.
Case 2a: $e_{1},e_{2}\subseteq V_{\alpha}$ for some $1\leqslant\alpha\leqslant
r.$
The missing edge is incident to $e_{1}$ or $e_{2}$, say the second endpoint of
the missing edge is in $V_{\beta}$. Then

$\displaystyle T_{r+1}(G)$
$\displaystyle=2\prod_{i\neq\alpha}|V_{i}|-\prod_{i\neq\alpha,\beta}|V_{i}|=(2|V_{\beta}|-1)\prod_{i\neq\alpha,\beta}|V_{i}|$
$\displaystyle\geqslant(|V_{\alpha}|+|V_{\beta}|-2)\prod_{i\neq\alpha,\beta}|V_{i}|\geqslant(|V_{1}|+|V_{2}|-2)\prod_{i=3}^{r}|V_{i}|=T_{r+1}(G_{3}),$

where the sum of the factors are the same in the two products, hence the
product is larger when the factors are ’closer’ to each other.

Case 2b: $e_{1}\subseteq V_{\alpha},e_{2}\subseteq V_{\beta}$ for some
$\alpha\neq\beta$.
Since the missing edge is incident to both class edges,

$\displaystyle T_{r+1}(G)$
$\displaystyle=(|V_{\beta}|-1)\prod_{i\neq\alpha,\beta}|V_{i}|+(|V_{\alpha}|-1)\prod_{i\neq\alpha,\beta}|V_{i}|=(|V_{\alpha}|+|V_{\beta}|-2)\prod_{i\neq\alpha,\beta}|V_{i}|$
$\displaystyle\geqslant(|V_{1}|+|V_{2}|-2)\prod_{i=3}^{r}|V_{i}|=T_{r+1}(G_{3}),$

where the last inequality holds by the same reasoning as in Case $2$a.

$\blacksquare$

## References

  * [1] J. Balogh, N. Bushaw, M. Collares, H. Liu, R. Morris, and M. Sharifzadeh.  The typical structure of graphs with no large cliques.  Combinatorica, 37(4):617–632, 2017.
  * [2] P. Erdős.  Some theorems on graphs.  Riveon Lematematika, 9:13–17, 1955.
  * [3] P. Erdős.  On a theorem of Rademacher-Turán.  Illinois J. Math., 6:122–127, 1962.
  * [4] P. Erdős.  On the number of complete subgraphs and circuits contained in graphs.  Časopis Pěst. Mat., 94:290–296, 1969.
  * [5] P. Erdős and M. Simonovits.  A limit theorem in graph theory.  Studia Sci. Math. Hungar, 1:51–57, 1966.
  * [6] Z. Füredi.  A proof of the stability of extremal graphs, Simonovits’ stability from Szemerédi’s regularity.  J. Combin. Theory Ser. B, 115:66–71, 2015.
  * [7] L. Lovász and M. Simonovits.  On the number of complete subgraphs of a graph. II.  In Studies in pure mathematics, pages 459–495. Birkhäuser, Basel, 1983.
  * [8] W. Mantel.  Problem 28.  Wiskundige Opgaven, 10:60–61, 1907.
  * [9] P. Turán.  Eine Extremalaufgabe aus der Graphentheorie.  Mat. Fiz. Lapok, 48:436–452, 1941.
  * [10] C. Xiao and G. O. H. Katona.  The number of triangles is more when they have no common vertex.  arXiv preprint: https://arxiv.org/abs/2003.04450, 2020.