Multi-Stage Linear Decision Rules for Stochastic Control of Natural Gas Networks with Linepack

Vladimir Dvorkin1,
Dharik Mallapragada1,
Audun Botterud1,
Jalal Kazempour2 and
Pierre Pinson2
1Massachusetts Institute of Technology, Cambridge, MA, USA.
2Technical University of Denmark, Kng. Lyngby, Denmark.

The disturbances from variable and uncertain renewable generation propagate from power systems to natural gas networks, causing gas network operators to adjust gas supply nominations to ensure operational security. To alleviate expensive supply adjustments, we develop control policies to leverage instead the flexibility of linepack – the gas stored in pipelines – to balance stochastic gas extractions. These policies are based on multi-stage linear decision rules optimized on a finite discrete horizon to guide controllable network components, such as compressors and valves, towards feasible operations. Our approach  offers several control applications. First, it treats the linepack as a main source of flexibility to balance disturbances from power systems without substantial impacts on nominal gas supply. Second, these policies can be optimized to minimize the variability (due to intermittency of renewables) and variance (due to their uncertainty) of network state variables, such as pressures. Finally, it enables topology optimization to decouple network parts and prevent uncertainty propagation through the network. This is demonstrated using illustrative numerical experiments.

Integrated energy systems, linear decision rules,  natural gas linepack, stochastic control, topology optimization.

Vladimir Dvorkin and Dharik Mallapragada acknowledge funding from the MIT Energy Initiative Low-Carbon Energy Center on Electric Power Systems.

§ INTRODUCTION

In many countries, balancing stochastic renewable generation in power systems relies on the flexibility of gas-fired power plants that couple power and natural gas systems. The disturbances from variable and uncertain renewables thus propagate to natural gas networks, causing  network  operators  to  adjust gas supply nominations to ensure   gas deliverability across the network. Such measures, however, are expensive and may not suffice to cope with weather-dependent gas extractions in the future. This motivates seeking alternative flexibility sources to control natural gas networks.

Natural gas linepack – temporally pressurized gas stored in pipelines – has traditionally provided long-term flexibility for network operators (e.g., month-long storage), but more recently it has been modeled within shorter operational time frames. According to <cit.> and <cit.>, linepack flexibility has a potential to save up to 1.4% to 2.0% of deterministic day-ahead scheduling cost. In the systems exposed to uncertainty, this cost saving potential increases up to 3.5% on average <cit.>. The linepack flexibility also enables cost-security trade-offs in the stochastic dispatch of power and natural gas systems <cit.>.

The linepack models in <cit.> and <cit.>, however, provide flexibility in the interest of stochastic day-ahead scheduling. As two-stage stochastic programs, they co-optimize nominal set-points and reserve margins that immunize future operations against uncertainty. Unfortunately, those models do not answer how to control the uncertain system state (e.g., nodal pressures and gas flows) as that uncertainty gradually realizes throughout the control (operating) horizon. Such a control task requires a multi-stage stochastic modeling of network state, i.e., optimizing the network state as a function of all prior uncertainty realizations at any given stage, which is computationally challenging <cit.>. This problem is thus typically limited to two subsequent stages <cit.> or enjoys overly-conservative robust optimization techniques that disregard the temporal evolution of the stochastic renewable generation process <cit.>.

In contrast to scheduling problems, this paper develops multi-stage stochastic control policies for natural gas networks with linepack and offers their computationally efficient optimization. Specifically, the following contributions are made:

* We develop multi-stage policies for controllable network assets that invoke linepack flexibility to guide operations within a finite discrete control horizon. These policies are based on multi-stage linear decision rules <cit.> that model uncertain network state through random trajectories and produce control inputs to maintain those trajectories within technical limits, hence expanding a two-stage stochastic control horizon modeled in <cit.>.

* We provide a distributionally robust chance-constrained optimization problem and its second-order cone program (SOCP) reformulation to optimize multi-stage control policies. We use the exact reformulation of double-sided distributionally robust constraints from <cit.> to reduce the conservatism of models in <cit.>.

* We provide several applications for the proposed multi-stage control policies in the sequential system coordination setting, where power system dispatch is followed by the gas network optimization problem. We find out that:

a) The linepack flexibility suffices to balance stochastic extractions without substantial adjustments of the nominal gas injections. Invoking linepack flexibility in a 48-node network, we show that the standard deviation of stochastic gas extractions of 7.2% of their nominal value can be accommodated while limiting the standard deviation of gas injections to 2.5% of their nominal value. The cost-saving potential of linepack storage in our setting amounts to 10.3% in expectation.

b) The proposed multi-stage control policies can be optimized to simultaneously minimize the variability (due to intermittency of renewable generation) and the variance (due to uncertainty) of the network state, thus improving on the variance-only control in <cit.>.

c) Recognizing the role of network effects, the proposed control policies are additionally co-optimized with the binary valve deployment to identify the optimal network topology, which limits spatio-temporal disturbance propagations within a control horizon.

Paper Organization: Section <ref> introduces the gas network equations and uncertainty model. Section  <ref> presents a chance-constrained multi-stage policy optimization problem, its tractable reformulation, and several applications. Section <ref> provides numerical experiments and Section <ref> concludes.

Notation: lower- (upper-) case letters denote column vectors (matrices). $\mathbb{0}$ and $\mathbb{1}$ denote vectors (matrices) of zeros and ones; when ambiguous, their dimension is provided with a subscript. Operator $\text{dg}[x]$ returns a diagonal $n\times n$ matrix with diagonal entries of $n-$dimensional vector $x$,
operator $[A]_{i}$ returns an $i$th row $(1 \times n)$ of matrix $A$, operator $\text{Tr}[A]$ denotes matrix trace, and symbol $^\top$ stands for transposition. $\norm{\cdot}$ denotes $\ell_{2}-$norm. Boldface font denotes random variables and $\tilde{x}$ denotes the dependency of $x$ on random variables.

§ PRELIMINARIES

[Compressor model]

[gray,dashed] (0,-1.75) – (4,-1.75);
[gray,dashed] (2,-1.15) – (8,-1.15);
[gray,dashed] (4,-1.75) – (9,-1.75);
[gray,dashed] (6,-0.75) – (9,-0.75);
[line width=0.15mm, ->, >= stealth, black] (9,-1.75) – (9,-0.75) node[midway,right]$\kappa_{\ell}$;

[line width=0.25mm, black] (0,0) node[] $\bullet$ node[above]$n$ – (2,0) node[] $\bullet$ node[above]$m$;

[xshift = 0cm, yshift = 0cm]
[dashed,line width=0.25mm] node[yshift=-1.75cm] $\bullet$ node[yshift=-1.45cm] $\varrho_{n}$ plot[domain=0:2,yshift=-0.75cm]   (,0.5*-exp(0.1*^1.75)) node[yshift=-0.75cm] $\bullet$ node[yshift=-0.45cm] $\varrho_{m}$;

[black] (3.0,-0.6) node $\Longleftrightarrow$;

[line width=0.25mm, black] (4,0) node[] $\bullet$ node[above]$n$ – (6,0) node[] $\bullet$ node[above]$n'$;

[line width=0.25mm, black] (6,0) – (8,0) node[] $\bullet$ node[above]$m$;

[xshift = 4cm, yshift = -1.75cm]
[dashed,line width=0.25mm] node[above] $\varrho_{n}$ node[] $\bullet$ plot[domain=0:2]   (,0.5*) node[above] $\varrho_{n'}$ node[] $\bullet$;

[xshift = 6cm, yshift = 0.25cm]
[dashed,line width=0.25mm] plot[domain=0:2] (1*,-exp(0.1*^1.75)) node[above] $\varrho_{m}$ node[] $\bullet$;

[Linepack model ]

[cylinder, line width=0.25mm, black, shape border rotate=0, draw,minimum height=4cm,minimum width=1.65cm]

[line width=0.25mm,gray] (-1.9,0)  – (-1,0);
[line width=0.25mm,gray] (1,0)  – (1.85,0);
[decorate,decoration=zigzag,segment length=1mm, amplitude=1mm,line width=0.25mm,gray] (-1,0) – (1,0);
[line width=0.25mm,gray,->,>=stealth] (-0.5,0.25) – node[above] $\textcolor{black}{\varphi_{\ell}}$ (0.5,0.25);
[decorate,decoration=brace,amplitude=5pt,xshift=0pt,yshift=0pt,line width=0.15mm,gray]
(1.0,-0.2) – (-1.0,-0.2) node [midway,below,yshift = -0.1cm]

[line width=0.25mm,black] (-2.25,0)  – (-1.9,0);
[line width=0.25mm,black,->,>=stealth] (-3.0,0)  node[] $\bullet$ node[left] $\varrho_{n}$ – (-2.20,0) node[above] $\varphi_{\ell}^{\shortplus}$;

[line width=0.25mm,black] (2.35,0) – (3.25,0) node[] $\bullet$ node[right] $\varrho_{m}$;
[line width=0.25mm,black,->,>=stealth] (1.85,0)  – (2.5,0) node[above] $\varphi_{\ell}^{\shortminus}$;

Modeling of pressure regulation (left) and linepack natural gas storage (right) and the corresponding notation.

§.§ Natural Gas Network Equations

Consider a gas network with the sets $\mathcal{N}=\{1,\dots,N\}$ of nodes and $\mathcal{E}=\{1,\dots,E\}$ of edges (pipelines) connecting those nodes. Each edge is assigned a direction from sending end $n$ to receiving end $m$, i.e., if $(n,m)\!\in\!\mathcal{E}$, then $(m,n)\!\notin\!\mathcal{E}$, but the flow is allowed to be negative. This topology is encoded in the node-edge incidence matrix $A\!\in\!\mathbb{R}^{N\times E}$ as

\begin{align*}
A_{k\ell} =
\left\{
\begin{array}{rl}
+1, & \text{if}\;k=n  \\
-1, & \text{if}\;k=m \\
0, & \text{otherwise}
\end{array}
\right.\quad\forall\ell=(n,m)\in\mathcal{E}.
\end{align*}

The gas network optimization problem identifies optimal gas injections $\vartheta\in\mathbb{R}^{N}$ that satisfy gas extractions $\delta\in\mathbb{R}_{+}^{N}$ across the network. Towards this goal, the network operator must maintain such nodal pressures $\varrho\in\mathbb{R}^{N}$ that do not prevent the gas flow $\varphi\in\mathbb{R}^{E}$ in the network. To support pressures, the network operator deploys active pipelines $\mathcal{E}_{a}\!\subseteq\!\mathcal{E}$ that host compressors $\mathcal{E}_{c}\!\subseteq\!\mathcal{E}_{a}$ or control valves $\mathcal{E}_{v}\!\subseteq\!\mathcal{E}_{a}$, $\mathcal{E}_{c}\cap\mathcal{E}_{v}=\emptyset$, that support pressure in a continues manner <cit.>. A compressor edge $\ell=(n,m)\!\in\!\mathcal{E}_{c}$ is modeled as in Fig. <ref>, where the controllable compression rate $\kappa_{\ell}\geqslant0$ is followed by the non-linear pressure drop according to the Weymouth equation <cit.>. A valve edge $\ell\in\mathcal{E}_{v}$ is modeled similarly, but the linear decompression rate $\kappa_{\ell}$ always remains non-positive.

To regulate pressure, active pipelines consume gas according to conversion factors stored in matrix $B\in\mathbb{R}^{N\times E}$:

\begin{align*}
B_{k\ell} =
\left\{
\begin{array}{rl}
b_{\ell}, & \text{if}\;k=n,\;k\in\mathcal{E}_{c}  \\
-b_{\ell}, & \text{if}\;k=m,\;k\in\mathcal{E}_{v}  \\
0, & \text{otherwise}
\end{array}
\right.\quad\forall\ell=(n,m)\in\mathcal{E},
\end{align*}

where $b_{\ell}$ is a conversion factor from the regulation rate to gas mass. This gives rise to the following gas flow equations

\begin{align}
&A\varphi = \vartheta - B\kappa - \delta,\label{eq:conserv_law}\\
&\varphi_{\ell}|\varphi_{\ell}|=w_{\ell}\braceit{(\varrho_{n} + \kappa_{\ell})^2 - \varrho_{m}^2},&&\forall\ell=(n,m)\in\mathcal{E}, \label{eq:weymouth_eq}\\
&\varphi_{\ell}\geqslant 0,\;\forall\ell\in\mathcal{E}_{a},\label{eq:uni_direction}
\end{align}

where equation (<ref>) ensures gas mass conservation by balancing gas flows, injections and extractions, equation (<ref>) models the gas flow in pipelines using the Weymouth equation, where $w\in\mathbb{R}_{+}^{E}$ is the friction coefficient, and (<ref>) models unidirectional gas flow required for active pipelines only.

To model linepack, we adopt the notation in Fig. <ref>, where $\varphi_{\ell}^{\shortplus},\varphi_{\ell}$ and $\varphi_{\ell}^{\shortminus}$ respectively denote the inlet, midway and outlet gas flows, and $\psi_{\ell}$ denotes the amount of linepack. The linepack model in <cit.> couples these variables as

\begin{align}
&\varphi_{\ell} = \tfrac{1}{2}\braceit{\varphi_{\ell}^{\shortplus} + \varphi_{\ell}^{\shortminus}},\label{eq:mean_flow}\\
&\psi_{\ell} = \tfrac{1}{2}s_{\ell}\braceit{\varrho_{n}+\kappa_{\ell}+\varrho_{m}},\label{eq:line_pack_def}
\end{align}

where the first entry sets the midway flow as an average flow through the pipeline, and the second entry defines the linepack proportionally to the pressures at the sending and receiving ends, with $s_{\ell}\geqslant0$ being a pipe-specific conversion factor. Observe, the linepack equations (<ref>) and (<ref>) are related to the Weymouth equation (<ref>), which requires the midway flow to be proportional to the loss of pressure. The linepack flexibility calls for the following relaxation of conservation law (<ref>):

\begin{align}
&A^{\shortplus}\varphi^{\shortplus} + A^{\shortminus}\varphi^{\shortminus}
\end{align}

which requires flow conservation only in terms of inlet and outlet gas flows, where matrices $A^{\shortplus}$ and $A^{\shortminus}$ are obtained from the full incidence matrix $A$ by striking out only negative and positive entries, respectively. To model linepack dynamics across a finite set $\mathcal{T}=\{1,\dots,T\}$ of time stages, we consider

\begin{align}
&\psi_{t} = \psi_{t-1} + \varphi_{t}^{\shortplus} - \varphi_{t}^{\shortminus}, \quad\forall t\in\mathcal{T},\label{eq:lp_in_time}\\
&\psi_{T}\geqslant\psi_{\ell0}, \label{eq:non_depletion}
\end{align}

where equation (<ref>) models the linepack state in time and equation (<ref>) does not permit the linepack depletion at the last stage $(t=T)$ below the initial amount $(t=0)$.

§.§ Linearization of the Weymouth Equation (<ref>)

When gas extractions are uncertain, solving the system of equations (<ref>) is difficult due to the non-convex Weymouth equation. We thus provide the following linearization technique to reduce problem complexity.
Let $\mathcal{J}(x)\in\mathbb{R}^{E\times m}$ denote the Jacobian of (<ref>) in some arbitrary point $x\in\mathbb{R}^{m}$, and let $(\mathring{\varphi},\mathring{\varrho},\mathring{\kappa})$ be a stationary point, i.e., obtained by solving equations (<ref>) for the deterministic (mean) gas extraction values. Then, according to <cit.>, the following linear equation

\begin{align}
\varphi &=
\underbrace{\mathcal{J}(\mathring{\varphi})^{-1}(\mathcal{J}(\mathring{\varrho})\mathring{\varrho} + \mathcal{J}(\mathring{\kappa})\mathring{\kappa}) + \mathring{\varphi}}_{w_{0}(\mathring{\varphi},\mathring{\varrho},\mathring{\kappa})} \nonumber \\
\underbrace{-\mathcal{J}(\mathring{\varphi})^{-1}\mathcal{J}(\mathring{\kappa})}_{W_{2}(\mathring{\varphi},\mathring{\kappa})}\kappa\nonumber\\
&=w_{0} + W_{1}\varrho + W_{2}\kappa\label{eq:wey_lin}
\end{align}

is equivalent to equation (<ref>) at the stationary point, where $w_{0}\in\mathbb{R}^{E}$, $W_{1}\in\mathbb{R}^{E\times N}$ and $W_{2}\in\mathbb{R}^{E\times E}$ are sensitivities depending on the stationarity point. To ensure the flow solution uniqueness under linearization (<ref>), we require the pressure at the reference node $\text{r}$ (e.g., with a large constant gas injection) to be fixed as $\varrho_{\text{r}t}=\mathring{\varrho}_{\text{r}t}$. When deviations from the stationary point are large, however, linearization (<ref>) may produce approximation errors. The work in <cit.>, however, bounds these errors to modest values even under large deviations.

§.§ From Renewable Power to Gas Extraction Uncertainty

The gas extraction uncertainty is due to combined cycle gas turbines (CCGT) that balance stochastic renewable generation in power systems. To model renewable uncertainty, consider a dynamic stochastic process $\fat{\zeta}\!=\!(\fat{\zeta}_{1},\dots,\fat{\zeta}_{T})\in\mathbb{R}^{k}$  which develops throughout a $T-$stage horizon. Here, vector $\fat{\zeta}_{t}\in\mathbb{R}^{k_{t}}$ collects random variables revealed at stage $t$. Let vector $\boldsymbol{\zeta}^{t}=(\boldsymbol{\zeta}_{1},\dots,\boldsymbol{\zeta}_{t})\in\mathbb{R}^{k^{t}}$ collect random variables realized upon stage $t$, i.e., current and all previous realizations, meaning $k^{t}=\sum_{\tau=1}^{t}k_{\tau}$ and $k^{T}=k$. The random generation from a set $\mathcal{R}=\{1,\dots,R\}$ of renewable units is modeled as

\begin{align}\label{eq:renewable_process}
\tilde{r}_{t}(\fat{\zeta}^{t}) = \Omega_{t}\fat{\zeta}^{t} \in\mathbb{R}^{R},
\end{align}

i.e., as an affine combination of random variables revealed up to stage $t$, where $\Omega_{t}\in\mathbb{R}^{R\times k^{t}}$ is a matrix of coefficients. We consider that  $\fat{\zeta}$ belongs to the unknown distribution $\mathbb{P}_{\fat{\zeta}}(\widehat{\mu},\widehat{\Sigma})$, but its mean $\widehat{\mu}\in\mathbb{R}^{k}$ and covariance $\widehat{\Sigma}\in\mathbb{R}^{k\times k}$ are known from history. Finally, we set $\fat{\zeta}_{1}\!=\!1$ $(k_{1}\!=\!1)$ as the renewable generation at time stage 1 (stage “here-and-now”) is certain.

To map renewable uncertainty $\fat{\zeta}$ into uncertain gas extractions, suppose that the power system operator solves a multi-stage optimal power flow problem, where the affine generator response $\tilde{g}_{t}(\fat{\zeta}^{t}) = G_{t}\fat{\zeta}^{t}\in\mathbb{R}^{M}$ is computed for all $M$ generators by optimizing variable $G_{t}\in\mathbb{R}^{M\times k^{t}}$, which is consistent with <cit.>. Then, for a power-to-gas conversion matrix $\Lambda\in\mathbb{R}^{M\times N}$, the uncertain extraction is modeled as $\tilde{\delta}_{t}(\fat{\zeta}^{t})=\Lambda G_{t}^{\star} \fat{\zeta}^{t}\in\mathbb{R}^{N}$, i.e., as an affine combination of random renewable deviations, where $G_{t}^{\star}$ is an optimized generator response. To ease the narrative, we make a substitution $\Delta_{t} = \Lambda G_{t}^{\star}\in\mathbb{R}^{N\times k^{t}}$. Once the generator response is optimized, we assume that the power system operator submits uncertainty information – matrices $\{\Delta_{t}\}_{t\in\mathcal{T}}$ and two moments $\widehat{\mu}$ and $\widehat{\Sigma}$ – to the gas network operator.

In the interest of space, we do not discuss the optimization of generator policy $\tilde{g}_{t}(\fat{\zeta}^{t})$ explicitly, but provide it in the online repository <cit.>.

§ INVOKING LINEPACK FLEXIBILITY THROUGH MULTI-STAGE STOCHASTIC OPTIMIZATION

The uncertainty of gas extractions motivates the following stochastic formulation of the gas network optimization:

\begin{align}
&\mathbb{E}_{\mathbb{P}_{\fat{\zeta}}}\!\!\left[\sum_{t=1}^{T}\braceit{c_{1}^{\top}\tilde{\vartheta}_{t}(\fat{\zeta}^{t}) + \tilde{\vartheta}_{t}(\fat{\zeta}^{t})^{\top}\text{dg}[c_{2}]\tilde{\vartheta}_{t}(\fat{\zeta}^{t})}\right]\label{stoch_intr_obj}\\
&\text{subject to}\colon\nonumber\\
\begin{aligned}
&A^{\shortplus}\tilde{\varphi}_{t}^{\shortplus}(\fat{\zeta}^{t}) + A^{\shortminus}\tilde{\varphi}_{t}^{\shortminus}(\fat{\zeta}^{t})
&\qquad\qquad\qquad\qquad\;\!-B\tilde{\kappa}_{t}(\fat{\zeta}^{t})-\tilde{\delta}_{t}(\fat{\zeta}^{t}) \\
&\tilde{\varphi}_{t}(\fat{\zeta}^{t})=w_{0t} + W_{1t}\tilde{\varrho}_{t}(\fat{\zeta}^{t}) + W_{2t}\tilde{\kappa}_{t}(\fat{\zeta}^{t})\\
&\tilde{\varphi}_{t}(\fat{\zeta}^{t}) = \tfrac{1}{2}\braceit{\tilde{\varphi}_{t}^{\shortplus}(\fat{\zeta}^{t}) + \tilde{\varphi}_{t}^{\shortminus}(\fat{\zeta}^{t})}\\
&\tilde{\psi}_{t}(\fat{\zeta}^{t}) = \tfrac{1}{2}\text{dg}[s]\braceit{\tilde{\kappa}_{t}(\fat{\zeta}^{t}) + |A|^{\top}\tilde{\varrho}_{t}(\fat{\zeta}^{t})}\\
&\tilde{\psi}_{t}(\fat{\zeta}^{t}) = \tilde{\psi}_{t\shortminus1}(\fat{\zeta}^{t\shortminus1}) + \tilde{\varphi}_{t}^{\shortplus}(\fat{\zeta}^{t}) - \tilde{\varphi}_{t}^{\shortminus}(\fat{\zeta}^{t})
\end{aligned}
\right]=1,\label{stoch_intr_as}
\\
\begin{aligned}
\begin{aligned}
&\underline{\varrho}\leqslant \tilde{\varrho}_{t}(\fat{\zeta}^{t})\leqslant\overline{\varrho}\\
&\underline{\kappa}\leqslant \tilde{\kappa}_{t}(\fat{\zeta}^{t})\leqslant\overline{\kappa}\\
\end{aligned}
& &
\begin{aligned}
\end{aligned}
\end{aligned}
\right]\!\geqslant\!1\!-\!\varepsilon_{t},\label{stoch_intr_cc}\\
&\text{for all time stages}\;t\in\mathcal{T}.\nonumber
\end{align}

This problem minimizes the expected quadratic cost of gas injection, with cost vectors $c_{1}$ and $c_{2}$, subject to probabilistic constraints enforced across the $T-$stage control horizon. Here, the stochastic gas injection $\tilde{\vartheta}_{t}$ and pressure regulation rate $\tilde{\kappa}_{t}$ are variable vectors controlled by the network operator, and stochastic pressure $\tilde{\varrho}_{t}$, flow $\tilde{\varphi}_{t}^{(\cdot)}$ and linepack $\tilde{\psi}_{t}$ vectors are state variables that adjust in response to the control variables. Since the pressure at the reference node is fixed to the reference value $\mathring{\varrho}_{\text{r}t}$, the response of state variables is unique <cit.>.  Constraint (<ref>) requires the stochastic equalities to hold with probability 1, i.e., for any realizations of uncertainty. The entries of this constraint are stochastic counterparts of the gas network equations introduced in Section <ref>. $T$ joint chance constraints in (<ref>) are introduced to ensure the satisfaction of minimal and maximum physical limits with probability at least $1-\varepsilon_{t}$, where $\varepsilon_{t}$ is a small prescribed parameter.

Unlike two-stage scheduling problems under uncertainty, the variables and constraints in formulation (<ref>) are required to depend on $\fat{\zeta}^{t}=(\boldsymbol{\zeta}_{1},\dots,\boldsymbol{\zeta}_{t})$ – all prior realization of renewable forecast errors up to stage $t$. This enables expressing the network state through stochastic trajectories that must be controlled within network limits up to parameter $\varepsilon_{t}$ at every time stage $t$. This formulation, however, increases computational complexity (exponentially rather than linearly) as $T$ increases <cit.>. Fortunately,  this multi-stage stochastic program can be approximated efficiently under linear decision rules <cit.>.

§.§ Reformulations via Linear Decision Rules

To reformulate the multi-stage stochastic problem (<ref>), we introduce truncation operators $S_{t},\forall t\in\mathcal{T}$, defined in <cit.> as

\begin{align*}
S_{t}:\mathbb{R}^{k}\mapsto\mathbb{R}^{k^{t}},\quad \fat{\zeta}\mapsto\fat{\zeta}^{t},
\end{align*}

to extract only those random entries of vector $\fat{\zeta}$ that realize by a particular time stage $t$.
Using truncation operators, the variables of stochastic problem (<ref>) are defined through the following multi-stage linear decision rules:

\begin{align}\label{eq:LDRs}
\begin{aligned}
\end{aligned}
&\tilde{\psi}_{t}(\fat{\zeta}^{t})= \Psi_{t}S_{t}\fat{\zeta}\\
\end{aligned}
\end{aligned}
\end{aligned},
\end{align}

where $\Theta_{t},P_{t}\!\in\!\mathbb{R}^{N\times k^{t}}$, $K_{t},\Psi_{t},\Phi_{t}^{(\cdot)}\!\in\!\mathbb{R}^{E\times k^{t}}$ are coefficient matrices subject to optimization. These matrices share an important property: their first column corresponds to the nominal value, e.g., gas supply nomination at stage $t$, and the remaining columns define the variable recourse with respect to all prior realizations of uncertainty up to stage $t$. This variable representation makes possible the following reformulations.

§.§.§ Objective Function Reformulation
The expected cost in (<ref>) is reformulated under linear decision rules (<ref>) using truncation and the first two moments of distribution $\mathbb{P}_{\fat{\zeta}}$ as

\begin{align}
&\mathbb{E}_{\mathbb{P}_{\fat{\zeta}}}\left[\sum_{t=1}^{T}\braceit{c_{1}^{\top}\Theta_{t}S_{t}\fat{\zeta} + \braceit{\Theta_{t}S_{t}\fat{\zeta}}^{\top}\text{dg}[c_{2}]\Theta_{t}S_{t}\fat{\zeta}}\right]\Longrightarrow\nonumber\\
&\sum_{t=1}^{T}\!\braceit{c_{1}^{\top}\Theta_{t}S_{t}\widehat{\mu} + \text{Tr}\left[
\Theta_{t}^{\top}\text{dg}[c_{2}]\Theta_{t}S_{t}\braceit{\widehat{\Sigma} + \widehat{\mu}\widehat{\mu}^{\top}}S_{t}^{\top}
\right]},
\end{align}

which is a convex expression easy to optimize. Here, the second term is obtained knowing that the expected value of the outer product of $\fat{\zeta}$ amounts to $\mathbb{E}_{\mathbb{P}_{\fat{\zeta}}}[\fat{\zeta}\fat{\zeta}^{\top}]=\widehat{\Sigma}+\widehat{\mu}\widehat{\mu}^{\top}$.

§.§.§ Reformulation of Stochastic Equalities
The entries of constraint (<ref>) admit an analytic reformulation by constraining the matrices in (<ref>): each entry can be represented as a linear stochastic equality $X_{t}S_{t}\fat{\zeta}=\mathbb{0}_{m}$ for some coefficient matrix $X_{t}\in\mathbb{R}^{m\times k^{t}}$. One then verifies that this equality holds for any $\fat{\zeta}$ if $X_{t}$ is constrained by $X_{t}S_{t}=\mathbb{0}_{m\times k}$. For instance, the pressure at the reference node reformulates accordingly as

\begin{align*}
\overset{\fat{\zeta}_{1}=1}{\Longleftrightarrow}
[P_{t}S_{t}\fat{\zeta}]_{\text{r}}=\begin{bmatrix}\mathring{\varrho}_{\text{r}t}&\mathbb{0}_{1\times (k^{t}\shortminus1)}\end{bmatrix} S_{t}\fat{\zeta}
\\
&\Longleftrightarrow\braceit{[P_{t}]_{\text{r}} - \begin{bmatrix}\mathring{\varrho}_{\text{r}t}&\mathbb{0}_{1\times (k^{t}\shortminus1)}\end{bmatrix}}S_{t}=\mathbb{0}.
\end{align*}

The remaining stochastic equalities are reformulated by analogy, whose final expressions are given in (<ref>)-(<ref>).

§.§.§ Reformulation of Joint Chance Constraints
We follow the analytic reformulation based on Bonferroni and Chebyshev approximations. That is, we split $T$ joint chance constraints (<ref>)  into $(E + |\mathcal{E}_{a}|) + (N+2E)$ individual chance constraints each, where the first cardinality term relates to single-sided constraints and the second one to double-sided constraints. Single-sided constraints are treated using a distributionally robust Chebyshev reformulation <cit.>. For instance, the constraints on the minimum stochastic gas flow in active pipelines

\begin{align*}
\tilde{\varphi}_{t\ell}(\fat{\zeta}^{t})\geqslant0
\right]\geqslant1-\overline{\varepsilon}_{t}, \;\forall \ell\in\mathcal{E}_{a}, \forall t\in\mathcal{T},
\end{align*}

are reformulated into second-order cone constraint (<ref>), where $\overline{\varepsilon}_{t} = (1-\varepsilon_{t})/(E + |\mathcal{E}_{a}| + N+2E)$ and $\widehat{F}$ is covariance matrix factorization, i.e., $\widehat{\Sigma}=\widehat{F}\widehat{F}^{\top}$. Notice, a similar reformulation of double-sided chance-constraints, e.g., on stochastic gas injections bounded from both ends, is economically inefficient because the lower and upper bounds cannot be violated simultaneously. We thus invoke the exact reformulation of such constraints from <cit.>. For example, the chance constraint on stochastic gas injection

\begin{align*}
\underline{\vartheta}_{n}\leqslant[\Theta_{t}]_{n}S_{t}\fat{\zeta}\leqslant\overline{\vartheta}_{n}
\right]\geqslant1-\overline{\varepsilon}_{t}, \;\forall n\in\mathcal{N},\;\forall t\in\mathcal{T},
\end{align*}

re-writes into a second-order cone constraint (<ref>) and a set of linear constraints in (<ref>) and (<ref>), where $y_{tn}^{\vartheta}$ and $x_{tn}^{\vartheta}$ are auxiliary variables subject to optimization. The remaining double-sided chance-constraints are reformulated by analogy.

The tractable reformulation of the multi-stage stochastic problem (<ref>) in linear decision rules (<ref>) takes the form:

\begin{align}
\Theta_{t}^{\top}\text{dg}[c_{2}]\Theta_{t}S_{t}\braceit{\widehat{\Sigma}\!+\!\widehat{\mu}\widehat{\mu}^{\top}}S_{t}^{\top}
\right]}\label{prob_cc_obj}\\
&\text{subject to}\colon\nonumber\\
&\braceit{A^{\shortplus}\Phi_{t}^{\shortplus} + A^{\shortminus}\Phi_{t}^{\shortminus} - \Theta_{t}S_{t}+BK_{t}+\Delta_{t}}S_{t} = \mathbb{0}\label{prob_cc_eq_1}\\
&\braceit{\Phi_{t} - \big[w_{0t}\;\;\mathbb{0}_{E\times (k^{t}\shortminus1)}\big] -  W_{1t}P_{t} - W_{2t}K_{t}}S_{t} = \mathbb{0} \\
&\braceit{[P_{t}]_{\text{r}} - \big[\mathring{\varrho}_{\text{r}t}\;\;\mathbb{0}_{1\times (k^{t}\shortminus1)}\big]}S_{t}=\mathbb{0}\\
&\braceit{\Phi_{t} - \tfrac{1}{2}\Phi_{t}^{\shortplus} - \tfrac{1}{2}\Phi_{t}^{\shortminus}}S_{t}=\mathbb{0}\\
&\braceit{\Psi_{t}-\tfrac{1}{2}\text{dg}[s]\braceit{K_{t} + |A|^{\top}P_{t}}}S_{t}=\mathbb{0}\\
&\braceit{\Psi_{t}S_{t} - \Phi_{t}^{\shortplus} + \Phi_{t}^{\shortminus}}S_{t} - \Psi_{(t\shortminus1)}S_{(t\shortminus1)}=\mathbb{0}\label{prob_cc_eq_6}\\
\widehat{F}
[\Phi_{t}S_{t}\widehat{\mu}]_{\ell}\;^* \label{prob_cc_soc_min_flow}\\
\widehat{F}
[\Psi_{t}S_{t}\widehat{\mu} - \psi_{0}]_{\ell} \\
&\sqrt[-2]{\overline{\varepsilon}}\norm{\begin{matrix}\widehat{F}[\Theta_{t}S_{t}]_{n}^{\top}\\y_{tn}^{\vartheta}\end{matrix}}\leqslant\textstyle\frac{1}{2}\big(\overline{\vartheta}_{n} - \underline{\vartheta}_{n}\big) - x_{tn}^{\vartheta}\label{prob_cc_gas_inj_soc}\\
&\sqrt[-2]{\overline{\varepsilon}}\norm{\begin{matrix}\widehat{F}[K_{t}S_{t}]_{\ell}^{\top}\\y_{t\ell}^{\kappa}\end{matrix}}\leqslant\textstyle\frac{1}{2}\big(\overline{\kappa}_{\ell} - \underline{\kappa}_{\ell}\big) - x_{t\ell}^{\kappa}\\
&\sqrt[-2]{\overline{\varepsilon}}\norm{\begin{matrix}\widehat{F}[P_{t}S_{t}]_{n}^{\top}\\y_{tn}^{\varrho}\end{matrix}}\leqslant\textstyle\frac{1}{2}\big(\overline{\varrho}_{n} - \underline{\varrho}_{n}\big) - x_{tn}^{\varrho}\\
&\left|[\Theta_{t}S_{t}]_{n}\widehat{\mu} - \textstyle\frac{1}{2}\big(\overline{\vartheta}_{n} - \underline{\vartheta}_{n}\big) \right| \leqslant y_{tn}^{\vartheta} + x_{tn}^{\vartheta}\label{prob_cc_gas_inj_lin_1}\\
&\left|[K_{t}S_{t}]_{\ell}\widehat{\mu} - \textstyle\frac{1}{2}\big(\overline{\kappa}_{\ell} - \underline{\kappa}_{\ell}\big) \right| \leqslant y_{t\ell}^{\kappa} + x_{t\ell}^{\kappa}\\
&\left|[P_{t}S_{t}]_{n}\widehat{\mu} - \textstyle\frac{1}{2}\big(\overline{\varrho}_{n} - \underline{\varrho}_{n}\big)\right| \leqslant y_{tn}^{\varrho} + x_{tn}^{\varrho}\\
&\textstyle\frac{1}{2}\big(\overline{\vartheta}_{n} - \underline{\vartheta}_{n}\big)\geqslant x_{tn}^{\vartheta} \geqslant 0,\; y_{tn}^{\vartheta} \geqslant 0\label{prob_cc_gas_inj_lin_2}\\
&\textstyle\frac{1}{2}\big(\overline{\kappa}_{\ell} - \underline{\kappa}_{\ell}\big)\geqslant x_{t\ell}^{\kappa} \geqslant 0,\; y_{t\ell}^{\kappa} \geqslant 0\\
&\textstyle\frac{1}{2}\big(\overline{\varrho}_{n} - \underline{\varrho}_{n}\big)\geqslant x_{tn}^{\varrho} \geqslant 0,\; y_{tn}^{\varrho} \geqslant 0 \label{prob_cc_soc_last}\\
&\forall t\in\mathcal{T},\;\forall n\in\mathcal{N},\;\forall\ell\in\mathcal{E}, \;^*\forall\ell\in\mathcal{E}_{a}.
\end{align}

§.§ Stochastic Control Applications

The gas network operator controls the network state by optimizing stochastic gas injections $\tilde{\vartheta}_{t}(\fat{\zeta}^{t})$ and pressure regulation rates $\tilde{\kappa}_{t}(\fat{\zeta}^{t})$ across the $T-$stage control horizon. This subsection discusses how these control variables can be optimized by chance-constrained program (<ref>) in several applications.

§.§.§ Linepack to Balance Stochastic Renewables
Consider a network operator who accommodates uncertain gas extractions in real-time and is reluctant to adjust nominal gas injection contracts, because substantially altering gas nominations leads to expensive regulation penalties. Instead of substantially altering nominal injection, the network operator can leverage the linepack as an alternative source of flexibility to balance gas extractions by optimizing pressure regulation rates of compressors and valves. Doing so means optimizing program (<ref>) while additionally ensuring the satisfaction of the following constraint on stochastic gas injection variables:

\begin{align}
\leqslant \alpha^{\vartheta}[\Theta_{t}]_{n}S_{t}\widehat{\mu},\; \forall n\in\mathcal{N},
\end{align}

where the left-hand side computes the standard deviation $\text{Std}[\tilde{\vartheta}_{t}(\fat{\zeta}^{t})]$ of stochastic injections, and the right-hand side is the fraction of the nominal gas injection up to factor $\alpha^{\vartheta}\geqslant0$. Setting $\alpha^{\vartheta}=0.025$, for example, constrains the standard deviation of gas injections under the optimized control policies to 2.5% of the nominal value, which is relatively small.

§.§.§ Minimal Variability of Network State

Linepack flexibility can be invoked to minimize the variability of state variables, such as nodal gas pressures. Towards the goal, objective function (<ref>) is augmented with

\begin{align}
\mathbb{E}_{\mathbb{P}_{\fat{\zeta}}}\left[\alpha^{\varrho}\sum_{t=2}^{T}
\big\lVert
P_{t}S_{t}\fat{\zeta} - P_{t-1}S_{t-1}\fat{\zeta}
\big\rVert
\right],\label{eq:rho_var}
\end{align}

which minimizes the expected distance between stochastic nodal pressures at adjacent stages of control horizon up to prescribed non-negative penalty parameter $\alpha^{\varrho}$. Hence, by setting $\alpha^{\varrho}$, the control variables of (<ref>) are optimized to meet a trade-off between the expected costs and variability of system state. To reformulate (<ref>), we make a substitution $\tilde{P}_{t}=P_{t}S_{t}$ for compactness. Then, this term becomes

\begin{align}
\alpha^{\varrho}\sum_{t=2}^{T}
\big\lVert
\tilde{P}_{t}\fat{\zeta} - \tilde{P}_{t-1}\fat{\zeta}
\big\rVert
\right] \nonumber\\
&= \mathbb{E}_{\mathbb{P}_{\fat{\zeta}}}\left[
\alpha^{\varrho}\sum_{t=2}^{T}
\braceit{\braceit{\tilde{P}_{t} - \tilde{P}_{t-1}}\fat{\zeta}}^{\top}\braceit{\tilde{P}_{t} - \tilde{P}_{t-1}}\fat{\zeta}
\right]\nonumber\\
[\tilde{P}_{t} - \tilde{P}_{t-1}]_{i}\fat{\zeta}
\right]\nonumber\\
\braceit{\tilde{P}_{t} - \tilde{P}_{t-1}}\widehat{\Sigma}\braceit{\tilde{P}_{t} - \tilde{P}_{t-1}}^{\top}
\right],\label{eq:rho_var_ref}
\end{align}

which is a convex function. This derivation shows that term (<ref>) minimizes variability, e.g., inter-temporal pressure ramps, and the variance of stochastic pressures simultaneously.

§.§.§ Network Topology Optimization
Network topology has substantial impacts on disturbance propagation in natural gas networks. Fortunately, the topology can be optimized by the network operator by activating binary valves. Unlike control valves with variable decompression rates $\tilde{\kappa}_{t}(\fat{\zeta}^{t})$, the binary valves decouple gas states at both sides of the valve <cit.>. Hence, by activating binary valves, the network operator decouples network parts to minimize uncertainty propagation. To optimize topology, consider $V$ binary valves installed in the network and consider a set $\mathcal{C}=\{1,\dots,C\}$ of possible network topologies with $C=2^{V}$. To select a network topology, consider binary variables $v_{1},\dots,v_{C}\in\{0;1\}$: $v_{c}=1$ if topology $c$ is chosen, and  $v_{c}=0$ otherwise. Only one topology can be chosen for the entire control horizon, meaning

\begin{align}\label{eq:unique_topology}
\sum_{c=1}^{C}v_{c} = 1.
\end{align}

Suppose that for each topology $c\in\mathcal{C}$, sensitivity coefficients $w_{0c},W_{1tc}$ and $W_{2tc}$ in (<ref>) and reference node pressure $\mathring{\varrho}_{\text{r}tc}$ are known to the network operator, i.e., they can always be pre-computed offline by solving a finite series of deterministic optimization problems. Then, stochastic gas flows proxy  $\tilde{\phi}_{tc}(\fat{\zeta}^{t})\in\mathbb{R}^{E}$ at time stage $t$ in network topology $c$ writes as

\begin{align}
&\tilde{\phi}_{tc}(\fat{\zeta}^{t})=w_{0tc} + W_{1tc}\tilde{\varrho}_{t}(\fat{\zeta}^{t}) + W_{2tc}\tilde{\kappa}_{t}(\fat{\zeta}^{t}).
\end{align}

Here, the sensitivities amount to zero for pipelines with binary valves when those are activated, hence preventing the gas flow. Then, the following constraints map the proxy gas flows and reference node pressure to the ones under the chosen topology:

\begin{align}\label{eq:top_opt_last}
\end{align}

because only one topology can be selected as per equation (<ref>). Then, stochastic gas flow variables $\tilde{\varphi}_{t}(\fat{\zeta}^{t})$ participate in the rest of the gas flow equations in (<ref>). The tractable reformulation of stochastic equations (<ref>) is similar to that in Section <ref>. Yet, the flow equation in (<ref>) involves the product of binary and continuous variables, which is addressed by the standard Big-M approach. We provide the full problem reformulation as a mixed-integer SOCP (MISOCP) in <cit.>.

§ NUMERICAL EXPERIMENTS

§.§ Experimental Setup

We run experiments on the IEEE 118-bus system from <cit.>, with 11 wind farms distributed among 3 zones, and on the 48-node natural gas network from <cit.>. The two systems are coupled through 9 CGGT plants sited in the gas network as in Fig. <ref>. The goal is to accommodate the disturbances from renewable generation in the gas network through a 5-stage control horizon with several hours between the stages. To model renewable uncertainty, we assume that the intertemporal changes of wind power generation in each zone is conditioned on the realization of the random variable $\boldsymbol{\zeta}$ with arbitrary distribution but with known first- and second-order moments $\mu=\mathbb{1}$ and $\Sigma=\text{dg}[0,\sigma_{2}^{2},\dots,\sigma_{13}^{2}]$, respectively, with $\sigma_{i}^{2}=0.15,\forall i$. In terms of stochastic process (<ref>), this means $k_{1}=1$, $k_{t}=3,\forall t\geqslant2$ and $k=13$. We then choose matrices $\Omega_{t}$ in (<ref>) to obtain the descending stochastic wind power generation process depicted in Fig. <ref> (top). Then, following the procedure in Section <ref>, we solve a chance-constrained optimal power flow problem and convert the resulting stochastic CCGT generation into the ascending stochastic natural gas extraction process displayed in Fig. <ref> (bottom). The standard deviation of stochastic gas extractions amounts to up to 7.2% of their nominal values. When optimizing linear decision rules (<ref>) to accommodate this stochastic process, we require the stochastic network state trajectories to remain within network limits with individual constraint satisfaction probability at least 99.5% (i.e., $1-\overline{\varepsilon}_{t}=0.995$). Finally, we extract $10^3$ uncertainty samples from $
N(\mu,\Sigma)$ for the out-of-sample analysis.

Next, we provide selected results for control applications from Section <ref>. Solution time does not exceed 1.2 sec for the SOCP and 24.5 sec for the MISOCP programs on average with the MOSEK solver on a standard laptop. All modeling data and codes to replicate the results are available in <cit.>.

§.§ Results

Expected cost, state variability and feasibility across the 5-stage control horizon under deterministic and stochastic control

3*Parameter     3*Unit     3*c]@c@Deterministic
control policy     5cStochastic control policy

2*c]@c@Base     2*c]@c@Linepack-
agnostic      3cVariability-aware

$\alpha^{\varrho}=10$     $\alpha^{\varrho}=50$     $\alpha^{\varrho}=100$

Expected gas injection cost     $1000     644.8 (94.6%)     681.7 (100.0%)     752.1 (110.3%)     694.4 (101.9%)     701.2 (102.9%)     703.5 (103.2%)

Pressure variability term $\frac{\eqref{eq:rho_var}}{\alpha^{\varrho}}$     MPa     072.01 (189.7%)     038.0 (100.0%)     066.0 (173.6%)     007.8 0(20.5%)     007.3 0(19.2%)     007.2 0(19.1%)

Expected / worst-case magnitude

of pressure constraint violations

MPa     77.42 / 147.76     0.00 / 0.00     0.00 / 0.00     0.00 / 0.00     0.00 / 0.00     0.00 / 0.00

Expected / worst-case magnitude
of gas mass constraint violations
MMSCFD     26.86 / 146.91     0.01 / 0.02     0.13 / 0.13     0.01 / 0.02     0.02 / 0.02      0.02 / 0.02

First-stage gas injection
$\sum_{n\in\mathcal{N}}\vartheta_{1n}$     MMSCFD     2924.8     3229.0     3203.8     3233.2     3219.5     3219.1

Expected compressor deployment
$\sum_{\ell\in\mathcal{E}_{c}}^{t\in\mathcal{T}}\mathbb{E}_{\mathbb{P}_{\boldsymbol{\zeta}^{t}}}[\tilde{\kappa}_{t\ell}(\fat{\zeta}^{t})]$      kPa     7127.9     10225.3      10912.7     12464.8     12451.1     12459.8

Expected valve deployment
$\sum_{\ell\in\mathcal{E}_{v}}^{t\in\mathcal{T}}\mathbb{E}_{\mathbb{P}_{\boldsymbol{\zeta}^{t}}}[\tilde{\kappa}_{t\ell}(\fat{\zeta}^{t})]$     kPa     0.0     714.8     1251.27     2281.0     2604.2     2647.6

[From renewable to gas uncertainty]
ylabel = Renewable generation

y tick label style=
/pgf/number format/.cd,
fixed zerofill,
y label style=align=center,yshift=-0.15cm,
legend style=cells=align=center,legend columns=-1,font=,draw=none,xshift=-0.4cm,yshift=0.6cm
in 2,3,...,100
[color=blue!20,mark=none, forget plot]table [x index=0, y index=, col sep=comma] PSCC_2022_code/results/wind_results.csv;

[color=blue,mark=o,line width = 0.025cm] table [x index=0, y index=1, col sep=comma] PSCC_2022_code/results/wind_results.csv;
[color=blue!20,mark=none]table [x index=0, y index=3, col sep=comma] PSCC_2022_code/results/wind_results.csv;

[width=0.275,height=0.21,yshift = -0.15,
ylabel = Gas extraction
ymax = 1.0,
xlabel = Time stage,
y tick label style=
/pgf/number format/.cd,
fixed zerofill,
y label style=align=center,yshift=-0.15cm
in 2,3,...,100
[color=blue!20,mark=none]table [x index=0, y index=, col sep=comma] PSCC_2022_code/results/gas_coms_results.csv;

[color=blue,mark=o,line width = 0.025cm] table [x index=0, y index=1, col sep=comma] PSCC_2022_code/results/gas_coms_results.csv;

[Linepack relative density across the network ]

[inner sep=0pt] (a) at (0,0) ;

[below of = a, yshift = -1.9cm] (l) ;
[above of = l, yshift = -1.28cm,font=, scale = 0.8, xshift = -1.515cm,font=] $\shortminus25$;
[above of = l, yshift = -1.28cm,font=, scale = 0.8, xshift = -1.125cm,font=] $\shortminus19$;
[above of = l, yshift = -1.28cm,font=, scale = 0.8, xshift = -0.76cm,font=] $\shortminus9$;
[above of = l, yshift = -1.28cm,font=, scale = 0.8, xshift = -0.385cm,font=] $0$;
[above of = l, yshift = -1.28cm,font=, scale = 0.8, xshift = -0.0cm,font=] +$1$;
[above of = l, yshift = -1.28cm,font=, scale = 0.8, xshift = 0.375cm,font=] +$3$;
[above of = l, yshift = -1.28cm,font=, scale = 0.8, xshift = 0.750cm,font=] +$6$;
[above of = l, yshift = -1.28cm,font=, scale = 0.8, xshift = 1.125cm,font=] +$10$;
[above of = l, yshift = -1.28cm,font=, scale = 0.8, xshift = 1.500cm,font=] +$12$;
[above of = l, yshift = -1.0cm,font=, scale = 0.8, xshift = 2.95cm,font=] $\frac{\tilde{\psi}_{1i}(\boldsymbol{\zeta}^{1}) - \psi_{1}}{\psi_{1i}}\cdot100$,%;

[Pressure scenarios]
ylabel = Pressure regulation
y tick label style=
/pgf/number format/.cd,
fixed zerofill,
legend style=cells=align=center,fill=none,legend columns=-1,font=,draw=none,xshift=0.1cm,yshift=0.75cm,
y label style=align=center,yshift=-0.15cm
in 2,3,...,100
[color=red!20,mark=none, forget plot]table [x index=0, y index=, col sep=comma] PSCC_2022_code/results/sto_pres_reg_wo_var.csv;

in 2,3,...,100
[color=blue!20,mark=none, forget plot]table [x index=0, y index=, col sep=comma] PSCC_2022_code/results/sto_pres_reg_wt_var.csv;

[color=red,mark=o,line width = 0.025cm] table [x index=0, y index=1, col sep=comma] PSCC_2022_code/results/sto_pres_reg_wo_var.csv;
[color=blue,mark=o,line width = 0.025cm] table [x index=0, y index=1, col sep=comma] PSCC_2022_code/results/sto_pres_reg_wt_var.csv;

[width=0.275,height=0.21,yshift = -0.15,
ylabel = Gas pressure
xlabel = Time stage,
y tick label style=
/pgf/number format/.cd,
fixed zerofill,
y label style=align=center,yshift=-0.15cm
in 2,3,...,100
[color=red!20,mark=none]table [x index=0, y index=, col sep=comma] PSCC_2022_code/results/sto_pressure_wo_var.csv;

in 2,3,...,100
[color=blue!20,mark=none]table [x index=0, y index=, col sep=comma] PSCC_2022_code/results/sto_pressure_wt_var.csv;

[color=red,mark=o,line width = 0.025cm] table [x index=0, y index=1, col sep=comma] PSCC_2022_code/results/sto_pressure_wo_var.csv;
[color=blue,mark=o,line width = 0.025cm] table [x index=0, y index=1, col sep=comma] PSCC_2022_code/results/sto_pressure_wt_var.csv;

Multi-stage natural gas network optimization: (a) Normalized total renewable power generation scenarios (top) and their conversion into normalized total gas extraction (bottom) as explained in Section <ref>, (b) Density plot of the relative difference between the deterministic ($\psi_{1i}$) and the base stochastic ($\tilde{\psi}_{1i}
(\boldsymbol{\zeta}^{1})$) first-stage linepack decisions for $i=1,\dots,E$, (c) Normalized scenarios of total pressure regulation (top) and aggregated nodal pressures (bottom) under the base stochastic (variability-agnostic) and stochastic variability-aware network control policies.

xlabel = Expected gas injection cost [$\times\$1000$],
ylabel = Var. term $\frac{\eqref{eq:rho_var}}{\alpha^{\varrho}}$ [$\times1000$],

ymin = 6,
ymax = 12,
xmin = 742,
xmax = 757,
y label style=align=center,yshift=-0.15cm,

legend style=scale=0.8,cells=align=center,legend columns=2,font=,draw=none,xshift=0.cm,yshift=0.cm
[color=gray,mark=o,line width = 0.025cm] table [x=cost, y=std, col sep=comma] PSCC_2022_code/results/var_trade_off_conf_c_1.csv;

[fill=red!75] (0,0) edge[bend left=90,fill=red!75] (0,0.075) – (0.045,0.0)  – (0.045,0.075) – (0.0,0.075) node[pos=0.5,yshift=-2.6] $v_{1}$;
[fill=green!75] (0.09,0.075) edge[bend left=90,fill=green!75] (0.09,0.0) – (0.045,0.075) – (0.045,0.0) – (0.09,0.0) node[pos=0.5,yshift=3.5] $v_{2}$;

[color=gray,mark=*,line width = 0.025cm] table [x=cost, y=std, col sep=comma] PSCC_2022_code/results/var_trade_off_conf_c_2.csv;

[fill=green!75] (0,0) edge[bend left=90,fill=green!75] (0,0.075) – (0.045,0.0)  – (0.045,0.075) – (0.0,0.075) node[pos=0.5,yshift=-2.6] $v_{1}$;
[fill=green!75] (0.09,0.075) edge[bend left=90,fill=green!75] (0.09,0.0) – (0.045,0.075) – (0.045,0.0) – (0.09,0.0) node[pos=0.5,yshift=3.5] $v_{2}$;

[color=gray,mark=square,line width = 0.025cm] table [x=cost, y=std, col sep=comma] PSCC_2022_code/results/var_trade_off_conf_c_3.csv;

[fill=green!75] (0,0) edge[bend left=90,fill=green!75] (0,0.075) – (0.045,0.0)  – (0.045,0.075) – (0.0,0.075) node[pos=0.5,yshift=-2.6] $v_{1}$;
[fill=red!75] (0.09,0.075) edge[bend left=90,fill=red!75] (0.09,0.0) – (0.045,0.075) – (0.045,0.0) – (0.09,0.0) node[pos=0.5,yshift=3.5] $v_{2}$;

[color=gray,mark=square*,line width = 0.025cm] table [x=cost, y=std, col sep=comma] PSCC_2022_code/results/var_trade_off_conf_c_4.csv;

[fill=red!75] (0,0) edge[bend left=90,fill=red!75] (0,0.075) – (0.045,0.0)  – (0.045,0.075) – (0.0,0.075) node[pos=0.5,yshift=-2.6] $v_{1}$;
[fill=red!75] (0.09,0.075) edge[bend left=90,fill=red!75] (0.09,0.0) – (0.045,0.075) – (0.045,0.0) – (0.09,0.0) node[pos=0.5,yshift=3.5] $v_{2}$;

[color=blue,densely dotted,mark=none,line width = 0.075cm] coordinates(742,12.2)(743,10)(743.85,8.1)(744.7,8.05)(744.83,7.74375)(746.817,7.60241)(748.5,7.5287)(748.7,7.1287)(750.2,7.051)(750.25,6.93)(752.442,6.77)(753.4,6.735)(754,6.728)(755,6.7)(756.99,6.65);

[,->,>=stealth] (0.8,2.35) – node[rotate=-33,above,pos=0.5,scale=0.85,yshift=-0.05cm] penalty $\alpha^{\varrho}$ increases (2.7,1.1);

Trade-offs between the expected cost and pressure variability under four network topologies for varying penalty factor $\alpha^{\varrho}$. The green/red color indicates that the binary valve is activated/deactivated. The optimal frontier (depicted in dashed blue) is obtained by solving the mixed-integer topology optimization problem from Section <ref> for various assignments $\alpha^{\varrho}$. The variance of renewable generation is increased in this experiment from 0.15 to 0.20 for more illustrative results.

We first compare deterministic and stochastic control policies in Table <ref>. The deterministic policy is obtained by solving problem (<ref>) when replacing chance constraints (<ref>)–(<ref>) with their deterministic counterparts to constraint the nominal variable components only. The base stochastic policy is optimized following the application in Section <ref>: we set factor $\alpha^{\vartheta}=2.5\%$ to minimize the adjustment of gas injections, while exploiting the linepack as the main source of flexibility. The results in the $3^{\text{rd}}$ and $4^{\text{th}}$ columns of Table <ref> show that the expected cost under deterministic policy is 5.4% smaller than under the base stochastic policy. However, the out-of-sample analysis of the deterministic solution on 1000 uncertainty realization scenarios demonstrates substantial magnitudes of pressure and gas mass constraint violation across the 5-stage horizon, both in expectation and in the average worst-case scenario (computed below the $5\%$-quantile of the violation magnitude distribution). Improving on the deterministic solution, the base stochastic control policy demonstrates practically zero constraint violation at the expense of a 5.4% increase in expected cost. The difference between the two policies is that the stochastic one requires more nominal gas injection at the first stage, which is then stored as a linepack in the western network part to be deployed later to balance uncertain extractions, as shown by the density plot in Fig. <ref>.

Moreover, optimizing the base stochastic policy with the exact reformulation of the double-sided chance constraints in (<ref>) demonstrates a less conservative solution than the Chebyshev approximation (as in <cit.> and <cit.>), which guarantees the same constraint satisfaction probability but at larger expected cost of $698,643, which is 2.5% more expensive than in Table <ref>.

Next, we estimate the cost-saving potential of linepack flexibility in balancing stochastic gas extractions. To do so, we compare the base policy with the linepack-agnostic policy which disregards the flexibility of linepack. To obtain this policy, we reduce the recourse (adjustment) of linepack stochastic variable $\tilde{\psi}_{t}(\fat{\zeta}^{t})$ by introducing the following constraint:

\begin{align}
\leqslant \alpha^{\psi}[\Psi_{t}]_{\ell}S_{t}\widehat{\mu},\; \forall \ell\in\mathcal{E}, \forall t\in\mathcal{T},
\end{align}

to limit the standard deviation of linepack variable by an $\alpha^{\psi}-$portion of its nominal value. We empirically find out that the minimal value of $\alpha^{\psi}$ that ensures the feasibility of chance-constrained program (<ref>) is 4%, for which we report the results in the $5^{\text{th}}$ column of Table <ref>. Observe, that the feasibility performance of the base and linepack-agnostic strategies remain similar due to guarantees of chance constraints, but the ignorance to linepack flexibility results in a substantial increase in the expected cost. Here, we estimate the cost-saving potential of the linepack flexibility at 10.3%.

Next, consider three variability-aware policies for varying pressure variability penalty factor $\alpha^{\varrho}$ in Table <ref>. Even with a small penalty, the pressure variability already drops to 20.5% relative to the base policy at a small increase in operating costs by 1.9%. An increasing penalty further reduces the variability but at a larger cost, thus enabling the network operator to trade off between the expected cost and network state variability. Table <ref> and Figure <ref> (top) illustrate that variability-aware policies leverage active pipelines more intensively, with more notable use of control valves to regulate pressures. This yields substantially less variable and uncertain nodal pressure profiles, as shown in Fig. <ref> (bottom).

Finally, we analyze the  network topology optimization from Section <ref>. The topology is optimized by switching two binary valves $v_{1}$ and $v_{2}$ in edges (29,30) and (28,37), respectively, to provide the optimal cost-variability frontier to the network operator, as depicted in Fig. <ref>. For example, the expected operating cost of $\approx\$754\times10^3$ is achieved under the original topology with no activated valve, as well as under two other topologies with the second or both valves active. However, it is variability-optimal to maintain this cost level by activating the second valve to reduce the pressure variability measure by 13.2%, from 7.71 to 6.69 MPa.

§ CONCLUSIONS

To address propagating uncertainty and variability of renewable generation, we developed multi-stage stochastic control policies for natural gas network operators to leverage the linepack flexibility. Using chance-constrained programming, these policies were optimized for compressors and valves to satisfy feasibility and variability criteria without substantial deviations from the nominal natural gas supply injections.

Using a realistically sized natural gas network, we estimated the cost-saving potential of linepack flexibility at 10.3% of operating costs in expectation. We also found out that the system state variability can be reduced to 20.5% of the nominal value at a small 1.9% increase in expected costs. Finally, we concluded that the network topology must be optimized itself to enable new cost-variability trade offs to network operators.

Future research will focus on how the proposed stochastic control policies agree with a dynamic natural gas modeling to explicitly account for the time delays in gas transportation and linepack storage across the multi-stage control horizon.


# An Infinite Family of Connected 1-Factorisations of Complete 3-Uniform
Hypergraphs

Barbara Maenhaut Jeremy Mitchell and Anna Puskás
bmm@maths.uq.edu.aujeremy.mitchell<EMAIL_ADDRESS>School
of Mathematics and Physics
The University of Queensland
QLD 4072, Australia

###### Abstract

A connected 1-factorisation is a 1-factorisation of a hypergraph for which the
union of each pair of distinct 1-factors is a connected hypergraph. A uniform
1-factorisation is a 1-factorisation of a hypergraph for which the union of
each pair of distinct 1-factors is isomorphic to the same subhypergraph, and a
uniform-connected 1-factorisation is a uniform 1-factorisation in which that
subhypergraph is connected. Chen and Lu [Journal of Algebraic Combinatorics,
46(2) 475–497, 2017] describe a family of 1-factorisations of the complete
3-uniform hypergraph on $q+1$ vertices, where $q\equiv 2\pmod{3}$ is a prime
power. In this paper, we show that their construction yields a connected
1-factorisation only when $q=2,5,11$ or $q=2^{p}$ for some odd prime $p$, and
a uniform 1-factorisation only for $q=2,5,8$ (each of these is a uniform-
connected 1-factorisation).

##  1 Introduction

A _1-factor_ of a graph $G$ is a spanning 1-regular subgraph of $G$, and a
_1-factorisation_ of $G$ is a collection of edge-disjoint 1-factors of $G$
that partition the edge-set of $G$. It is natural to ask: under what
conditions does the complete graph on $n$ vertices ($K_{n}$) admit a
1-factorisation? It is clear that $n$ must be even. By Kirkman’s 1847
construction of 1-factorisations of $K_{n}$ for all even integers $n\geq 2$
[8], this condition is sufficient.

Given a 1-factorisation of a graph $G$, a well-studied problem is to ask if
the union of each pair of its 1-factors is isomorphic to the same subgraph $H$
of $G$. Such a 1-factorisation is called a _uniform 1-factorisation_ (U1F) of
$G$ and the subgraph $H$ is called the _common graph_. Furthermore, a uniform
1-factorisation in which the common graph is a Hamilton cycle is called a
_perfect 1-factorisation_ (P1F). In the 1960’s, Kotzig [9] posed a question
which has become known as Kotzig’s perfect 1-factorisation conjecture, namely
that for each even integer $n$, the complete graph $K_{n}$ admits a perfect
1-factorisation. Three infinite families of perfect 1-factorisations of
complete graphs are known to exist, covering orders $n=p+1$ and $n=2p$ where
$p$ is an odd prime [3]. Perfect 1-factorisations of complete graphs are also
known to exist for all even orders up to $n=56$ and some other sporadic
orders, however the conjecture remains open. For an updated overview of the
problem, we recommend a survey by Rosa [1] and a paper on the number of non-
isomorphic P1Fs of $K_{16}$ by Gill and Wanless [7]. Recently, Davies,
Maenhaut, and Mitchell [6], have generalised the notions of uniform and
perfect 1-factorisations of graphs to the context of hypergraphs.

A hypergraph $\mathcal{H}$ consists of a non-empty vertex set $V(\mathcal{H})$
and an edge set $E(\mathcal{H})$ in which each element of $E(\mathcal{H})$ is
a non-empty subset of the vertex set $V(\mathcal{H})$. The complete
$k$-uniform hypergraph of order $n$, denoted $K_{n}^{k}$, is the hypergraph
with $n$ vertices, in which the edges are precisely all the $k$-subsets of the
vertex set. A spanning 1-regular subhypergraph of a hypergraph is known as a
1-factor. A partition of the edge set of a hypergraph $\mathcal{H}$ into
1-factors is called a _1-factorisation_ of $\mathcal{H}$, and such a
1-factorisation having $\alpha$ 1-factors is often denoted by
$\mathcal{F}=\\{F_{1},\dots,F_{\alpha}\\}$. An obvious necessary condition for
the existence of a 1-factorisation of the complete $k$-uniform hypergraph on
$n$ vertices is that $k|n$. Baranyai [2] showed that for $k\geq 3$, this
condition is also sufficient.

A _path_ between two vertices, $x$ and $y$, of a hypergraph $\mathcal{H}$ is
an alternating sequence of vertices and edges

$[x=v_{1},e_{1},v_{2},e_{2},\dots,v_{s},e_{s},v_{s+1}=y],$

such that $v_{1},v_{2},\dots,v_{s+1}$ are distinct vertices of $\mathcal{H}$,
and $e_{1},e_{2},\dots e_{s}$ are distinct edges of $\mathcal{H}$ such that
$\\{v_{i},v_{i+1}\\}\subseteq e_{i}$ for $1\leq i\leq s$. If every two
vertices of a hypergraph $\mathcal{H}$ have a path between them, we say that
$\mathcal{H}$ is _connected_. A Berge cycle in a hypergraph $\mathcal{H}$, is
an alternating sequence of vertices and edges

$(v_{1},e_{1},v_{2},e_{2},\dots,v_{m},e_{m}),$

such that $[v_{1},e_{1},v_{2},e_{2},\dots,v_{m}]$ is a path in $\mathcal{H}$,
$\\{v_{1},v_{m}\\}\subseteq e_{m},$ and $e_{m}\in
E(\mathcal{H})\setminus\\{e_{1},e_{2},\dots,e_{m-1}\\}$. Note that each edge
$e_{i}$ may contain vertices other than $v_{i}$ and $v_{i+1}$ including
vertices outside of $\\{v_{1},\dots,v_{m}\\}$. A Hamilton Berge cycle in a
hypergraph $\mathcal{H}$ is a Berge cycle in $\mathcal{H}$ for which
$\\{v_{1},\dots,v_{m}\\}$ is the vertex set of $\mathcal{H}$.

In [6], Davies et al. generalised uniform and perfect 1-factorisations of
graphs to the context of hypergraphs in several different ways, leading to the
following definitions. A _connected 1-factorisation_ (C1F) is a
1-factorisation of a hypergraph for which the union of each pair of distinct
1-factors is a connected hypergraph. A _uniform 1-factorisation_ (U1F) is a
1-factorisation of a hypergraph for which the union of each pair of 1-factors
is isomorphic to the same subhypergraph, called the common hypergraph, and a
_uniform-connected 1-factorisation_ (UC1F) is a U1F in which the common
hypergraph is connected. A _Hamilton-Berge 1-factorisation_ (HB1F) is a
1-factorisation of a $k$-uniform hypergraph for which the union of each
$k$-set of 1-factors has a Hamilton Berge cycle. In addition to showing some
existence results of these generalisations, they also classified some known
1-factorisations as being C1Fs, HB1Fs, and U1Fs [6]. Of these known
1-factorisations, the infinite family of symmetric 1-factorisations of
$K_{q+1}^{3}$ for $q\equiv 2\pmod{3}$ found by Chen and Lu [5] is the subject
of this paper. We denote this 1-factorisation by $\mathcal{F}_{q},$ see §2.2.
Davies et al. [6], showed that for $q=2,5,8$ these 1-factorisations are C1Fs,
U1Fs, UC1Fs, and HB1Fs, and that the 1-factorisations when $q=11,32$ are C1Fs
and HB1Fs.

The main results of this paper determine when $\mathcal{F}_{q}$ is a C1F or a
U1F.

######  Theorem 1.1.

$\mathcal{F}_{q}$ is a connected 1-factorisation if and only if
$q\in\\{2,5,11\\}$ or $q=2^{p}$ for some odd prime $p$.

######  Theorem 1.2.

$\mathcal{F}_{q}$ is a uniform 1-factorisation if and only if
$q\in\\{2,5,8\\}$, and in these cases it is a uniform-connected
1-factorisation.

##  2 Preliminaries

Throughout this paper, $q$ denotes a prime power that satisfies $q\equiv
2\pmod{3}.$ Let $\mathbb{F}=\mathbb{F}_{q}$ be the finite field of order $q$,
let $\mathbb{F}^{*}=\mathbb{F}\setminus\\{0\\}$, and let
$V=\mathbb{F}\cup\\{\infty\\}$ be the vertex set of the complete 3-uniform
hypergraph of order $q+1$, $K^{3}_{q+1}$. We will work with a particular
1-factorisation of $K^{3}_{q+1}$, originally given by Chen and Lu [5]. To
describe this 1-factorisation, we first recall the action of the group
$\mathrm{PSL}(2,q)$ on the projective line $\mathrm{PG}(1,q).$

###  2.1 The action of $\mathbf{PSL(2,q)}$ on the projective line

Recall that $V=\mathbb{F}\cup\\{\infty\\}$ can be identified with the
projective line $\mathrm{PG}(1,q).$ (In homogeneous coordinates, identify
$\infty$ with $[1:0]^{T}$ and $x\in\mathbb{F}$ with $[x:1]^{T}.$) The group
$\mathrm{PSL}(2,q)$ is a quotient of $\mathrm{SL}(2,q):$

$\mathrm{PSL}(2,q)=\left\\{\left(\begin{array}[]{cc}\alpha&\beta\\\
\gamma&\delta\end{array}\right)\mid\alpha,\beta,\gamma,\delta\in\mathbb{F};\
\alpha\delta-\beta\gamma=1\right\\}/\sim,$

where two matrices are equivalent by $\sim$ if one is a scalar multiple of the
other. The group $\mathrm{PSL}(2,q)$ acts faithfully on $\mathrm{PG}(1,q):$

$\left(\begin{array}[]{cc}\alpha&\beta\\\
\gamma&\delta\end{array}\right).\left[\begin{array}[]{c}x\\\
y\end{array}\right]=\left[\begin{array}[]{c}\alpha x+\beta y\\\ \gamma
x+\delta y\end{array}\right].$

It is often more convenient to think of this action in terms of fractional
linear transformations on $\mathbb{F}\cup\\{\infty\\}.$ We may also write this
as:

$t_{\alpha,\beta,\gamma,\delta}(x):=\frac{\alpha x+\beta}{\gamma x+\delta}$

for $x\in\mathbb{F}\cup\\{\infty\\},$ where
$\frac{\alpha\infty+\beta}{\gamma\infty+\delta}=\frac{\alpha}{\gamma}$ for
$\gamma\neq 0$, $\frac{\alpha\infty+\beta}{\delta}=\infty$ for $\alpha\neq 0$,
and $\frac{\omega}{0}=\infty$ for $\omega\in\mathbb{F}^{*}$.

Recall that the action of $\mathrm{PSL}(2,q)$ on $\mathrm{PG}(1,q)$ is
transitive. Note that we may think of $\mathrm{PSL}(2,q)$ as a subgroup of
$\mathrm{PGL}(2,q)=\mathrm{GL}(2,q)/\sim,$ and the action given above extends
to one of $\mathrm{PGL}(2,q).$ Under this (extended) action, the stabiliser of
the point $\infty$ is a subgroup. Indeed, it is the group of the invertible
linear transformations of $\mathbb{F}\cup\\{\infty\\}:$

$\mathrm{PGL}(2,q)_{\infty}=\\{g_{\alpha,\beta}:=t_{\alpha,\beta,0,1}\mid\alpha\in\mathbb{F}^{\ast},\
\beta\in\mathbb{F}\\}.$

###  2.2 The construction of Chen and Lu

The following construction was given by Chen and Lu [5, Example 5.1, Lemma
5.2]. We present it here in a format convenient for our purposes. Let
$f:V\rightarrow V$ be the map defined by

$f(x)=\frac{1}{1-x}\text{ for $x\in V\setminus\\{1,\infty\\}$ and
$f(1)=\infty$ and $f(\infty)=0$.}$

For any $\alpha\in\mathbb{F}^{\ast}$ and $\beta\in\mathbb{F}$ define
$g_{\alpha,\beta}:$ $V\rightarrow V$ as $g_{\alpha,\beta}(x)=\alpha x+\beta$
for $x\in\mathbb{F}$ and $g_{\alpha,\beta}(\infty)=\infty$. Set
$m_{\alpha,\beta}:=g_{\alpha,\beta}\circ f\circ g_{\alpha,\beta}^{-1}.$ Here
$g_{\alpha,\beta}\in\mathrm{PGL}(2,q)$ and the conjugation makes sense in this
group, so that $m_{\alpha,\beta}\in\mathrm{PSL}(2,q).$ Then

$m_{\alpha,\beta}(x)=\beta+\frac{\alpha^{2}}{\alpha+\beta-x}\text{ for
$x\in\mathbb{F}\setminus\\{\alpha+\beta\\}$ and
$m_{\alpha,\beta}(\alpha+\beta)=\infty$, $m_{\alpha,\beta}(\infty)=\beta$.}$

Note that $m_{1,0}=f$ and $m_{\alpha,\beta}^{2}=m_{\alpha,\beta}^{-1}.$ In
particular, $m_{\alpha,\beta}\in\mathrm{PSL}(2,q)$ has order $3$ for any
$\alpha\in\mathbb{F}^{\ast}$ and $\beta\in\mathbb{F}.$ It has no fixed points
on $V=\mathrm{PG}(1,q).$ We also note that in the notation of [5],
$f=t_{0,1,-1,1}$ and
$m_{\alpha,\beta}=t_{-\beta,\alpha^{2}+\alpha\beta+\beta^{2},-1,\alpha+\beta}$.

It follows that the sets

$F_{\alpha,\beta}:=\left\\{\left\\{x,m_{\alpha,\beta}(x),m_{\alpha,\beta}^{-1}(x)\right\\}\mid\,x\in\mathbb{F}\cup\\{\infty\\}\right\\}$

are 1-factors of $K^{3}_{q+1}$ on $V.$ Set

$\mathcal{F}_{q}=\\{F_{\alpha,\beta}\mid\alpha\in\mathbb{F}^{\ast},\beta\in\mathbb{F}\\}.$

By [5, Lemma 5.2] $\mathcal{F}_{q}$ is a 1-factorisation of $K_{q+1}^{3}$ for
$q\geq 5$ if $q\equiv 2\pmod{3}$. In fact for $q=2$ it is the trivial
1-factorisation of $K_{3}^{3}$. Recall also that $\mathcal{F}_{q}$ has
$\frac{q(q-1)}{2}$ 1-factors. In particular, each is represented by exactly
two $(\alpha,\beta)$ pairs: $F_{\alpha,\beta}=F_{-\alpha,\alpha+\beta}$. Using
the notation of [5], $F_{\eta^{i},\beta}$ is $F_{i,\beta}$ in our notation,
and their ${\mathcal{PG}}_{(q+1;3,\frac{q(q-1)}{2})}$ is our
$\mathcal{F}_{q}.$

######  Remark 2.1.

Observe that $f=m_{1,0}$ having no fixed points implies that no
$x\in\mathbb{F}$ satisfies $x^{2}-x+1=0.$

In the language of the action of $\mathrm{PSL}(2,q)$ on $\mathrm{PG}(1,q),$
each 1-factor $F_{\alpha,\beta}\in{\mathcal{F}}_{q}$ is the set of orbits of
$\langle m_{\alpha,\beta}\rangle$ on $V=\mathrm{PG}(1,q).$ The elements
$m_{\alpha,\beta}\in\mathrm{PSL}(2,q)$ are exactly the conjugates of
$f=m_{1,0}$ in $\mathrm{PGL}(2,q)$ by the stabiliser
$\mathrm{PGL}(2,q)_{\infty}.$ Each subgroup $\langle m_{\alpha,\beta}\rangle$
is isomorphic to the cyclic group of order $3$.

In this paper we are concerned with the subhypergraph spanned by two (or in
the last section, three) 1-factors of ${\mathcal{F}}_{q}.$ The following
remark says that by relabelling vertices of $V$ we may assume, without loss of
generality, that one of the factors is $F_{1,0}.$

######  Remark 2.2.

Given two 1-factors $F_{\alpha_{1},\beta_{1}},F_{\alpha_{2},\beta_{2}}$ of
${\mathcal{F}}_{q},$ there is a $1$-factor $F_{\alpha_{0},\beta_{0}}$ so that
the subhypergraph $H$ spanned by the pair
$(F_{\alpha_{1},\beta_{1}},F_{\alpha_{2},\beta_{2}})$ is isomorphic to the
one, $H^{\prime}$, spanned by the pair $(F_{1,0},F_{\alpha_{0},\beta_{0}}).$
Indeed, let $(m_{\alpha_{1},\beta_{1}},m_{\alpha_{2},\beta_{2}})$ be a pair of
elements of $\mathrm{PSL}(2,q).$ Consider
$g=g_{\alpha_{1}^{-1},-\alpha_{1}^{-1}\beta_{1}},$ and set
$\alpha_{0}=\alpha_{1}^{-1}\alpha_{2},$
$\beta_{0}=\alpha_{1}^{-1}(\beta_{2}-\beta_{1}).$ Then
$(gm_{\alpha_{1},\beta_{1}}g^{-1},gm_{\alpha_{2},\beta_{2}}g^{-1})=(f,m_{\alpha_{0},\beta_{0}})=(m_{1,0},m_{\alpha_{0},\beta_{0}}).$
Therefore $g$ gives an isomorphism between the hypergraphs $H$ and
$H^{\prime}.$

##  3 Connected 1-Factorisations of $\mathcal{F}_{q}$

In this section we prove Theorem 1.1, noting that
$\mathcal{F}_{2},\mathcal{F}_{5},\mathcal{F}_{8}$, and $\mathcal{F}_{11}$ were
shown to be C1Fs in [6]. The graph theoretic properties of the factorisation
$\mathcal{F}_{q}$ can be rephrased in terms of the action of
$\mathrm{PSL}(2,q)$ on $\mathrm{PG}(1,q).$ We explain this first. Note that
whenever we refer to the action of a group on $\mathrm{PG}(1,q),$ we
understand this to mean that the group is embedded into $\mathrm{PSL}(2,q)$ or
$\mathrm{PGL}(2,q),$ and the action is the one described in §2.

######  Lemma 3.1.

The 1-factorisation $\mathcal{F}_{q}$ is a connected 1-factorisation if and
only if the subgroup $H_{\alpha,\beta}=\langle f,m_{\alpha,\beta}\rangle$ acts
transitively on $\mathrm{PG}(1,q)$ for each
$(\alpha,\beta)\in\mathbb{F}_{q}^{*}\times\mathbb{F}_{q}.$ Such a subgroup
$H_{\alpha,\beta}$ has at least four elements of order $3.$

###### Proof.

As seen above, two vertices of $V$ are in the same edge of $F_{\alpha,\beta}$
if and only if they are in the same orbit under the action of $\langle
m_{\alpha,\beta}\rangle$ on $\mathrm{PG}(1,q).$ Similarly, the union of two
1-factors $F_{1,0}\cup F_{\alpha,\beta}$ is connected if and only if the
action of the subgroup $H:=\langle f,m_{\alpha,\beta}\rangle$ acts
transitively on $\mathrm{PG}(1,q).$ Indeed, for $x,y\in V$ a path from $x$ to
$y$ along edges from $F_{1,0}$ and $F_{\alpha,\beta}$ corresponds to an
element $w\in\mathrm{PSL}(2,q)$ such that $w(x)=y$ and $w=f^{i_{0}}\circ
m_{\alpha,\beta}^{i_{1}}\circ f^{i_{2}}\circ\cdots\circ
m_{\alpha,\beta}^{i_{\ell}}\in H$, $i_{k}\in\\{-1,0,1\\}$ ($0\leq k\leq\ell$).
The first statement now follows from Remark 2.2.

Furthermore if $F_{\alpha,\beta}\neq F_{1,0}$ then
$f,f^{-1},m_{\alpha,\beta},m_{\alpha,\beta}^{-1}$ are four distinct elements
of $H_{\alpha,\beta}$ that each have order 3. ∎

According to Lemma 3.1, the subgroups of $\mathrm{PSL}(2,q)$ are relevant for
deciding whether $\mathcal{F}_{q}$ is a C1F or not. We recall the following
theorem classifying all subgroups of ${{PSL}}(2,q)$.

######  Theorem 3.2.

[13, Theorem 6.25] Let $q=p^{s},$ $d=\gcd(2,p-1).$ Every subgroup of
$PSL(2,q)$ is isomorphic to (at least) one of the following.

  1. (a)

The dihedral groups of orders $\frac{2(q\pm 1)}{d}$ and their subgroups.

  2. (b)

A group $K$ of order $\frac{q(q-1)}{d}$ and its subgroups. A Sylow
$p$-subgroup $Q$ of $K$ is elementary Abelian, normal in $K,$ and the factor
group $K/Q$ is a cyclic group of order $\frac{q-1}{d}.$

  3. (c)

$A_{4},S_{4},$ or $A_{5}.$

  4. (d)

${{PSL}}(2,p^{r})$ or ${{PGL}}(2,p^{r})$ where $r|s.$ Note
${{PSL}}(2,2^{r})={{PGL}}(2,2^{r})$. Further, for $p>2$, ${{PGL}}(2,p^{r})$
does not occur if $r=s$.

We wish to understand which of the above subgroups are isomorphic to the
subgroups obtained by taking the union of a pair of 1-factors of
$\mathcal{F}_{q}$. We may eliminate some right away. This is the content of
the following.

######  Corollary 3.3.

Let $q$ be an odd prime such that $q\equiv 2\pmod{3}$. Let
$F_{\alpha,\beta}\in{\mathcal{F}}_{q}$ be a 1-factor that is different from
$F_{1,0},$ and let $H_{\alpha,\beta}=\langle f,m_{\alpha,\beta}\rangle.$ Then
$H_{\alpha,\beta}$ is isomorphic to $A_{4},$ $S_{4}$ or $A_{5},$ or
$H_{\alpha,\beta}=\mathrm{PSL}(2,q).$

###### Proof.

In the notation of Theorem 3.2 we have $s=1$ and $d=2.$ Further, $q\equiv
2\pmod{3}$ implies that $3\nmid\frac{q(q-1)}{2}.$ Since by Lemma 3.1
$H_{\alpha,\beta}$ has at least four distinct elements of order $3,$ it
follows that $H_{\alpha,\beta}$ is neither dihedral, nor a subgroup of a group
$K$ of order $\frac{q(q-1)}{d}.$ Therefore it is either the entire group
$\mathrm{PSL}(2,q),$ or isomorphic to one of $A_{4},$ $S_{4}$ or $A_{5}.$ ∎

We now show that for certain conditions on $q$ we can find pairs of 1-factors
whose corresponding subgroup does not act transitively on $PG(1,q)$.

######  Lemma 3.4.

Let $q\equiv 2\pmod{3}$. If $q=p^{\ell}$ for some odd prime $p\geq 5$ and some
integer $\ell\geq 2$, or $q=2^{r}$ for some odd composite $r$, then
$\mathcal{F}_{q}$ is not a C1F.

###### Proof.

Under the conditions of the lemma we have a $5\leq q^{\prime}<q$ such that
$\mathbb{F}_{q^{\prime}}\subset\mathbb{F}.$ Indeed if $q=p^{\ell}$, then take
$q^{\prime}=p.$ If $q=2^{r},$ then take $q=2^{r^{\prime}}$ for $r^{\prime}$
the smallest prime divisor of $r.$ (Here $q^{\prime}\equiv 2\pmod{3}$ from the
same property of $q.$)

Consider some $\alpha\in\mathbb{F}_{q^{\prime}}^{\ast}$ and
$\beta\in\mathbb{F}_{q^{\prime}}$ such that $F_{\alpha,\beta}\neq F_{1,0}.$
Such a pair exists, since there are at least $5(5-1)-2=20$ choices for the
pair $(\alpha,\beta)$ outside of $\\{(1,0),(1,-1)\\}.$ For such a choice, all
vertices in $\mathbb{F}_{q^{\prime}}\cup\\{\infty\\}$ will appear in edges
only with other vertices of $\mathbb{F}_{q^{\prime}}\cup\\{\infty\\}$ in both
$F_{\alpha,\beta}$ and $F_{1,0}$. Thus the subgraph $F_{\alpha,\beta}\cup
F_{1,0}$ has no edges that include vertices from both
$\mathbb{F}_{q^{\prime}}\cup\\{\infty\\}$ and
$\mathbb{F}\setminus\mathbb{F}_{q^{\prime}},$ and is therefore disconnected.

In other words, the choice of $(\alpha,\beta)$ implies that
$H_{\alpha,\beta}=\langle f,m_{\alpha,\beta}\rangle$ is a subgroup of
$\mathrm{PSL}(2,q^{\prime}).$ Therefore it leaves
$\mathrm{PG}(1,q^{\prime})\subset\mathrm{PG}(1,q)$ invariant, and does not act
transitively on $\mathrm{PG}(1,q).$ ∎

Therefore $\mathcal{F}_{q}$ may only be a C1F if $q$ is an odd prime, or
$q=2^{p}$ for some odd prime $p$.

######  Lemma 3.5.

Let $q$ be an odd prime such that $q\equiv 2\pmod{3}$. If $q>11$ then
$\mathcal{F}_{q}$ is not a C1F.

###### Proof.

It follows from Lemma 3.1 that it suffices to show that there are two
different 1-factors, $F_{\alpha,\beta}$ and
$F_{\alpha^{\prime},\beta^{\prime}}$ such that the action of the subgroup
$H=\langle m_{\alpha,\beta},m_{\alpha^{\prime},\beta^{\prime}}\rangle$ of
$\mathrm{PSL}(2,q)$ is not transitive on $\mathrm{PG}(1,q).$ This follows if
we show that there are two elements $m_{\alpha,\beta}$ and
$m_{\alpha^{\prime},\beta^{\prime}},$ corresponding to different 1-factors,
that are contained in a subgroup of $\mathrm{PSL}(2,q)$ that is isomorphic to
$A_{4}.$ Indeed, this would mean that $|H|\leq|A_{4}|=12,$ and in turn that
$H$ is not transitive on $\mathrm{PG}(1,q),$ which has more than $12$
elements.

From [4] we know that if $q$ is odd and $3|q+1$ then $\mathrm{PSL}(2,q)$
contains $\frac{q(q^{2}-1)}{24}$ copies of $A_{4}$ and that each $C_{3}$
subgroup of ${{PSL}}(2,q)$ is contained in $\frac{q+1}{3}$ subgroups $A_{4}.$
There are $\frac{q(q-1)}{2}$ 1-factors in $\mathcal{F}_{q}$, each
corresponding to a distinct copy of $C_{3}$ inside $\mathrm{PSL}(2,q).$ Each
one of these elements is contained in $\frac{q+1}{3}$ copies of $A_{4}$. If no
two were contained in the same copy of $A_{4},$ then there would be at least
$\frac{q(q-1)(q+1)}{6}$ copies of $A_{4}$ in a subgroup of $PSL(2,q).$ Since
there are only $\frac{q(q^{2}-1)}{24}$ such copies of $A_{4}$, this is a
contradiction. This completes the proof. ∎

Thus for $\mathcal{F}_{q}$ to be a C1F, $q<11$ or $q=2^{p}$ for some odd prime
$p$. To show that $\mathcal{F}_{2^{p}}$ is indeed a C1F, we need to make use
of the following facts.

######  Lemma 3.6.

[12, §2.5 Remarque] The group $PSL(2,2^{p})={{PGL}}(2,2^{p})$ has no subgroup
isomorphic to $S_{4}.$ It contains a subgroup isomorphic to $A_{4}$ or $A_{5}$
under the following conditions:

  1. (a)

$PSL(2,2^{p})$ contains $A_{4}$ if and only if there exists an
$x\in\mathbb{F}_{2^{p}}$ such that $x^{2}+x=1$.

  2. (b)

$PSL(2,2^{p})$ contains $A_{5}$ if and only if there exist
$x,y,z\in\mathbb{F}_{2^{p}}$ such that $x^{2}+x=1$ and $y^{2}+z^{2}=-1$.

######  Lemma 3.7.

If $q=2^{p}$ for some odd prime $p$, then $\mathcal{F}_{q}$ is a C1F.

###### Proof.

By Lemma 3.1 it suffices to show that $H_{\alpha,\beta}=\langle
f,m_{\alpha,\beta}\rangle$ acts transitively on $\mathrm{PG}(1,q)$ whenever
$F_{\alpha,\beta}\neq F_{1,0}.$ By Remark 2.1 there is no $x\in\mathbb{F}_{q}$
such that $x^{2}+x+1=0.$ In characteristic $2$ this is equivalent to
$x^{2}+x=1.$ Thus by Lemma 3.6 above, $H_{\alpha,\beta}$ is not isomorphic to
$S_{4},$ $A_{4}$ or $A_{5}.$ It follows from Corollary 3.3 that
$H_{\alpha,\beta}=\mathrm{PSL}(2,q)$ is the entire group. It therefore acts
transitively on $\mathrm{PG}(1,q).$ This completes the proof. ∎

The proof of Theorem 1.1 follows by combining Lemmas 3.4, 3.5, and 3.7 with
the knowledge from [6] that $\mathcal{F}_{2},\mathcal{F}_{5},$ and
$\mathcal{F}_{11}$ are C1Fs.

##  4 Uniform 1-Factorisations

In this section we prove Theorem 1.2, noting that $\mathcal{F}_{5}$ and
$\mathcal{F}_{8}$ were shown to be U1Fs (and UC1Fs) in [6].

For two distinct 1-factors $F_{1}$ and $F_{2}$ of a hypergraph, we say that a
pair of vertices, $B=\\{v_{1},v_{2}\\}$, is _repeated_ in the pair $F_{1}$ and
$F_{2}$ if $B\subseteq e$ for some edge $e\in F_{1}$ and $B\subseteq
e^{\prime}$ for some edge $e^{\prime}\in F_{2}$. We call the number of
repeated pairs in a pair of 1-factors the _pair overlap number_. If each pair
of distinct 1-factors of a 1-factorisation have the same pair overlap number,
we call that the _pair overlap number_ of the 1-factorisation. Davies et al.
[6] showed that if a U1F of $K_{n}^{3}$ exists then the pair overlap number of
the 1-factorisation is 2. Thus in order to prove that $\mathcal{F}_{q}$ is not
a U1F, we need only show that there exist two distinct 1-factors with pair
overlap number not equal to 2.

Let $F_{1,0}$ and $F_{\alpha,\beta}$ be distinct 1-factors of
$\mathcal{F}_{q}$, with corresponding functions $f$ and $m_{\alpha,\beta}$ for
$\alpha\in\mathbb{F}^{*}$ and $\beta\in\mathbb{F}$. Recall that this is the
case if and only if $(\alpha,\beta)\not\in\\{(1,0),(-1,1)\\}$ in $\mathbb{F}$.
Observe that the pair overlap number of $F_{1,0}$ and $F_{\alpha,\beta}$ is

$|\\{x\in\mathbb{F}\cup\\{\infty\\}\,\,:\,\,f(x)=m_{\alpha,\beta}(x)\\}|+|\\{x\in\mathbb{F}\cup\\{\infty\\}\,:\,f^{-1}(x)=m_{\alpha,\beta}(x)\\}|.$

This means that every repeated pair corresponds to a solution to either
$f(x)=m_{\alpha,\beta}(x)$ or $f^{-1}(x)=m_{\alpha,\beta}(x)$.

We will now consider the number of solutions for $f(x)=m_{\alpha,\beta}(x)$
with values of $\alpha$ and $\beta$ that result in $F_{\alpha,\beta}$ being
distinct from $F_{1,0}$. A solution to $f(x)=m_{\alpha,\beta}(x)$ gives us the
equation

$\frac{1}{1-x}=\beta+\frac{\alpha^{2}}{\alpha+\beta-x}.$

We note that for $x=\infty$, $f(\infty)=0$ and
$m_{\alpha,\beta}(\infty)=\beta$ so there is at least one solution if
$\beta=0$, and only one if $\beta=0$, $\alpha=-1$, and $F_{1,0}\neq F_{-1,0}$.
Further, if $\beta=0$, $\alpha\not\in\\{-1,1\\}$, then we also get the
solution $x=\frac{\alpha}{1+\alpha}$. If $\alpha+\beta=1$ then the only
solutions are $x=1$ and $x=-\alpha$. (Note
$\left(\alpha,\beta\right)\neq\left(1,0\right)$. We may have $\alpha=-1$.) We
now consider the case where $\alpha+\beta\neq 1$. Then
$f(x)=m_{\alpha,\beta}(x)$ implies $x\not\in\\{1,\alpha+\beta\\}$, every
solution is in $\mathbb{F}$ and $f(x)=m_{\alpha,\beta}(x)$ is equivalent to

$\displaystyle
0=(\alpha^{2}+\alpha\beta-\alpha+\beta^{2}-\beta)-x(\alpha^{2}+\alpha\beta+\beta^{2}+\beta-1)+\beta
x^{2}.$ (1)

We will now consider the number of solutions for
$f^{-1}(x)=m_{\alpha,\beta}(x)$ for values of $\alpha$ and $\beta$ that result
in $F_{\alpha,\beta}$ being distinct from $F_{1,0}$. A solution to
$f^{-1}(x)=m_{\alpha,\beta}(x)$ gives us the equation

$1-\frac{1}{x}=\beta+\frac{\alpha^{2}}{\alpha+\beta-x}.$

Note that $f^{-1}(\infty)=1$ and $m_{\alpha,\beta}(\infty)=\beta$, so there is
at least one solution if $\beta=1$. If $\beta=1$ we may assume $\alpha\neq-1$
as we require $F_{\alpha,\beta}$ to be distinct from $F_{1,0}$, and then we
have the solution $x=\frac{1}{1-\alpha}$ which is $\infty$ if $\alpha=1$. If
$\alpha+\beta=0$ then $f^{-1}(0)=m_{\alpha,\beta}(0)=\infty,$ so $x=0$ and
$x=1-\alpha$ give solutions. Now assume that $\beta\neq 1$ and
$\alpha+\beta\neq 0.$ Then $f^{-1}(x)=m_{\alpha,\beta}(x)$ implies
$x\notin\\{0,\alpha+\beta\\},$ every solution is in $\mathbb{F}$ and
$f^{-1}(x)=m_{\alpha,\beta}(x)$ is equivalent to

$\displaystyle
0=(1-\beta)x^{2}+x(\alpha^{2}+\alpha\beta+\beta^{2}-\alpha-\beta-1)+(\alpha+\beta).$
(2)

To summarise the above we have the following.

$\begin{array}[]{p{3.4cm}|p{11cm}}$\hskip
5.40608pt\text{Conditions}$&$\\{x\in\mathbb{F}\cup\\{\infty\\}\mid
f(x)=m_{\alpha,\beta}(x)\\}$\\\ \hline\cr\hline\cr$\hskip 5.40608pt\beta=0,\
\alpha=-1$&$\\{\infty\\}$\\\ \hline\cr$\hskip 5.40608pt\beta=0,\
\alpha\not\in\\{-1,1\\}$&$\\{\infty,\frac{\alpha}{1+\alpha}\\}$\\\
\hline\cr$\hskip 5.40608pt\beta\neq 0,\ \alpha+\beta=1$&$\\{1,-\alpha\\}$\\\
\hline\cr$\begin{array}[]{p{3.5cm}}$\beta\neq 0,\ \alpha+\beta\neq 1,$\\\
$((\alpha,\beta)\neq(-1,1))$\end{array}$&$\\{x\in\mathbb{F}\mid\beta
x^{2}-(\alpha^{2}+\alpha\beta+\beta^{2}+\beta-1)x+(\alpha^{2}+\alpha\beta+\beta^{2}-\alpha-\beta)=0\\}$\end{array}$

$\begin{array}[]{p{3.4cm}|p{11cm}}$\hskip
5.40608pt\text{Conditions}$&$\\{x\in\mathbb{F}\cup\\{\infty\\}\mid
f^{-1}(x)=m_{\alpha,\beta}(x)\\}$\\\ \hline\cr\hline\cr$\hskip
5.40608pt\beta=1,\ \alpha=1$&$\\{\infty\\}$\\\ \hline\cr$\hskip
5.40608pt\beta=1,\
\alpha\not\in\\{-1,1\\}$&$\\{\infty,\frac{1}{1-\alpha}\\}$\\\ \hline\cr$\hskip
5.40608pt\beta\neq 1,\ \alpha+\beta=0$&$\\{0,1-\alpha\\}$\\\
\hline\cr$\begin{array}[]{p{3.5cm}}$\beta\neq 1,\ \alpha+\beta\neq 0,$\\\
$\left((\alpha,\beta)\neq(-1,1)\right)$\end{array}$&$\\{x\in\mathbb{F}\mid(1-\beta)x^{2}+(\alpha^{2}+\alpha\beta+\beta^{2}-\alpha-\beta-1)x+(\alpha+\beta)=0\\}$\end{array}$

We use the information in the tables to show that $\mathcal{F}_{q}$ is not a
U1F if $q\notin\\{5,8\\}.$ The cases of $5|q$ and $2|q$ are treated separately
from that of other primes. We start with the case of primes greater than 5.

######  Lemma 4.1.

Let $q=p^{\ell}$ for some prime $p>5$ and some integer $\ell\geq 1$ such that
$q\equiv 2\pmod{3}$. Then $\mathcal{F}_{q}$ is not a U1F.

###### Proof.

Let $F_{1,0}$ and $F_{-1,0}$ be 1-factors of $\mathcal{F}_{q}$; we shall prove
that the pair overlap number of this pair of 1-factors is not 2. $F_{1,0}$ and
$F_{-1,0}$ are distinct, and from above we know that there is only one
repeated pair corresponding to a solution to $f(x)=m_{-1,0}(x)$. Further, we
know that $\\{x\in\mathbb{F}_{q}\cup\\{\infty\\}\ |\
f^{-1}(x)=m_{-1,0}(x)\\}=\\{x\in\mathbb{F}_{q}\ |\ x^{2}+x-1=0\\}$, and
$x^{2}+x-1=0$ will have 2 solutions in $\mathbb{F}_{q}$ if $5$ is a quadratic
residue, and 0 if not. Thus the pair overlap number of this pair of 1-factors
must be either 1 or 3, and thus $\mathcal{F}_{q}$ is not a U1F. ∎

######  Lemma 4.2.

Let $q=5^{\ell}$ for some integer $\ell>1$ such that $q\equiv 2\pmod{3}$. Then
$\mathcal{F}_{q}$ is not a U1F.

###### Proof.

As in the proof of Lemma 4.1 we show that there is a choice of $\alpha,\beta$
such that the pair overlap number of $F_{1,0}$ and $F_{\alpha,\beta}$ is not
2. This implies that $\mathcal{F}_{q}$ is not a U1F. We shall show that for
$\alpha\in\mathbb{F}\setminus\mathbb{F}_{5}$ the factor $F_{1,0}$ has a pair
overlap number of $4$ with at least one of $F_{\alpha,-\alpha},$
$F_{\alpha,1-\alpha}$ or $F_{\alpha^{2},1-\alpha^{2}}.$

It follows from the tables above that if
$\alpha\in\mathbb{F}\setminus\mathbb{F}_{5}$ and we set $\beta=-\alpha$ then
$f^{-1}(x)=m_{\alpha,-\alpha}$ has the two distinct solutions $0$ and
$1-\alpha$. The solutions of $f(x)=m_{\alpha,-\alpha}$ are $x\in\mathbb{F}$
such that $\alpha x^{2}+(\alpha^{2}-\alpha-1)x-\alpha^{2}=0.$ The discriminant
is $D_{1}=(\alpha-1)^{2}\cdot(\alpha^{2}-\alpha+1).$ Therefore the pair
overlap number between $F_{1,0}$ and $F_{\alpha,-\alpha}$ is $4$ if
$\alpha^{2}-\alpha+1$ is a square in $\mathbb{F}$.

Now set $\beta=1-\alpha$ in the tables above. If
$\alpha\in\mathbb{F}\setminus\mathbb{F}_{5}$ then $f(x)=m_{\alpha,1-\alpha}$
has the two distinct solutions, $1$ and $-\alpha$. The solutions of
$f^{-1}(x)=m_{\alpha,1-\alpha}$ are $x\in\mathbb{F}$ such that $\alpha
x^{2}+(\alpha^{2}-\alpha-1)x+1=0.$ The discriminant is
$D_{2}=(\alpha+1)^{2}\cdot(\alpha^{2}+\alpha+1).$ Therefore the pair overlap
number between $F_{1,0}$ and $F_{\alpha,1-\alpha}$ is $4$ if
$\alpha^{2}+\alpha+1$ is a square in $\mathbb{F}$.

Now take an $\alpha\in\mathbb{F}\setminus\mathbb{F}_{5}.$ If
$\alpha^{2}-\alpha+1\in\mathbb{F}^{2}$ or
$\alpha^{2}+\alpha+1\in\mathbb{F}^{2}$ then the pair overlap number of
$F_{1,0}$ with $F_{\alpha,-\alpha}$ or with $F_{\alpha,1-\alpha}$ is not $2$
by the above paragraphs. Recall that $\mathbb{F}^{\ast}$ is a cyclic group,
therefore the product of two non-squares is a square. Therefore if
$\alpha^{2}-\alpha+1\notin\mathbb{F}^{2}$ and
$\alpha^{2}+\alpha+1\notin\mathbb{F}^{2},$ then their product is a square:
$(\alpha^{2}-\alpha+1)(\alpha^{2}+\alpha+1)=(\alpha^{2})^{2}+\alpha^{2}+1\in\mathbb{F}^{2}.$

Observe that $q\equiv 2\pmod{3}$ implies that $\ell$ is odd. Therefore
$\mathbb{F}$ does not contain the field of $25$ elements. This implies that
for $\alpha\in\mathbb{F}\setminus\mathbb{F}_{5}$ we have
$\alpha^{2}\in\mathbb{F}\setminus\mathbb{F}_{5}$. Thus using similar working
to above, the pair overlap number of $F_{1,0}$ and
$F_{\alpha^{2},1-\alpha^{2}}$ is $4$. ∎

We now turn our attention to the case where $q=2^{\ell}$ for $\ell$ an odd
integer, $\ell>3$. We shall show that then $\mathcal{F}_{q}$ is not a U1F by
proving that there is an $\alpha\in\mathbb{F}_{q}\setminus\\{0,1\\}$ such that
the pair overlap number of $F_{1,0}$ with $F_{\alpha,1}$ or $F_{\alpha,0}$ is
not $2$. As in the case of odd characteristic, the proof involves considering
the number of solutions of the quadratic equations (1) and (2) in special
cases. To do so we recall the following.

######  Lemma 4.3.

Let $\ell$ be a positive integer and set $\mathbb{F}=\mathbb{F}_{2^{\ell}}.$
The field extension $\mathbb{F}|\mathbb{F}_{2}$ is cyclic, its Galois group
generated by the Frobenius automorphism $x\mapsto x^{2}.$ The trace map:
${\mathrm{Tr}}={\mathrm{Tr}}_{\mathbb{F}_{2}}^{\mathbb{F}}:\mathbb{F}\rightarrow\mathbb{F}_{2}$
given by

${\mathrm{Tr}}(x)={\mathrm{Tr}}_{\mathbb{F}_{2}}^{\mathbb{F}_{2^{\ell}}}(x)=\sum_{i=0}^{\ell-1}x^{2^{i}}$
(3)

is an $\mathbb{F}_{2}-$linear map. For any $x\in\mathbb{F}$ we have
$x^{2^{\ell}}=x.$ For $x\in\mathbb{F}$ there exists an $r\in\mathbb{F}$ such
that $x=r^{2}+r$ if and only if ${\mathrm{Tr}}(x)=0.$ A quadratic equation
$x^{2}+Lx+C$ with $L\neq 0$ has two solutions in $\mathbb{F}$ if
${\mathrm{Tr}}\left(\frac{C}{L^{2}}\right)=0,$ and zero solutions otherwise.
If $\ell$ is an odd integer then ${\mathrm{Tr}}(1)=1.$

###### Proof.

For general facts about the trace map, see [10, §5]. The fact that $x=r^{2}+r$
has a solution if and only if ${\mathrm{Tr}}(x)=0$ is the additive form of
Hilbert’s Theorem 90 [10, Theorem 6.3]. The statement about the number of
roots of a quadratic equation follows from the Artin-Schreier theorem [10,
Theorem 6.4] by a change of variables. See for example [11, Proposition 1]. ∎

We now have the following.

######  Lemma 4.4.

Let $q=2^{\ell}$ with $\ell$ a positive odd integer, and set
$\mathbb{F}=\mathbb{F}_{2^{\ell}},$
${\mathrm{Tr}}={\mathrm{Tr}}^{\mathbb{F}}_{\mathbb{F}_{2}}$ as in (3). If
there exists an $\alpha\in\mathbb{F}^{\ast}$ such that

${\mathrm{Tr}}\left(\frac{\alpha}{(\alpha^{2}+\alpha+1)^{2}}\right)=0\text{ or
}{\mathrm{Tr}}\left(\frac{\alpha^{2}}{(\alpha^{2}+\alpha+1)^{2}}\right)=0$ (4)

then ${\mathcal{F}}_{q}$ is not a U1F.

###### Proof.

First note that for $\alpha=1$ the conditions in (4) are not satisfied since
$\mathrm{Tr}(1)\neq 0$, so we only consider $\alpha\neq 1$. Therefore
$F_{1,0}$ is different from both $F_{\alpha,0}$ and from $F_{\alpha,1}.$
Recall the discussion at the beginning of the section about the pair overlap
number of the two 1-factors, $F_{1,0}$ and $F_{\alpha,\beta}.$ Specialising
the corresponding tables to characteristic $2$ and $\beta\in\\{0,1\\}$ we find
that the solutions are as follows.

$\begin{array}[]{c|c|c}\text{Conditions}&\\{x\in\mathbb{F}\cup\\{\infty\\}\mid
f(x)=m_{\alpha,\beta}(x)\\}&\\{x\in\mathbb{F}\cup\\{\infty\\}\mid
f^{-1}(x)=m_{\alpha,\beta}(x)\\}\\\ \hline\cr\hline\cr\beta=0\ (\alpha\neq
1)&\\{\infty,\frac{\alpha}{1+\alpha}\\}&\\{x\in\mathbb{F}\mid
x^{2}+(\alpha^{2}+\alpha+1)x+\alpha=0\\}\\\ \hline\cr\beta=1\ (\alpha\neq
1)&\\{x\in\mathbb{F}\mid
x^{2}+(\alpha^{2}+\alpha+1)x+\alpha^{2}=0\\}&\\{\infty,\frac{1}{1+\alpha}\\}\end{array}$

It follows that if
${\mathrm{Tr}}\left(\frac{\alpha}{(\alpha^{2}+\alpha+1)^{2}}\right)=0$ then
the quadratic equation $x^{2}+(\alpha^{2}+\alpha+1)x+\alpha=0$ has two
solutions by Lemma 4.3 and then $F_{1,0}$ and $F_{\alpha,0}$ have a pair
overlap number of $4$. On the other hand if
${\mathrm{Tr}}\left(\frac{\alpha^{2}}{(\alpha^{2}+\alpha+1)^{2}}\right)=0$
then $x^{2}+(\alpha^{2}+\alpha+1)x+\alpha^{2}=0$ has two solutions and
therefore $F_{1,0}$ and $F_{\alpha,1}$ have a pair overlap number of $4$. Thus
the pair overlap number of $\mathcal{F}_{q}$ is not two and this implies that
$\mathcal{F}_{q}$ is not a U1F. ∎

We shall show that the conditions of Lemma 4.4 are always met by an
$\alpha\in\mathbb{F}^{\ast}$ when $\mathbb{F}=\mathbb{F}_{2^{t}}$ for $t>3.$
We do this in two steps.

######  Lemma 4.5.

Let $\ell$ be a positive odd integer and set
$\mathbb{F}=\mathbb{F}_{2^{\ell}},$
${\mathrm{Tr}}={\mathrm{Tr}}^{\mathbb{F}}_{\mathbb{F}_{2}}$ as in (3). If
there is no $\alpha\in\mathbb{F}^{\ast}$ satisfying (4) then for every
$x\in\mathbb{F}\setminus\\{0,1\\}$ we have
${\mathrm{Tr}}\left(x+\frac{1}{x}\right)=1.$

###### Proof.

Suppose that there is no $\alpha\in\mathbb{F}^{*}$ satisfying (4). Recall that
since ${\mathrm{Tr}}:\mathbb{F}\rightarrow\mathbb{F}_{2}$ is a surjective
$\mathbb{F}_{2}-$linear map, its kernel is an index $2$ subgroup of the
additive group $\mathbb{F}$, call this subgroup $R$. Every element not in $R$
has trace $1.$ It therefore suffices to show that $x$ and $\frac{1}{x}$ are in
different cosets of $R$ for every $x\in\mathbb{F}\setminus\\{0,1\\}.$

First assume that $x\neq 1$ and ${\mathrm{Tr}}(x)=1$. Since
${\mathrm{Tr}}(1)=1$ we have ${\mathrm{Tr}}(x+1)=0$ and so $x=r^{2}+r+1$ for
some $r\in\mathbb{F}\setminus\\{0,1\\}.$ Since neither $r$ nor $r+1$ satisfy
the conditions in (4) of Lemma 4.4, we have that

${\mathrm{Tr}}\left(\frac{r^{2}}{(r^{2}+r+1)^{2}}\right)=1\text{ and
}{\mathrm{Tr}}\left(\frac{r+1}{(r^{2}+r+1)^{2}}\right)=1.$

It follows that the sum of these elements has trace zero:

$0={\mathrm{Tr}}\left(\frac{r^{2}}{(r^{2}+r+1)^{2}}+\frac{r+1}{(r^{2}+r+1)^{2}}\right)={\mathrm{Tr}}\left(\frac{1}{r^{2}+r+1}\right)={\mathrm{Tr}}\left(\frac{1}{x}\right).$

Thus taking reciprocals maps
$\\{h\in\mathbb{F}\setminus\\{1\\}\,:\,{\mathrm{Tr}}(h)=1\\}$ into
$\\{h\in\mathbb{F}^{\ast}\,:\,{\mathrm{Tr}}(h)=0\\}.$ These sets both have
$2^{\ell-1}-1$ elements, therefore this is in fact a bijection. That is, for
any $x\in\mathbb{F}\setminus\\{0,1\\}$ we have
${\mathrm{Tr}}(x)\neq{\mathrm{Tr}}\left(\frac{1}{x}\right),$ hence
${\mathrm{Tr}}\left(x+\frac{1}{x}\right)=1.$ ∎

Putting Lemmas 4.4 and 4.5 together we see that ${\mathcal{F}}_{q}$ is not a
U1F for $q=2^{\ell},$ $\ell$ an odd integer greater than 3, unless a somewhat
strange condition is satisfied by $\mathbb{F}=\mathbb{F}_{2^{\ell}}$. We show
that this condition is indeed strange, and is in fact not satisfied for any
$\ell>3.$

######  Lemma 4.6.

Let $\ell$ be a positive odd integer and set
$\mathbb{F}=\mathbb{F}_{2^{\ell}},$
${\mathrm{Tr}}={\mathrm{Tr}}^{\mathbb{F}}_{\mathbb{F}_{2}}$ as in (3). If
$\ell>3$ then not all $x\in\mathbb{F}\setminus\\{0,1\\}$ satisfy

${\mathrm{Tr}}\left(x+\frac{1}{x}\right)=1.$ (5)

###### Proof.

Observe that if $x$ satisfies (5) then we have:

$\begin{split}x^{2^{\ell-1}}\cdot{\mathrm{Tr}}\left(x+\frac{1}{x}\right)=x^{2^{\ell-1}}\cdot\sum_{i=0}^{\ell-1}\left(x^{2^{i}}+x^{-2^{i}}\right)&=x^{2^{\ell-1}}\\\
\sum_{i=0}^{\ell-1}\left(x^{2^{\ell-1}+2^{i}}+x^{2^{\ell-1}-2^{i}}\right)&=x^{2^{\ell-1}}\\\
x+\sum_{i=0}^{\ell-2}\left(x^{2^{\ell-1}+2^{i}}\right)+x^{2^{\ell-1}}+\sum_{i=0}^{\ell-1}\left(x^{2^{\ell-1}-2^{i}}\right)&=0\end{split}$
(6)

where the last line follows from the fact that $x^{2^{\ell}}=x$ for every
$x\in\mathbb{F}$ (see Lemma 4.3). The left-hand side here is a polynomial of
degree $2^{l-1}+2^{l-2}$ (with coefficients in $\mathbb{F}_{2}$). Therefore it
has at most $2^{l-1}+2^{l-2}$ roots in the field $\mathbb{F}$. If $\ell>3$
then $2^{\ell-1}+2^{\ell-2}<2^{\ell}-2.$ Therefore there is an
$x\in\mathbb{F}\setminus\\{0,1\\}$ that does not satisfy (5). ∎

Combining these gives us the following.

######  Corollary 4.7.

Let $q=2^{\ell}$ for some odd integer $\ell>3$. Then $\mathcal{F}_{q}$ is not
a U1F.

The proof of Theorem 1.2 then follows from Lemmas 4.1, 4.2, along with
Corollary 4.7, and the knowledge from [6] that
$\mathcal{F}_{2},\mathcal{F}_{5},\mathcal{F}_{8}$ are both U1Fs and C1Fs.

##  5 Hamilton-Berge 1-Factorisations

A necessary condition for a 1-factorisation of $K_{n}^{k}$ to be a Hamilton-
Berge 1-factorisation is that the union of each $k$-set of 1-factors is
connected. We remark that in the proof of Lemma 3.4, the subfield is actually
large enough to allow us to find three 1-factors whose union is disconnected.
We also note that in the proof of Lemma 3.5 there are not enough copies of
$A_{4}$ to ensure that no three distinct copies of $C_{3}$ are contained in
the same copy of $A_{4}$. From these two remarks it follows that if
$q=p^{\ell}$ for some prime $p\geq 5$ and some integer $\ell\geq 2$, or if
$q>11$ is prime, or if $q=2^{r}$ for some odd composite $r$, then
$\mathcal{F}_{q}$ cannot be an HB1F. Finally, it follows from Lemma 3.7 that
if $q=2^{p}$ for some odd prime $p$, then $\mathcal{F}_{q}$ satisfies the
property that the union of each set of three distinct 1-factors is connected.
Thus $\mathcal{F}_{q}$ can only be an HB1F if $q\in\\{2,5,11\\}$ or $q=2^{p}$
for some odd prime $p$. The 1-factorisations
$\mathcal{F}_{5},\mathcal{F}_{8},\mathcal{F}_{11}$, and $\mathcal{F}_{32}$
were shown to be HB1Fs in [6], and the 1-factorisation $\mathcal{F}_{2}$ is
trivially an HB1F. We have also shown computationally that $\mathcal{F}_{128}$
is an HB1F, which leads us to the following conjecture.

######  Conjecture 5.1.

$\mathcal{F}_{q}$ is a Hamilton-Berge 1-factorisation if and only if it is a
connected 1-factorisation.

Acknowledgements The authors acknowledge the support of an Australian
Government Research Training Program Scholarship, and the support of ARC grant
DE200101802.

## References

  * [1] R. Alexander.  Perfect 1-factorizations.  Mathematica Slovaca, 69(3):479–496, 2019.
  * [2] Z. Baranyai.  On the factorization of the complete uniform hypergraph.  In Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. I, pages 91–108. Colloq. Math. Soc. János Bolyai, Vol. 10. 1975.
  * [3] D. Bryant, B. Maenhaut, and I. Wanless.  New families of atomic Latin squares and perfect one-factorisations.  J. Combin. Theory Ser. A, 113:608–624, 2006.
  * [4] P. J. Cameron, H. R. Maimani, G. R. Omidi, and B. Tayfeh-Rezaie.  3-designs from ${\rm PSL}(2,q)$.  Discrete Math., 306(23):3063–3073, 2006.
  * [5] H. Y. Chen and Z. P. Lu.  Symmetric factorizations of the complete uniform hypergraph.  J. Algebraic Combin., 46(2):475–497, 2017.
  * [6] S. Davies, B. Maenhaut, and J. Mitchell.  Perfect 1-factorisations of complete hypergraphs.  Australas. J. Combin., 85(1):35–48, 2022.
  * [7] M. J. Gill and I. M. Wanless.  Perfect 1-factorisations of $k\\_${$16$}.  Bulletin of the Australian Mathematical Society, 101(2):177–185, 2020.
  * [8] T. P. Kirkman.  On a problem in combinations.  Cambridge and Dublin Mathematical Journal, 2:191–204, 1847.
  * [9] A. Kotzig.  Problem 20.  In Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), page 162. Publ. House Czech. Acad. Sci., Prague, 1964.
  * [10] S. Lang.  Algebra, volume 211 of Graduate Texts in Mathematics.  Springer-Verlag, New York, third edition, 2002.
  * [11] K. Pommerening.  Quadratic equations in finite fields of characteristic 2 (English Version).  http://www.klauspommerening.de/MathMisc/QuGlChar2.pdf, 2012.  [Online; accessed 18-May-2022].
  * [12] J.-P. Serre.  Propriétés galoisiennes des points d’ordre fini des courbes elliptiques.  Invent. Math., 15(4):259–331, 1972.
  * [13] M. Suzuki.  Group theory. I, volume 247 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences].  Springer-Verlag, Berlin-New York, 1982.  Translated from the Japanese by the author.