# Hyena Neural Operator for Partial Differential Equations

Saurabh Patil  [  Zijie Li  [  Amir Barati Farimani<EMAIL_ADDRESS>[

###### Abstract

Numerically solving partial differential equations typically requires fine
discretization to resolve necessary spatiotemporal scales, which can be
computationally expensive. Recent advances in deep learning have provided a
new approach to solving partial differential equations that involves the use
of neural operators. Neural operators are neural network architectures that
learn mappings between function spaces and have the capability to solve
partial differential equations based on data. This study utilizes a novel
neural operator called Hyena, which employs a long convolutional filter that
is parameterized by a multilayer perceptron. The Hyena operator is an
operation that enjoys sub-quadratic complexity and state space model to
parameterize long convolution that enjoys a global receptive field. This
mechanism enhances the model’s comprehension of the input’s context and
enables data-dependent weight for different partial differential equations
instances. To measure how effective the layers are in solving partial
differential equations, we conduct experiments on Diffusion-Reaction equation
and Navier Stokes equation. Our findings indicate Hyena Neural operator can
serve as an efficient and accurate model for learning partial differential
equations solution operator. The data and code used can be found at:
https://github.com/Saupatil07/Hyena-Neural-Operator

###### keywords:

American Chemical Society, LaTeX

meche] Department of Mechanical Engineering, Carnegie Mellon University, USA
meche] Department of Mechanical Engineering, Carnegie Mellon University, USA
meche] Department of Mechanical Engineering, Carnegie Mellon University, USA
[biomed] Department of Biomedical Engineering, Carnegie Mellon University, USA
[mld] Machine Learning Department, Carnegie Mellon University, USA IR,NMR,UV

##  1 Introduction

Numerical modeling of Partial differential equations (PDEs) plays a crucial
role in engineering as they serve as fundamental tools for representing and
analyzing various physical phenomena. They find application in diverse areas,
such as fluid dynamics, gas dynamics, electrical circuitry, heat transfer, and
acoustics, enabling us to model and understand these phenomena effectively.
PDEs provide a framework for understanding complex systems by describing the
relationships between various quantities that change over time and space. They
are widely used in science and engineering to make predictions, optimize
designs, and analyze data. Traditional numerical solvers for partial
differential equations (PDEs) are often costly because they rely on methods
that require a fine discretization of the problem domain. Numerous techniques
in deep learning have been proposed to address the computational complexity of
numerical solvers and to forecast fluid properties. These approaches include
reinforcement learning1, 2, 3, surrogate modeling4, 5, generative adversarial
networks (GANs)6, 7, 8, 9 and diffusion models.10, 11, 12, 13 Neural operators
are designed to operate on function representations and enable the learning of
operators directly from data. Compared to traditional solvers, they alleviate
the need for fine discretization and can be used to infer the solution of
different instances within a family of PDE once trained. One of the earliest
neural operators proposed was the DeepONet 14. It consists of a branch network
responsible for processing the input functions and learning the action of the
operator, along with a trunk network that learns the function bases for the
solution function space. Wang et al. 15 further improved the performance of
DeepONets by introducing an improved architecture and training methods. MIONet
16 extends DeepONet to problems involving multiple input functions. In
addition to DeepONet, another group of methods 17, 18 leverage a learnable
kernel integral to approximate the target operator. A notable instance is
Fourier Neural Operator 19(FNO), which utilizes the Fourier transform to learn
the convolution kernel integral in the frequency domain. The Fourier neural
operator has been further adapted to various forms as shown in (Tran et al.
20, Guibas et al. 21, Li et al. 22). Other than the Fourier domain, the
wavelet domain has also been explored in (Tripura and Chakraborty 23, Gupta et
al. 24). Cao 25 draws the connection between a softmax-free attention and two
different types of integral and proposes a attention-based operator learning
framework. Li et al. 26 further expands the work on attention by proposing to
propagate to the solution in latent space with cross-attention mechanism and
relative positional encoding27.

Various previous works 19, 25, 24 have shown that the capability of capturing
global interaction is crucial to the prediction accuracy. Non-local learnable
modules such as spectral convolution 19, attention 25 or dilated convolution
28 are better at learning complex time-evolving dynamics where other local
learnable modules like residual neural network (ResNet)29 often fails to
model. State space models (SSMs) are a type of recurrent model that can be
viewed as long-context convolution. It effectively extends the receptive field
to the whole input sequence and has the potential to learn and model complex
non-local interaction that lies in the PDE data.

The state space models are represented by the following equations:

$x(t+1)=Ax(t)+Bu(t),\quad y(t)=Cx(t)+Du(t),$ (1)

where the input $u(t)$ represents a one-dimensional signal, while the state
$x(t)$ represents an N-dimensional hidden representation that follows a linear
ordinary differential equation (ODE). The output $y(t)$ is a straightforward
one-dimensional projection of the state. $A,B,C,D$ are learned projections.
State space models 30 serve as a foundational framework widely employed in
scientific and engineering fields like control theory. Earlier examples of SSM
layers in deep learning model includes Structured State Space(S4)31, its
variants 32, 33 and Gated State Space (GSS) 34. A later work Hungry Hungry
Hippo (H3)35 was proposed to address the limitations of prior SSM layers,
specifically targeting two key drawbacks: their incapability to recall
previous tokens in the sequence and their expensive computational cost. H3
solves the associative recall by including an additional gate and a short
convolution obtained via a shift SSM. It also proposes FlashConv, a fast and
efficient algorithm for training and inferring SSMs. It works by using a fused
block FFT algorithm to compute the convolutions in the SSM, which
significantly reduces the training and inference time. Recent work Hyena 36
further extends H3 and incorporates implicit filter parametrization, advancing
the accuracy and efficiency of SSM-based model, which have achieved state-of-
the-art performance across benchmarks like LRA37.

This work presents a novel deep-learning architecture for learning PDE
solutions called Hyena Neural Operator (HNO), which utilizes long convolutions
and element-wise multiplicative gating mechanism. Hyena Neural Operator(HNO)
employs an Encoder-Decoder architecture with a latent-marching strategy26. We
demonstrate that HNO has competitive performance against Fourier Neural
Operator on various numerical benchmarks.

Figure 1: Hyena Neural Operator architecture. Given the initial observation
and the grid, the encoder layer encodes it to a latent embedding, which is an
input to the latent Hyena layers. The latent output from Hyena layers, Fourier
projection, and the grid is given as input to the cross-attention module. The
resultant values are once again passed through Hyena layers and the output
solution is obtained following an MLP layer. Figure 2: Hyena architecture. The
input to the Hyena operator is first projected to a width defined by the order
and input dimension. The projections are first passed through a short filter
and then to generated filters made on the fly. Inside the Hyena filter, the
data is processed in three steps: first the positional encoding, second the
implicit filter, and lastly the exponential modulation.

##  2 Method

###  2.1 Hyena Neural Operator

The Hyena operator can be characterized as a repetition of two sub-quadratic
operations: an implicit long convolution $h$ (which means that the Hyena
filters are implicitly parameterized by the output of a feed-forward network)
and a multiplicative component-wise control of the (projected) input. Hyena
first computes $N+1$ learnable projections111In practice it is implemented as
a single convolution layer. of the input: $(v,\xi^{1},\cdots,\xi^{N})$, which
is similar to query/key/value projections in a standard attention mechanism.
The next step is to compute the convolution filters, which are implicitly
parametrized 38, 39, 40 and modulated via a window function. Concretely, the
value of the filter $h$ on the $t$-th location is given by:

$h_{t}=\psi(t)\text{FFN}(\gamma(t)),$ (2)

where $\psi(\cdot)$ is a window function that decays exponentially with
respect to $t$: $\psi(t)=\exp(-\alpha t)$, with $\alpha$ controlling the
decaying speed, FFN denotes the feed-forward network equipped with a sine
activation function, and $\gamma(\cdot)$ is a positional encoding function:

$\gamma(t)=[t,\cos{(2\pi t/L)},\ldots,\cos{(2\pi Kt/L)},\sin{(2\pi
t/L)},\ldots,\sin{(2\pi Kt/L)}],$ (3)

with $K$ as a hyperparameter, $L$ being the length of the input sequence. The
implicit filter decouples the parameter size of the filter and its valid
receptive field. The sine activation function together with the positional
encoding function allows the filter to learn high-frequency patterns 41
whereas the exponential decaying function enables the learned filter to focus
on the different parts of the input at different steps.

With the computed filter $(h^{1},h^{2},\cdots,h^{N})$ and the projected inputs
$(v,\xi^{1},\cdots,\xi^{N})$, the update rule within a Hyena operator block is
defined as follows:

$z^{n+1}=\xi^{n}\odot\mathcal{K}(h^{n},z^{n}),\quad n=1,....,N,$ (4)

where $\mathcal{K}$ denotes the convolution operation:
$\mathcal{K}(h,u)=h*u=\sum_{n=1}^{L}h_{t-n}u_{n}$, and $\odot$ denotes
element-wise multiplication, $N$ is a hyperparameter. If we view the input
sequence as the sampling of a function on the discretization grid
$\\{x_{t}\\}_{t=1}^{N}$, then (4) can be viewed as an approximation to the
integral transform:
$z^{n+1}(x_{t})=\xi^{n}(x_{t})\int_{\Omega}h^{n}(x_{t}-y)z^{n}(y)dy$, where
the function are iteratively updated by a kernel integral and an instance-
based weight value $\xi^{n}(x_{t})$. The spectral convolution layer in FNO can
be viewed as a special case of (4) with filter’s value explicitly
parameterized and no instance-based weight.

#### Encoder

The encoder is composed of three main components, an input embedding layer
that takes in the input function’s sampling and lifts the input features into
high-dimensional encodings $\mathbf{u}^{(0)}$, multiple layers of Hyena
operator followed by feedforward networks. The output from each Hyena layer is
aggregated and then passed on to the projection layer which projects the
output from the Hyena layers to latent embedding. The latent embeddings are
passed through a series of Hyena layers and the output from the layers is once
again aggregated and passed to the decoder. The update protocol inside each
Hyena operator block is:

$\mathbf{u}^{(l^{\prime})}=\mathbf{k}^{(l)}+\text{Norm}\left(\text{Hyena}(\mathbf{u}^{(l)})\right),\quad\mathbf{u}^{(l+1)}=\text{FFN}(\mathbf{u}^{(l^{\prime})}),$
(5)

where $\text{Hyena}(\cdot)$ denotes the Hyena operator, $\text{Norm}(\cdot)$
denotes the layer normalization layer 42.

#### Decoder

To generate the solution, the decoder utilizes the input coordinates and the
output obtained from the encoder. The first layer is a random Fourier
projection layer41, 43. By incorporating random Fourier projection, the
inherent spectral bias found in coordinate-based neural networks is alleviated
41, 38. Following the Fourier projection, the latent encoding
$\mathbf{u}^{(L)}$, along with the encoding of positions $\mathbf{p}^{(0)}$
that has been learned, is fed into the cross-attention module inspired by the
Li et al. 26. Finally, the decoder outputs the prediction by taking the result
of the cross-attention module, passing it through the Hyena operator, and then
applying a feed-forward network. The decoder process can be described as
follows:

$\mathbf{p}^{\prime}=\mathbf{p}^{(0)}+\text{Cross-
Attn}(\mathbf{p}^{(0)},\mathbf{u}^{(L)}),\quad\mathbf{p}^{\prime\prime}=\mathbf{p}^{\prime}+\text{Hyena}(\mathbf{p}^{\prime}),\quad\mathbf{p}=\mathbf{p}^{\prime\prime}+\text{FFN}(\mathbf{p}^{\prime\prime}).$
(6)

#### Training settings

The overall training framework of this work shares similarities with previous
data-driven models focused on operator learning. We used the Adam optimizer44
and a CosineAnnealing scheduler45 with a decay rate of $1e-8$. The dropout
rate was set to $0.03$ inside the feedforward layers of the Hyena operator.
Unless stated we have trained the models for 500 epochs with an initial
learning rate set as $1\text{\times}{10}^{-4}$. We use GELU46 activation. To
train the model on 2D Navier-Stokes data, we employ a curriculum strategy that
involves gradually increasing the prediction time steps following Li et al.
26. Instead of forecasting all upcoming states until the end of the specified
time horizon, we initially limit the duration by a fraction called $\gamma$
(around $\gamma\approx 0.5$) and then gradually grow the time duration as the
training progresses. In this approach, the network is trained to predict the
states $u_{t_{0}},u_{t_{1}},\ldots,u_{\gamma T}$. We found that implementing
the above strategy worked better than asking the model to predict the whole
sequence at once which consequently improves stability and leads to slightly
faster convergence.

Figure 3: Visualization of time evolution of 1D Diffusion-Reaction equation.
Black dotted lines denote the model’s output. The blue line denote the initial
condition given as input to the models.

##  3 Numerical Experiments

We assess our model’s performance using benchmark problems, we consider the 2D
Navier-Stokes equation and the 1D Diffusion-Reaction equation. To ensure a
comprehensive assessment, we conduct a comparative analysis between the
performance of our model and that of the state-of-the-art neural operator,
namely the Fourier neural operator. Detailed insights into our model’s
architecture for different problems are available in Appendix A.

###  3.1 1D Diffusion-Reaction

We used the dataset provided by PDEBench47 a benchmark for SciML. The data
consist of an one-dimensional diffusion-reaction type PDE, that combines a
diffusion process and a rapid evolution from a source term 48. The equation is
expressed as:

$\displaystyle\partial_{t}u(t,x)$ $\displaystyle-\nu\partial_{xx}u(t,x)-\rho
u(1-u)=0,~{}~{}~{}x\in(0,1),t\in(0,1],$ (7) $\displaystyle u(0,x)$
$\displaystyle=u_{0}(x),~{}~{}~{}x\in(0,1).$ (8)

We evaluate the performance of Fourier neural operator and Hyena neural
operator on different values of $\nu=0.5,2.0$ at different resolutions. We
provide the condition at the initial time step and the model predicts the
solution at the final time step. Fig 3 shows the time evolution of the
equation. The models have been trained for 200 epochs with a batch size of 20.
Table 1 shows that Hyena neural operator consistently performs better than FNO
for different values of $\nu$ at varying resolutions.

Data settings  | Relative $L_{2}$ norm
---|---
Case | Resolution  | FNO | HNO
$\nu=0.5,\rho=1.0$ |  $256$ | 40.16 | 21.68
|  $512$ | 46.29 | 23.89
|  $1024$ | 42.71 | 22.52
$\nu=2.0,\rho=1.0$ |  $256$ | 41.33 | 36.32
|  $512$ | 39.20 | 36.91
|  $1024$ | 41.98 | 22.78

Table 1:  Relative $L_{2}$ norm($\times 10^{-4}$) for 1D Diffusion-Reaction.
Bold indicates best performance.

(a) HNO’s prediction for $\nu=1e-3$

(b) HNO’s prediction for $\nu=1e-4$

(c) HNO’s prediction for $\nu=1e-5$

Figure 4: HNO’s prediction on Navier stokes equation.

###  3.2 Navier-Stokes Equation

The Navier-Stokes equations are one of the most important equations in
physics. They are a fundamental description of the motion of fluids. It is a
complex and nonlinear equation that dictates the dynamics of various fluid
flows, encompassing turbulent phenomena as well. The equation in velocity
format can be written as:

$\frac{\partial\mathbf{u}}{\partial
t}+(\mathbf{u}\cdot\nabla)\mathbf{u}=-\frac{1}{\rho}\nabla
p+\nu\nabla^{2}\mathbf{u}+\mathbf{f},\quad x\in(0,1)^{2},t\in(0,T],$ (9)

where $\mathbf{f}$ is the external force, $\nu$ represents kinematic
viscosity, $p$ is the pressure term and $\mathbf{u}$ is the velocity vector.
The problem studied in this work follows the previous work of Li et al. 19,
where the target is to predict the vorticity: $\omega=\partial u_{y}/\partial
x-\partial u_{x}/\partial y$ given a fixed time horizon $T$ and the initial
value $\omega_{0}$ sampled from a Gaussian random field. The dataset is
generated on a 256 $\times$ 256 grid and sub-sampled to 64 $\times$ 64 for
training and testing.

Generally, when the viscosity coefficient $\nu$ is lower, the dynamics become
more chaotic, posing a greater challenge for learning. The results for the
Navier-Stokes experiments are presented in Table 2. In the case of Navier-
Stokes, the model is trained for 125,000 iterations with a batch size of 4.
For the size of each Navier-Stokes dataset, NS2-full contains 9800/200
(train/test) samples; each of the rest datasets contains 1000/200 samples.
Solving a complex equation like Navier-Stokes, the Hyena neural operator
significantly outperforms the Fourier neural operator when tested on different
viscosities $\nu=10^{-3},10^{-4},10^{-5}$ with varying $T$ on both large
dataset and small dataset . For viscosity such as $\nu=10^{-5}$, where the
flow change is more complicated compared to other viscosities, the Hyena
operator can keep up with temporal changes due to its ability to capture the
global interaction with long convoluions. By applying the curriculum strategy
to train the time-dependent data, the model was able to learn the solution
more efficiently and converge slightly faster.

Data settings  | Relative $L_{2}$ norm
---|---
Case |  $\nu,T$ | FNO-2D | FNO-3D | U-Net  | HNO
NS1 |  $1\times 10^{-3},50$ | 0.0128 | 0.0086 | 0.0245  | 0.0069
NS2-part |  $1\times 10^{-4},30$ | 0.1559 | 0.1918 | 0.2051  | 0.1245
NS2-full |  $1\times 10^{-4},30$ | 0.0834 | 0.0820 | 0.1190  | 0.0681
NS3 |  $1\times 10^{-5},20$ | 0.1556 | 0.1893 | 0.1982  | 0.1415
# of parameters (M)  | 0.41 | 6.56 | 24.95  | 9.23

Table 2:  Relative $L_{2}$ norm for Navier-Stokes equation benchmark with a
fixed resolution of 64x64. Bold indicates best performance.

##  4 Conclusion

In this study, we present the Hyena neural operator, a subquadratic state-
space model for learning the solution of PDEs. The data-controlled linear
operator demonstrated promising performance and achieved competitive outcomes
when compared to alternative approaches. Future work for HNO includes
downsampling the high-resolution data in latent space by using contracting-
expanding architecture such as Unet49. Other directions include using
tokenized equations to learn physically relevant information50 and improve the
HNO further.

This work is supported by the National Science Foundation under Grant No.
1953222.

## References

  * Foucart et al. 2022 Foucart, C.; Charous, A.; Lermusiaux, P. F. Deep Reinforcement Learning for Adaptive Mesh Refinement. _arXiv preprint arXiv:2209.12351_ 2022,
  * Yang et al. 2023 Yang, J.; Dzanic, T.; Petersen, B.; Kudo, J.; Mittal, K.; Tomov, V.; Camier, J.-S.; Zhao, T.; Zha, H.; Kolev, T.; Anderson, R.; Faissol, D. Reinforcement Learning for Adaptive Mesh Refinement. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics. 2023; pp 5997–6014
  * Lorsung and Barati Farimani 2023 Lorsung, C.; Barati Farimani, A. Mesh deep Q network: A deep reinforcement learning framework for improving meshes in computational fluid dynamics. _AIP Advances_ 2023, _13_ , 015026
  * Pant et al. 2021 Pant, P.; Doshi, R.; Bahl, P.; Barati Farimani, A. Deep learning for reduced order modelling and efficient temporal evolution of fluid simulations. _Physics of Fluids_ 2021, _33_ , 107101
  * Hemmasian et al. 2023 Hemmasian, A.; Ogoke, F.; Akbari, P.; Malen, J.; Beuth, J.; Farimani, A. B. Surrogate modeling of melt pool temperature field using deep learning. _Additive Manufacturing Letters_ 2023, _5_ , 100123
  * Farimani et al. 2017 Farimani, A. B.; Gomes, J.; Pande, V. S. Deep Learning the Physics of Transport Phenomena. 2017
  * Gao et al. 2021 Gao, H.; Sun, L.; Wang, J.-X. Super-resolution and denoising of fluid flow using physics-informed convolutional neural networks without high-resolution labels. _Physics of Fluids_ 2021, _33_ , 073603
  * Xie et al. 2018 Xie, Y.; Franz, E.; Chu, M.; Thuerey, N. TempoGAN: A Temporally Coherent, Volumetric GAN for Super-Resolution Fluid Flow. _ACM Trans. Graph._ 2018, _37_
  * Werhahn et al. 2019 Werhahn, M.; Xie, Y.; Chu, M.; Thuerey, N. A Multi-Pass GAN for Fluid Flow Super-Resolution. _Proceedings of the ACM on Computer Graphics and Interactive Techniques_ 2019, _2_ , 1–21
  * Shu et al. 2023 Shu, D.; Li, Z.; Farimani, A. B. A physics-informed diffusion model for high-fidelity flow field reconstruction. _Journal of Computational Physics_ 2023, _478_ , 111972
  * Yang and Sommer 2023 Yang, G.; Sommer, S. A Denoising Diffusion Model for Fluid Field Prediction. 2023
  * Wang et al. 2023 Wang, T.; Plechac, P.; Knap, J. Generative diffusion learning for parametric partial differential equations. 2023
  * 13 Jadhav, Y.; Berthel, J.; Hu, C.; Panat, R.; Beuth, J.; Barati Farimani, A. Stressd: 2d Stress Estimation Using Denoising Diffusion Model. _Available at SSRN 4478596_
  * Lu et al. 2019 Lu, L.; Jin, P.; Karniadakis, G. E. Deeponet: Learning nonlinear operators for identifying differential equations based on the universal approximation theorem of operators. _arXiv preprint arXiv:1910.03193_ 2019,
  * Wang et al. 2021 Wang, S.; Wang, H.; Perdikaris, P. Learning the solution operator of parametric partial differential equations with physics-informed DeepOnets. 2021
  * Jin et al. 2022 Jin, P.; Meng, S.; Lu, L. MIONet: Learning multiple-input operators via tensor product. 2022
  * Kovachki et al. 2023 Kovachki, N.; Li, Z.; Liu, B.; Azizzadenesheli, K.; Bhattacharya, K.; Stuart, A.; Anandkumar, A. Neural Operator: Learning Maps Between Function Spaces. 2023
  * Li et al. 2020 Li, Z.; Kovachki, N.; Azizzadenesheli, K.; Liu, B.; Bhattacharya, K.; Stuart, A.; Anandkumar, A. Neural Operator: Graph Kernel Network for Partial Differential Equations. 2020
  * Li et al. 2020 Li, Z.; Kovachki, N.; Azizzadenesheli, K.; Liu, B.; Bhattacharya, K.; Stuart, A.; Anandkumar, A. Fourier neural operator for parametric partial differential equations. _arXiv preprint arXiv:2010.08895_ 2020,
  * Tran et al. 2023 Tran, A.; Mathews, A.; Xie, L.; Ong, C. S. Factorized Fourier Neural Operators. 2023
  * Guibas et al. 2022 Guibas, J.; Mardani, M.; Li, Z.; Tao, A.; Anandkumar, A.; Catanzaro, B. Efficient Token Mixing for Transformers via Adaptive Fourier Neural Operators. International Conference on Learning Representations. 2022
  * Li et al. 2023 Li, Z.; Zheng, H.; Kovachki, N.; Jin, D.; Chen, H.; Liu, B.; Azizzadenesheli, K.; Anandkumar, A. Physics-Informed Neural Operator for Learning Partial Differential Equations. 2023
  * Tripura and Chakraborty 2022 Tripura, T.; Chakraborty, S. Wavelet neural operator: a neural operator for parametric partial differential equations. _arXiv preprint arXiv:2205.02191_ 2022,
  * Gupta et al. 2021 Gupta, G.; Xiao, X.; Bogdan, P. Multiwavelet-based operator learning for differential equations. _Advances in neural information processing systems_ 2021, _34_ , 24048–24062
  * Cao 2021 Cao, S. Choose a transformer: Fourier or galerkin. _Advances in neural information processing systems_ 2021, _34_ , 24924–24940
  * Li et al. 2022 Li, Z.; Meidani, K.; Farimani, A. B. Transformer for partial differential equations’ operator learning. _arXiv preprint arXiv:2205.13671_ 2022,
  * Su et al. 2022 Su, J.; Lu, Y.; Pan, S.; Murtadha, A.; Wen, B.; Liu, Y. RoFormer: Enhanced Transformer with Rotary Position Embedding. 2022
  * Stachenfeld et al. 2022 Stachenfeld, K.; Fielding, D. B.; Kochkov, D.; Cranmer, M.; Pfaff, T.; Godwin, J.; Cui, C.; Ho, S.; Battaglia, P.; Sanchez-Gonzalez, A. Learned Coarse Models for Efficient Turbulence Simulation. 2022
  * He et al. 2016 He, K.; Zhang, X.; Ren, S.; Sun, J. Deep Residual Learning for Image Recognition. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2016
  * Chen 1984 Chen, C.-T. _Linear system theory and design_ ; Saunders college publishing, 1984
  * Gu et al. 2022 Gu, A.; Goel, K.; Ré, C. Efficiently Modeling Long Sequences with Structured State Spaces. 2022
  * Gu et al. 2022 Gu, A.; Gupta, A.; Goel, K.; Ré, C. On the Parameterization and Initialization of Diagonal State Space Models. 2022
  * Gu et al. 2022 Gu, A.; Johnson, I.; Timalsina, A.; Rudra, A.; Ré, C. How to Train Your HiPPO: State Space Models with Generalized Orthogonal Basis Projections. 2022
  * Mehta et al. 2022 Mehta, H.; Gupta, A.; Cutkosky, A.; Neyshabur, B. Long range language modeling via gated state spaces. _arXiv preprint arXiv:2206.13947_ 2022,
  * Dao et al. 2022 Dao, T.; Fu, D. Y.; Saab, K. K.; Thomas, A. W.; Rudra, A.; Ré, C. Hungry Hungry Hippos: Towards Language Modeling with State Space Models. _arXiv preprint arXiv:2212.14052_ 2022,
  * Poli et al. 2023 Poli, M.; Massaroli, S.; Nguyen, E.; Fu, D. Y.; Dao, T.; Baccus, S.; Bengio, Y.; Ermon, S.; Ré, C. Hyena Hierarchy: Towards Larger Convolutional Language Models. 2023
  * Tay et al. 2020 Tay, Y.; Dehghani, M.; Abnar, S.; Shen, Y.; Bahri, D.; Pham, P.; Rao, J.; Yang, L.; Ruder, S.; Metzler, D. Long range arena: A benchmark for efficient transformers. _arXiv preprint arXiv:2011.04006_ 2020,
  * Mildenhall et al. 2021 Mildenhall, B.; Srinivasan, P. P.; Tancik, M.; Barron, J. T.; Ramamoorthi, R.; Ng, R. Nerf: Representing scenes as neural radiance fields for view synthesis. _Communications of the ACM_ 2021, _65_ , 99–106
  * Sitzmann et al. 2020 Sitzmann, V.; Martel, J. N. P.; Bergman, A. W.; Lindell, D. B.; Wetzstein, G. Implicit Neural Representations with Periodic Activation Functions. 2020
  * Romero et al. 2022 Romero, D. W.; Kuzina, A.; Bekkers, E. J.; Tomczak, J. M.; Hoogendoorn, M. CKConv: Continuous Kernel Convolution For Sequential Data. 2022
  * Tancik et al. 2020 Tancik, M.; Srinivasan, P.; Mildenhall, B.; Fridovich-Keil, S.; Raghavan, N.; Singhal, U.; Ramamoorthi, R.; Barron, J.; Ng, R. Fourier features let networks learn high frequency functions in low dimensional domains. _Advances in Neural Information Processing Systems_ 2020, _33_ , 7537–7547
  * Ba et al. 2016 Ba, J. L.; Kiros, J. R.; Hinton, G. E. Layer Normalization. 2016
  * Rahimi and Recht 2007 Rahimi, A.; Recht, B. Random Features for Large-Scale Kernel Machines. Advances in Neural Information Processing Systems. 2007
  * Kingma and Ba 2014 Kingma, D. P.; Ba, J. Adam: A method for stochastic optimization. _arXiv preprint arXiv:1412.6980_ 2014,
  * Loshchilov and Hutter 2017 Loshchilov, I.; Hutter, F. SGDR: Stochastic Gradient Descent with Warm Restarts. 2017
  * Hendrycks and Gimpel 2020 Hendrycks, D.; Gimpel, K. Gaussian Error Linear Units (GELUs). 2020
  * Takamoto et al. 2022 Takamoto, M.; Praditia, T.; Leiteritz, R.; MacKinlay, D.; Alesiani, F.; Pflüger, D.; Niepert, M. PDEBench: An extensive benchmark for scientific machine learning. _Advances in Neural Information Processing Systems_ 2022, _35_ , 1596–1611
  * Krishnapriyan et al. 2021 Krishnapriyan, A.; Gholami, A.; Zhe, S.; Kirby, R.; Mahoney, M. W. Characterizing possible failure modes in physics-informed neural networks. _Advances in Neural Information Processing Systems_ 2021, _34_ , 26548–26560
  * Ronneberger et al. 2015 Ronneberger, O.; Fischer, P.; Brox, T. U-net: Convolutional networks for biomedical image segmentation. Medical Image Computing and Computer-Assisted Intervention–MICCAI 2015: 18th International Conference, Munich, Germany, October 5-9, 2015, Proceedings, Part III 18. 2015; pp 234–241
  * Lorsung et al. 2023 Lorsung, C.; Li, Z.; Farimani, A. B. Physics Informed Token Transformer. _arXiv preprint arXiv:2305.08757_ 2023,

## Appendix A

##  Appendix A Model implementation details

Below we provide the implementation details of models used in Diffusion-
Reaction and Navier-Stokes problems. All the models are implemented in PyTorch

###  A.1 Hyperparameters

Problem  |  | Input encoder
---
top
Hyena hidden dim | Hyena FFN |  | Input encoder
---
bottom
1D Diffusion-Reaction  | [2, 128] | 128$\times$8 | [128, 256, 128] | [128, 128]
2D Navier-Stokes  | [12, 96] | 96$\times$8 | [96, 192, 96] | [96, 192]
Table 3: Architecture of input encoder. SA denotes self-attention, FFN denotes
feed forward network.

Problem |  | Query encoder
---
top
CA hidden dim |  | Hyena Hidden
---
dim
CA FFN |  | Query encoder
---
bottom
1D Diffusion-Reaction | [1, 128, 128] | 128$\times$8 | 128$\times$3 | [128, 256, 128] | -
2D Navier-Stokes | [2, 192, 192] | 192$\times$4 | 192$\times$3 | [192, 384, 196] | [192, 384]

Table 4: Architecture of query encoder. CA denotes cross-attention.

Problem | Propagator | Decoder | Hyena hidden dim | Total # of params (M)
---|---|---|---|---
1D Diffusion-Reaction | [128, 128, 128]$\times$3 | [128, 64, 1] | 128$\times$8 | 5.61
2D Navier-Stokes | [384, 384, 384] | [384, 192, 96, 1] | 192$\times$8 | 9.22

Table 5:  Architecture of propagator and decoder. The number of parameters is
the total number including input/query encoders. For 1D Diffusion-Reaction’
equation we use 3 unshared MLPs for propagating the dynamics.


# Insertion and Lie Bracket Concerning Finite Sets

Zhou Mai 111address:Colleague of Mathematical Science, Nankai University,
Weijin Road, Tianjin City, Republic China; email address:
<EMAIL_ADDRESS>
###### Abstract

In this article we discuss the operations of partitions (sequence of disjoint
finite subsets) which are quotient, insertion, composition and Lie bracket.
Moreover, we discuss applications of those operations for Feymman diagrams and
Kontesvich’s graphs.

$\bf{Keywords:}$ partition, quotient, insertion, Lie bracket, Feymman
diagrams, admissible graphs.

###### Contents

  1. 1 Introduction
  2. 2 Quotient and insertion of the partitions
  3. 3 Composition and Lie bracket
  4. 4 Applications to graphs

##  1 Introduction

In this article we discuss some operations of partitions, where the partition
means the sequence of disjoint finite subsets. The operations what we focus on
include quotient, insertion, composition and Lie bracket. All of operation is
generalization of ones concerning Feymman diagrams (see A. Connes and D.
Kreimer [1],[2], A. Connes and M. Marcolli [3], D. Kreimer [6]) and
Kontesvich’s graphs (see L. M. Ionescu [4], M. Kontesvich [7]). The
construction in this article is suitable for the cases of Feymman diagrams and
Kontesvich’s graphs, actually, if we consider some structure maps
additionally, the operations concerning Feymman diagrams and Kontesvich’s
graphs can be reduced to our construction. Here the construction of quotient
follows the ideas in (see Zhou Mai [9]), but, some modification occurs such
that it is more suitable for the cases of Feymman diagrams and Kontesvich’s
graphs. Our construction is suitable for ordinary graphs in the sense of
graphic theory as well. Somehow, a ordinary graph can be regarded as a Feymman
diagram without external lines, but, the case of subgraph is different. It
seems that three types of above graphs can be dealt with in an uniform way.

This paper is organized as follows. In section 2 we discuss the quotient and
insertion of partitions in details. Based on the quotient we construct the
coproduct which will result in a hopf algebra, but we do not discuss this
issue more. In section 3 we construct the composition and Lie bracket. Here
two types of composition are considered, both of them will result in well
defined Lie bracket. Finally, in section 4 we discuss the cases of Feymman
diagrams, Kontesvich’s graphs and ordinary graphs starting from our
construction.

##  2 Quotient and insertion of the partitions

### Quotient of partitions:

Firstly, we introduce some notations which will be useful for discussion
below.

  * •

For a finite set $A$, the reversion map
$\mathcal{R}:\mathcal{P}(\mathcal{P}(A))\rightarrow\mathcal{P}(A)$ is defined
to be:

$\mathcal{R}(\\{I_{i}\\})=\bigcup_{i}I_{i},\,\\{I_{i}\\}\in\mathcal{P}(\mathcal{P}(A)).$

Let $\mathcal{P}_{dis}^{2}(A)$ denote a subset of
$\mathcal{P}(\mathcal{P}(A))$,

$\mathcal{P}_{dis}^{2}(A)=\\{\\{I_{i}\\}\in\mathcal{P}(\mathcal{P}(A))|\\{I_{i}\\}\in\mathbf{part}(\mathcal{R}(\\{I_{i}\\}))\\}.$

We call the element $\\{I_{i}\\}\in\mathcal{P}_{dis}^{2}(A)$ the partition in
$A$.

  * •

Let $\\{I_{i}\\},\\{J_{j}\\}\in\mathcal{P}_{dis}^{2}(A)$, we say
$\\{J_{j}\\}\subset\\{I_{i}\\}$, if for $\forall\,J_{j}$, $\exists\,I_{i}$,
such that $J_{j}\subset I_{i}$.

  * •

Let $\\{I_{i}\\}\in\mathcal{P}_{dis}^{2}(A)$,
$B\subset\mathcal{R}(\\{I_{i}\\})$, and $\\{J_{j}\\}=\\{I_{i}\cap
B\\}_{I_{i}\cap B\not=\emptyset}$. We call $\\{J_{j}\\}$ the restriction of
$\\{I_{i}\\}$ on $B$, denoted by $\\{J_{j}\\}=\\{I_{i}\\}_{(B)}$.

It is obvious that $\mathcal{R}(\\{I_{i}\\}_{(B)})=B$. If $D\subset
B\subset\mathcal{R}(\\{I_{i}\\})$, $\\{J_{j}\\}=\\{I_{i}\\}_{(B)}$, we have
$\\{J_{j}\\}_{(D)}=\\{I_{i}\\}_{(D)}$.

Now we define the quotient between two partitions.

######  Definition 2.1.

Let $\\{I_{i}\\}\in\mathcal{P}_{dis}^{2}(A)$,
$B\subset\mathcal{R}(\\{I_{i}\\})$, we define the quotient of $\\{I_{i}\\}$ by
$\\{I_{i}\\}_{(B)}$, denoted by $\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)}$, to be

$\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)}=\\{I_{i}\\}_{I_{i}\cap
B=\emptyset}\cup\\{\mathcal{R}(\\{I_{i}\\}_{I_{i}\cap
B\not=\emptyset})\setminus B\\}.$ (2.1)

We call $\\{\mathcal{R}(\\{I_{i}\\}_{I_{i}\cap B\not=\emptyset})\setminus
B\\}$ the ideal part of the quotient $\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)}$.

It is convenience to denote $\mathcal{R}(\\{I_{i}\\}_{I_{i}\cap
B\not=\emptyset})$ by $\mathcal{R}_{\\{I_{i}\\},B}$, or, $\mathcal{R}_{B}$ for
short sometime. From definition 2.1 we can easily see that

$\mathcal{R}(\\{I_{i}\\})=\mathcal{R}(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})\cup
B,\,\mathcal{R}(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})\cap B=\emptyset.$

Therefore

$\mathcal{R}(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})=\mathcal{R}(\\{I_{i}\\})\setminus
B.$

Particularly, when $\mathcal{R}_{B}=B$, which means that if $I_{i}\cap
B\not=\emptyset$ we have $I_{i}\subset B$, or, $\\{I_{i}\\}_{(B)}$ is a subset
of $\\{I_{i}\\}$, then
$\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)}=(\\{I_{i}\\}\setminus\\{I_{i}\\}_{(B)})\cup\\{\emptyset\\}$.
We will identify $(\\{I_{i}\\}\setminus\\{I_{i}\\}_{(B)})\cup\\{\emptyset\\}$
with $\\{I_{i}\\}\setminus\\{I_{i}\\}_{(B)}$. In this special situation the
ideal part of quotient $\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)}$ is
$\\{\emptyset\\}$, we call this special situation the travail quotient. Noting
that $\\{I_{i}\\}=\\{I_{i}\\}_{I_{i}\cap
B=\emptyset}\cup\\{I_{i}\\}_{I_{i}\cap B\not=\emptyset}$, and
$\\{I_{i}\\}_{I_{i}\cap
B\not=\emptyset}\diagup\\{I_{i}\\}_{(B)}=\\{\emptyset\\}\cup\\{\mathcal{R}_{B}\setminus
B\\}$, thus we can rewrite the formula (2.1) in the following form:

$\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)}=\\{I_{i}\\}_{I_{i}\cap
B=\emptyset}\cup(\\{I_{i}\\}_{I_{i}\cap
B\not=\emptyset}\diagup\\{I_{i}\\}_{(B)}).$

For the quotient of the partitions we have the following properties.

######  Proposition 2.1.

Let $\\{I_{i}\\}\in\mathcal{P}_{dis}^{2}(A)$,
$B,C\subset\mathcal{R}(\\{I_{i}\\})$, $B\cap C=\emptyset$, then following
formulas are valid.

  * •

$(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})_{(C)}=\\{I_{i}\\}_{(B\cup
C)}\diagup\\{I_{i}\\}_{(B)}.$ (2.2)

$\begin{array}[]{c}(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})\diagup(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})_{(C)}\\\
=(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})\diagup(\\{I_{i}\\}_{(B\cup
C)}\diagup\\{I_{i}\\}_{(B)}).\end{array}$ (2.3)

  * •

When $\mathcal{R}_{B}\cap\mathcal{R}_{B}=\emptyset$, we have

$\begin{array}[]{c}(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})_{(C)}=\\{I_{i}\\}_{(C)},\\\
(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(C)})_{(B)}=\\{I_{i}\\}_{(B)},\end{array}$

$(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})\diagup\\{I_{i}\\}_{(C)}=(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(C)})\diagup\\{I_{i}\\}_{(B)},$
(2.4)

$(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})\diagup(\\{I_{i}\\}_{(B\cup
C)}\diagup\\{I_{i}\\}_{(B)})=(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})\diagup\\{I_{i}\\}_{(C)}.$
(2.5)

  * •

When $\mathcal{R}_{B}\cap\mathcal{R}_{B}\not=\emptyset$, we have

$(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})\diagup(\\{I_{i}\\}_{(B\cup
C)}\diagup\\{I_{i}\\}_{(B)})=\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B\cup C)}.$ (2.6)

###### Proof.

$\bf{Proof\,of\,the\,formulas\,(2.2)\,and\,(2.3):}$ At first, in order to
prove the formula (2.2), we calculate the left side of the formula. From
definition 2.1 we have

$\begin{array}[]{c}(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})_{(C)}\\\
=(\\{I_{i}\\}_{I_{i}\cap B=\emptyset}\cup\\{\mathcal{R}_{B}\setminus
B\\})_{(C)}\\\ =\\{I_{i}\cap C\\}_{I_{i}\cap
B=\emptyset}\cup\\{\mathcal{R}_{B}\cap C\\}.\end{array}$

On the other hand, for the right side of the formula (2.2) we have

$\begin{array}[]{c}\\{I_{i}\\}_{(B\cup C)}\diagup\\{I_{i}\\}_{(B)}\\\
=\\{I_{i}\cap(B\cup C)\\}_{I_{i}\cap
B=\emptyset}\cup\\{[\mathcal{R}_{B}\cap(B\cup C)]\setminus B\\}\\\
=\\{I_{i}\cap C\\}_{I_{i}\cap B=\emptyset}\cup\\{\mathcal{R}_{B}\cap
C\\}.\end{array}$

Therefore, the formula (2.2) is valid. The formula (2.3) is the corollary of
the formula (2.2). $\bf{Proof\,of\,the\,other\,formulas:}$ As the first step,
from definition 2.1 we get

$\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)}=\\{I_{i}\\}_{I_{i}\cap
B=\emptyset}\cup\\{\mathcal{R}_{B}\setminus B\\}.$

We need to consider two possibilities.

$\bf{Case\,of\,\mathcal{R}_{B}\cap\mathcal{R}_{C}=\emptyset:}$ Noting
$I_{i}\cap I_{i^{\prime}}=\emptyset,\,i\not=i^{\prime}$, we know that

$I_{i}\cap B\not=\emptyset\Longleftrightarrow I_{i}\cap
C=\emptyset\,(or\,I_{i}\cap C\not=\emptyset\Longleftrightarrow I_{i}\cap
B=\emptyset),\,if\,I_{i}\cap(B\cup C)\not=\emptyset.$

Thus we have

$\begin{array}[]{c}\mathcal{R}(\\{I_{i}\\}_{I_{i}\cap
C\not=\emptyset})=\mathcal{R}(\\{I_{i}\\}_{I_{i}\cap
C\not=\emptyset,\,I_{i}\cap B=\emptyset}),\end{array}$

and

$\begin{array}[]{c}(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})_{(C)}=\\{I_{i}\cap
C\\}_{I_{i}\cap B=\emptyset,\,I_{i}\cap C\not=\emptyset}=\\{I_{i}\cap
C\\}_{I_{i}\cap C\not=\emptyset}=\\{I_{i}\\}_{(C)},\end{array}$

similarly,

$(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(C)})_{(B)}=\\{I_{i}\\}_{(B)}.$

On the other hand, through a straightforward calculation, we have

$\begin{array}[]{c}(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})\diagup(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})_{(C)}\\\
=\\{I_{i}\\}_{I_{i}\cap(B\cup C)=\emptyset}\cup\\{\mathcal{R}_{B}\setminus
B\\}\cup\\{\mathcal{R}(\\{I_{i}\\}_{I_{i}\cap B=\emptyset,\,I_{i}\cap
C\not=\emptyset})\setminus C\\}\\\ =\\{I_{i}\\}_{I_{i}\cap(B\cup
C)=\emptyset}\cup\\{\mathcal{R}_{B}\setminus
B\\}\cup\\{\mathcal{R}_{C}\setminus C\\}.\end{array}$

From above discussion we can get the formulas (2.4) and (2.5).

$\bf{Case\,of\,\mathcal{R}_{B}\cap\mathcal{R}_{C}\not=\emptyset}:$ From
definition of quotient, by a straightforward calculation, we get

$\begin{array}[]{c}(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})\diagup(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})_{(C)}\\\
=\\{I_{i}\\}_{I_{i}\cap(B\cup
C)=\emptyset}\cup\\{(\mathcal{R}(\\{I_{i}\\}_{I_{i}\cap
B=\emptyset,\,I_{i}\cap C\not=\emptyset})\cup(\mathcal{R}_{B}\setminus
B))\setminus C\\}.\end{array}$

It is easy to check that

$\begin{array}[]{c}(\mathcal{R}_{B}\setminus B)\cap
C\not=\emptyset\Longleftrightarrow(\mathcal{R}_{C}\setminus C)\cap
B\not=\emptyset,\\\ (\mathcal{R}(\\{I_{i}\\}_{I_{i}\cap
B=\emptyset,\,I_{i}\cap
C\not=\emptyset})\cup\mathcal{R}_{B}=\mathcal{R}_{B\cup C}.\end{array}$

In summary we get

$(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})\diagup(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})_{(C)}=\\{I_{i}\\}_{I_{i}\cap(B\cup
C)=\emptyset}\cup\\{\mathcal{R}_{B\cup C}\setminus(B\cup C)\\}.$

Therefore the formula (2.6) is valid.

∎

######  Corollary 2.1.

$(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})\diagup(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})_{(C)}=(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(C)})\diagup(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(C)})_{(B)}.$

### Insertion of partitions:

Now we turn to the discussion of insertion. Let
$\\{I_{i}\\},\\{J_{j}\\}\in\mathcal{P}_{dis}^{2}(A)$,
$\mathcal{R}(\\{I_{i}\\})\cap\mathcal{R}(\\{J_{j}\\})=\emptyset$. We hope to
define the insertion of $\\{J_{j}\\}$ into $\\{I_{i}\\}$ at $I_{a}$.

######  Definition 2.2.

Let $\\{I_{i}\\}_{1\leq i\leq m},\\{J_{j}\\}_{1\leq j\leq
n}\in\mathcal{P}_{dis}^{2}(A)$,
$\mathcal{R}(\\{I_{i}\\})\cap\mathcal{R}(\\{J_{j}\\})=\emptyset$, and
$\iota:I_{a}\rightarrow\\{J_{j}\\}_{1\leq j\leq n}$ be a map ($1\leq a\leq
m$). The insertion of $\\{J_{j}\\}_{j=1}^{n}$ into $\\{I_{i}\\}_{i=1}^{m}$ at
$I_{a}$ by $\iota$ is a partition
$\\{I_{i}\\}\circ_{a}^{\iota}\\{J_{j}\\}\in\mathcal{P}_{dis}^{2}(A)$, where

$\begin{array}[]{c}\\{I_{i}\\}\circ_{a}^{\iota}\\{J_{j}\\}\\\
=\\{I_{1},\cdots,I_{a-1},J_{1}\cup\iota^{-1}(J_{1}),\cdots,J_{n}\cup\iota^{-1}(J_{n}),I_{a+1},\cdots,I_{m}\\}.\end{array}$
(2.7)

######  Remark 2.1.

  * •

For simplicity, we denote $\\{I_{i}\\}\circ_{a}^{\iota}\\{J_{j}\\}$ in the
following intuitive way:

$\begin{array}[]{c}\\{\cdots,\hat{I_{a}},\cdots\\}\\\ \uparrow\\\
\\{J_{1}\cup\iota^{-1}(J_{1}),\cdots,J_{n}\cup\iota^{-1}(J_{n})\\}.\end{array}$

  * •

Particularly, we can always identify $\\{I_{i}\\}$ with
$\\{I_{i}\\}\cup\\{\emptyset\\}$, then the insertion of $\\{J_{j}\\}$ into
$\\{I_{i}\\}$ at $\emptyset$ is defined in the following way. We replace
$\\{I_{i}\\}$ by $\\{I_{i}\\}\cup\\{J\\}$ firstly, where
$J=\mathcal{R}(\\{J_{j}\\})$. Then we consider
$(\\{I_{i}\\}\cup\\{J\\})\circ_{J}^{\iota}\\{J_{j}\\}$, where
$\iota:J\to\\{J_{j}\\}$ satisfies $\iota^{-1}(J_{j})=J_{j}$. It is easy to
check
$(\\{I_{i}\\}\cup\\{J\\})\circ_{J}^{\iota}\\{J_{j}\\}=\\{I_{i}\\}\cup\\{J_{j}\\}$.
We call insertion $(\\{I_{i}\\}\cup\\{J\\})\circ_{J}^{\iota}\\{J_{j}\\}$ the
travail insertion, denoted by $\\{I_{i}\\}\circ_{J}\\{J_{j}\\}$ simply,
because $\iota$ is chosen in a special way. We call the insertion in this way
the travail insertion.

######  Proposition 2.2.

Let $\\{I_{i}\\},\\{J_{j}\\}\in\mathcal{P}_{dis}^{2}(A)$,
$\mathcal{R}(\\{I_{i}\\})\cap\mathcal{R}(\\{J_{j}\\})=\emptyset$, then there
is $\\{K_{k}\\}\in\mathcal{P}_{dis}^{2}(A)$ such that

$\\{K_{k}\\}\diagup\\{J_{j}\\}=\\{I_{i}\\},$

if and only if, $\\{J_{j}\\}=\\{K_{k}\\}_{(J)}$
($J=\mathcal{R}(\\{J_{j}\\})$), $\mathcal{R}(\\{K_{k}\\}_{K_{k}\cap
J\not=\emptyset})\setminus J\not=\emptyset$, and, there is a map
$\iota:I_{a}\to\\{J_{j}\\}$ for some $a$ ($1\leq a\leq\\#\\{I_{i}\\}$) such
that

$\\{K_{k}\\}=\\{I_{i}\\}\circ_{a}^{\iota}\\{J_{j}\\}.$

###### Proof.

Let $\\{K_{k}\\}=\\{I_{i}\\}\circ_{a}^{\iota}\\{J_{j}\\}$. It is obvious that
$(\\{I_{i}\\}\circ_{a}^{\iota}\\{J_{j}\\})_{(\mathcal{R}(\\{J_{j}\\}))}=\\{J_{j}\\}$,
and, by a straightforward calculation we get

$(\\{I_{i}\\}\circ_{a}^{\iota}\\{J_{j}\\})\diagup\\{J_{j}\\}=\\{I_{i}\\}.$

Conversely, we assume $\\{K_{k}\\}$ satisfies
$\\{K_{k}\\}\diagup\\{J_{j}\\}=\\{I_{i}\\}$. Let $I=\mathcal{R}(\\{I_{i}\\})$,
$J=\mathcal{R}(\\{J_{j}\\})$, $K=\mathcal{R}(\\{K_{k}\\})$,
$\mathcal{R}_{J}=\mathcal{R}(\\{K_{k}\\}_{K_{k}\cap J\not=\emptyset})$. Then
we have $K=I\cup J$, $\\{J_{j}\\}=\\{K_{k}\\}_{(J)}=\\{K_{k}\cap
J\\}_{K_{k}\cap J\not=\emptyset}$, and

$\\{K_{k}\\}_{K\cap J=\emptyset}\cup\\{\mathcal{R}_{J}\setminus
J\\}=\\{I_{i}\\}.$

Thus $I_{a}=\mathcal{R}_{J}\setminus J$, $\\{K_{k}\\}_{K\cap
J=\emptyset}=\\{I_{i}\\}_{i\not=a}$ for some $a$ ($1\leq
a\leq\\#\\{I_{i}\\}$). Let $\\{K_{k}\\}_{K_{k}\cap
J\not=\emptyset}=\\{K_{k_{j}}\\}$, and $K_{k_{j}}=J_{j}\cup L_{j}$, where
$J_{j}\cap L_{j}=\emptyset$, $L_{j}\cap L_{j^{\prime}}=\emptyset$
($j\not=j^{\prime}$), we get a decomposition of $I_{a}$,
$I_{a}=\bigcup_{j}L_{j}$. Above decomposition define a map
$\iota:I_{a}\to\\{J_{j}\\}$, such that $\iota^{-1}(J_{j})=L_{j}$. Up to now,
we have proved

$\\{K_{k}\\}=\\{I_{i}\\}\circ_{a}^{\iota}\\{J_{j}\\}.$

∎

######  Corollary 2.2.

Let $\\{I_{i}\\}\in\mathcal{P}_{dis}^{2}(A)$,
$B\subset\mathcal{R}(\\{I_{i}\\})$, we have

$\\{I_{i}\\}=(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})\circ_{B}\\{I_{i}\\}_{(B)}.$

###### Proof.

Let $\\{I_{i}\\}\in\mathcal{P}_{dis}^{2}(A)$,
$B\subset\mathcal{R}(\\{I_{i}\\})$, we can take quotient

$\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)}=\\{I_{i}\\}_{I_{i}\cap
B=\emptyset}\cup\\{\mathcal{R}_{B}\setminus B\\}.$

Now we define a map $\iota:\mathcal{R}_{B}\setminus
B\rightarrow\\{I_{i}\\}_{(B)}$ as follows:

$\iota(x)=I_{i}\cap B,\,x\in I_{i}\cap(\mathcal{R}_{B}\setminus B).$

Then the insertion of $\\{I_{i}\\}_{(B)}$ into
$\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)}$ at $\mathcal{R}_{B}\setminus B$ by
$\iota$ just be $\\{I_{i}\\}$. Because the map $\iota$ is taken in a special
way, we denote above insertion by
$(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})\circ_{B}\\{I_{i}\\}_{(B)}$. ∎

Due to proposition 2.2 we can give an another statement of proposition 2.1 by
means of insertion.

######  Proposition 2.3.

Let $\\{I_{i}\\}\in\mathcal{P}_{dis}^{2}(A)$,
$B,C\subset\mathcal{R}(\\{I_{i}\\})$, $B\cap C=\emptyset$, then the following
conclusions are valid:

  * •

When $\mathcal{R}(\\{I_{i}\\}_{I_{i}\cap B\not=\emptyset})\cap C=\emptyset$
($\mathcal{R}(\\{I_{i}\\}_{I_{i}\cap C\not=\emptyset})\cap B=\emptyset$), we
have

$\begin{array}[]{c}(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})_{(C)}\circ_{\emptyset}\\{I_{i}\\}_{(B)}=\\{I_{i}\\}_{(B\cup
C)},\\\ (\\{I_{i}\\}\diagup\\{I_{i}\\}_{(C)})\diagup\\{I_{i}\\}_{(B)}\\\
=(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})\diagup(((\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})_{(C)}\circ_{\emptyset}\\{I_{i}\\}_{(B)})\diagup\\{I_{i}\\}_{(B)}).\end{array}$

  * •

When $\mathcal{R}(\\{I_{i}\\}_{I_{i}\cap B\not=\emptyset})\cap
C\not=\emptyset$ ($\mathcal{R}(\\{I_{i}\\}_{I_{i}\cap C\not=\emptyset})\cap
B\not=\emptyset$), we have

$\begin{array}[]{c}(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})_{(C)}\circ_{B}\\{I_{i}\\}_{(B)}=\\{I_{i}\\}_{(B\cup
C)},\\\ \\{I_{i}\\}\diagup\\{I_{i}\\}_{(B\cup C)}\\\
=(\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})\diagup[((\\{I_{i}\\}\diagup\\{I_{i}\\}_{(B)})_{(C)}\circ_{B}\\{I_{i}\\}_{(B)})\diagup\\{I_{i}\\}_{(B)}].\end{array}$

### Coproduct:

Now we consider the coproduct as an application of quotient. To give well
defined definition of coproduct, we need to make some preparations.

######  Definition 2.3.

Let $\\{I_{i}\\},\\{J_{j}\\}\in\mathcal{P}_{dis}^{2}(A)$, if
$\mathcal{R}(\\{J_{j}\\})\subset\mathcal{R}(\\{I_{i}\\})$, and

$\mathcal{R}_{J_{j}}\cap\mathcal{R}_{J_{j^{\prime}}}=\emptyset,\,j\not=j^{\prime},$
(2.8)

we call $\\{J_{j}\\}$ admits to $\\{I_{i}\\}$, denoted by
$\\{I_{i}\\}\sqsubset\\{J_{j}\\}$.

######  Remark 2.2.

The condition (2.8) is equivalent to the following conditions

$\mathcal{R}_{J_{j}}\cap
J_{j^{\prime}}=\emptyset\,(or,\,\mathcal{R}_{J_{j^{\prime}}}\cap
J_{j}=\emptyset),\,j\not=j^{\prime}.$

For convenience we introduce notations as follows. Let
$\\{I_{i}\\},\\{J_{j}\\}\in\mathcal{P}_{dis}^{2}(A)$,
$\mathcal{R}(\\{J_{j}\\})\subset\mathcal{R}(\\{I_{i}\\})$, we define

$\begin{array}[]{c}\\{I_{i}\\}\diagup(J_{1})\doteq\\{I_{i}\\}\diagup\\{I_{i}\\}_{(J_{1})},\\{I_{i}\\}\diagup(J_{1},J_{2})\doteq(\\{I_{i}\\}\diagup(J_{1}))\diagup(\\{I_{i}\\}\diagup(J_{1}))_{(J_{2})},\\\
\cdots,\\{I_{i}\\}\diagup(J_{1},\cdots,J_{k+1})\doteq(\\{I_{i}\\}\diagup(J_{1},\cdots,J_{k}))\diagup(\\{I_{i}\\}\diagup(J_{1},\cdots,J_{k}))_{(J_{k+1})}.\end{array}$

By proposition 2.1 we know that if $\\{I_{i}\\}\sqsubset\\{J_{j}\\}$ we have

$\\{I_{i}\\}\diagup(J_{j})=(\cdots((\\{I_{i}\\}\diagup\\{I_{i}\\}_{(J_{1})})\diagup\\{I_{i}\\}_{(J_{2})})\cdots)\diagup\\{I_{i}\\}_{(J_{p})},$

where $\\{J_{j}\\}=\\{J_{1},\cdots,J_{p}\\}$. Conversely, according to
proposition 2.2, there are positive integers $i_{1},\cdots,i_{p}$, ($1\leq
i_{1},\cdots,i_{p}\leq\\#\\{I_{I_{i}}\\}$), and maps
$\iota_{j}:I_{i_{j}}\to\\{I_{i}\\}_{J_{j}}$ as ones in corollary 2.2
($j=1,\cdots,p$), such that

$\\{I_{i}\\}=(\cdots((\\{I_{i}\\}\diagup(J_{j}))\circ_{J_{1}}\\{I_{i}\\}_{(J_{1})})\circ_{J_{2}}\\{I_{i}\\}_{(J_{2})}\cdots)\circ_{J_{p}}\\{I_{i}\\}_{(J_{p})}.$

Generally, $\\{J_{j}\\}$ may not admit to $\\{I_{i}\\}$, even though
$\mathcal{R}(\\{J_{j}\\})\subset\mathcal{R}(\\{I_{i}\\})$. But $\\{J_{j}\\}$
can always induce a new partition $\\{L_{l}\\}$ such that
$\mathcal{R}(\\{L_{l}\\})=\mathcal{R}(\\{J_{j}\\})$,
$\\{L_{l}\\}\sqsubset\\{I_{i}\\}$, and

$\\{I_{i}\\}\diagup(J_{j})=\\{I_{i}\\}\diagup(L_{l}).$

Now we describe the procedure from $\\{J_{j}\\}$ to $\\{L_{l}\\}$. In
$\\{J_{j}\\}$ we define an equivalent relation as follows.

$J_{j}\sim J_{j^{\prime}}\Longleftrightarrow\mathcal{R}(\\{I_{i}\\}_{I_{i}\cap
J_{j}}\not=\emptyset\\})\cap\mathcal{R}(\\{I_{i}\\}_{I_{i}\cap
J_{j^{\prime}}\not=\emptyset}\\})\not=\emptyset.$

Under the equivalent relation defined above $\\{J_{j}\\}$ can be divided into
some sets of equivalent class, denoted by
$\\{J_{j}\\}=\bigcup_{l}<J_{j}>_{l}$. We take $L_{l}$ to be
$L_{l}=\bigcup_{J_{j^{\prime}}\in<J_{j}>_{l}}J_{j^{\prime}}$. It is easy to
check that $\mathcal{R}(\\{L_{l}\\})=\mathcal{R}(\\{J_{j}\\})$,
$\\{L_{l}\\}\sqsubset\\{I_{i}\\}$. With the help of proposition 2.1 we can
prove $\\{I_{i}\\}\diagup(J_{j})=\\{I_{i}\\}\diagup(L_{l})$. Actually, we have

$\\{I_{i}\\}\diagup(J_{j^{\prime}})_{J_{j^{\prime}}\in<J_{j}>_{l}}=\\{I_{i}\\}\diagup\\{I_{i}\\}_{(L_{l})}.$

If we ignore the order in $\\{L_{l}\\}$, it is obvious that $\\{L_{l}\\}$ is
unique. We denote $\\{L_{l}\\}$ by $\\{L_{l}\\}=\\{J_{j}\\}_{ad}$.

We now introduce

$\mathcal{P}_{dis,\,k}^{2}(A)\subset\underbrace{\mathcal{P}_{dis}^{2}(A)\times\cdots\times\mathcal{P}_{dis}^{2}(A)}_{k-times},$

$\begin{array}[]{c}(\\{I_{i_{1}}^{(1)}\\}\cdots,\\{I_{I_{k}}^{(k)}\\})\in\mathcal{P}_{dis,\,k}^{2}(A)\Longleftrightarrow\\\
\mathcal{R}(\\{I_{i_{\lambda}}^{(\lambda)}\\})\cap\mathcal{R}(\\{I_{i_{\mu}}^{(\mu)}\\})=\emptyset,\,1\leq\lambda<\mu\leq
k,\,\bigcup\limits_{\lambda}\\{I_{i_{\lambda}}^{(\lambda)}\\}\in\mathcal{P}_{dis}^{2}(A).\end{array}$

Similar to definition 2.3 we have

######  Definition 2.4.

Let $\\{J_{j}\\}\in\mathcal{P}_{dis}^{2}(A)$,
$(\\{I_{i_{1}}^{(1)}\\},\cdots,\\{I_{I_{k}}^{(k)}\\})\in\mathcal{P}_{dis,\,k}^{2}(A)$,
we say
$\\{J_{j}\\}\sqsubset(\\{I_{i_{1}}^{(1)}\\},\cdots,\\{I_{I_{k}}^{(k)}\\})$, if
$\\{J_{j}\\}\subset\\{\mathcal{R}(\\{I_{i_{\lambda}}^{(\lambda)}\\})\\}_{\lambda=1}^{k}$,
and
$\\{J_{j}\\}_{J_{j}\cap\mathcal{R}(\\{I_{i_{\mu}}^{(\mu)}\\})\not=\emptyset}\sqsubset\\{I_{i_{\mu}}^{(\mu)}\\}$,
($\mu=1,\cdots,k$).

Furthermore, let $\\{J_{j}\\}\in\mathcal{P}_{dis}^{2}(A)$,
$(\\{I_{i_{1}}^{(1)}\\}\cdots,\\{I_{I_{k}}^{(k)}\\})\in\mathcal{P}_{dis,\,k}^{2}(A)$,
where
$\\{J_{j}\\}\sqsubset(\\{I_{i_{1}}^{(1)}\\}\cdots,\\{I_{I_{k}}^{(k)}\\})$, we
define

$\begin{array}[]{c}(\\{I_{i_{1}}^{(1)}\\},\cdots,\\{I_{I_{k}}^{(k)}\\})\diagup(J_{j})=(\\{I_{i_{1}}^{(1)}\\}\diagup(J_{j}),\cdots,\\{I_{I_{k}}^{(k)}\diagup(J_{j})\\}),\end{array}$

where

$\\{I_{i_{\lambda}}^{(\lambda)}\\}\diagup(J_{j})=\\{I_{i_{\lambda}}^{(\lambda)}\\}\diagup(J_{j})_{J_{j}\subset\mathcal{R}(I_{i_{\lambda}}^{(\lambda)}\\})},\,\lambda=1,\cdots,k.$

Similarly, we can discuss the insertion for the case of
$(\\{I_{i_{1}}^{(1)}\\},\cdots,\\{I_{i_{k}}^{(k)}\\})$ in a obvious way.

Let $\mathbb{K}$ be a field with characteristic zero,
$V_{\mathbb{K},A}=\bigoplus_{1\leq
k\leq\\#\\{A\\}}\mathbb{K}(\mathcal{P}_{dis,\,k}^{2}(A))$, where
$\mathbb{K}(\mathcal{P}_{dis,\,k}^{2}(A))$ denotes the vector space over
$\mathbb{K}$ spanned by $\mathcal{P}_{dis,\,k}^{2}(A)$. Based on the above
discussions we now define coproduct on $V_{\mathbb{K},A}$,
$\bigtriangleup:V_{\mathbb{K},A}\to V_{\mathbb{K},A}\otimes V_{\mathbb{K},A}$.

######  Definition 2.5.

Let $\\{I_{i}\\}\in\mathcal{P}_{dis}^{2}(A)$,
$(\\{I_{i_{1}}^{(1)}\\},\cdots,\\{I_{i_{k}}^{(k)}\\})\in\mathcal{P}_{dis,\,k}^{2}(A)$,
we define

  * •

$\begin{array}[]{c}\bigtriangleup\\{I_{i}\\}=\emptyset\otimes\\{I_{i}\\}+\\{I_{i}\\}\otimes\emptyset+\\\
\sum\limits_{\\{J_{1},\cdots,J_{l}\\}\sqsubset\\{I_{i}\\}}(\\{I_{i}\\}_{(J_{1})}\cdots,\\{I_{i}\\}_{(J_{l})})\otimes\\{I_{i}\\}\diagup(J_{j}).\end{array}$
(2.9)

  * •

$\begin{array}[]{c}\bigtriangleup(\\{I_{i_{1}}^{(1)}\\},\cdots,\\{I_{i_{k}}^{(k)}\\})\\\
=\emptyset\otimes(\\{I_{i_{1}}^{(1)}\\},\cdots,\\{I_{i_{k}}^{(k)}\\})+(\\{I_{i_{1}}^{(1)}\\},\cdots,\\{I_{i_{k}}^{(k)}\\})\otimes\emptyset+\\\
\sum\limits_{\\{J_{j}\\}\sqsubset(\\{I_{i_{1}}^{(1)}\\},\cdots,\\{I_{i_{k}}^{(k)}\\})}(\\{I_{i}\\}_{(J_{1})}\cdots,\\{I_{i}\\}_{(J_{l})})\otimes(\\{I_{i_{1}}^{(1)}\\},\cdots,\\{I_{i_{k}}^{(k)}\\})\diagup(J_{j}),\end{array}$
(2.10)

where $\\{I_{i}\\}=\bigcup_{\lambda}\\{I_{i_{\lambda}}^{(\lambda)}\\}$.

For associativity of coproduct defined in definition 2.5 we need the following
conclusion.

######  Proposition 2.4.

Let $\\{I_{i}\\},\\{J_{j}\\},\\{K_{k}\\}\in\mathcal{P}_{dis}^{2}(A)$,
$\\{J_{j}\\}\sqsubset\\{I_{i}\\}$,
$\\{K_{k}\\}\sqsubset\\{I_{i}\\}\diagup(J_{j})$. Then there is a partition
$\\{M_{\mu}\\}\in\mathcal{P}_{dis}^{2}(A)$ satisfying the following
conditions:

  * •

$\\{M_{\mu}\\}\sqsubset\\{I_{i}\\}$,
$\\{J_{j}\\}\sqsubset(\cdots,\\{I_{i}\\}_{(M_{\mu})},\cdots)$.

  * •

$(\cdots,(\\{I_{i}\\}\diagup(J_{j}))_{(K_{k})},\cdots)=(\cdots,\\{I_{i}\\}_{(M_{\mu})},\cdots)\diagup(J_{j})$.

  * •

$(\\{I_{i}\\}\diagup(J_{j}))\diagup(K_{k})=\\{I_{i}\\}\diagup(M_{\mu})$.

###### Proof.

For simplicity, let $J=\mathcal{R}(\\{J_{j}\\}_{j=1}^{p})$,
$K=\mathcal{R}(\\{K_{k}\\}_{k=1}^{q})$. A crucial stage of proof is to
construct $\\{M_{\mu}\\}$. At first we observe
$(\\{I_{i}\\}\diagup(J_{j}))\diagup(K_{k})$. From definition of quotient we
have

$\\{I_{i}\\}\diagup(J_{j})=\\{I_{i}\\}_{I_{i}\cap
J=\emptyset}\cup\\{\mathcal{R}_{J_{1}}\setminus
J_{1}\\}\cup\cdots\cup\\{\mathcal{R}_{J_{p}}\setminus J_{p}\\}.$

According to $\\{K_{k}\\}$ we have a decomposition of
$\\{I_{i}\\}\diagup(J_{j})$ as follows.

$\begin{array}[]{c}\\{I_{i}\\}\diagup(J_{j})=\\{I_{i}\\}_{I_{i}\cap(J\cup
K)=\emptyset}\cup\\\ (\\{I_{i}\cap K\\}_{I_{i}\cap J=\emptyset,\,I_{i}\cap
K_{1}\not=\emptyset}\cup\bigcup\limits_{\mathcal{R}_{J_{j}}\cap
K_{1}\not=\emptyset}\\{\mathcal{R}_{J_{j}}\setminus J_{j}\\})\cup\cdots\\\
\cdots\cup(\\{I_{i}\cap K\\}_{I_{i}\cap J=\emptyset,\,I_{i}\cap
K_{q}\not=\emptyset}\cup\bigcup\limits_{\mathcal{R}_{J_{j}}\cap
K_{q}\not=\emptyset}\\{\mathcal{R}_{J_{j}}\setminus J_{j}\\}).\end{array}$

In above expression, each part jointing $K$ consists of two parts, which are

$\\{I_{i}\cap K\\}_{I_{i}\cap J=\emptyset,\,I_{i}\cap
K_{k}\not=\emptyset},\,and\,\bigcup\limits_{\mathcal{R}_{J_{j}}\cap
K_{k}\not=\emptyset}\\{\mathcal{R}_{J_{j}}\setminus J_{j}\\}.$

Here we allow one of two parts to be empty set. The decomposition discussed
above suggests us to take $\\{M_{\mu}\\}$ to be

$\begin{array}[]{c}M_{k}=\mathcal{R}(\\{I_{i}\cap K\\}_{I_{i}\cap
J=\emptyset,\,I_{i}\cap
K_{k}\not=\emptyset})\cup(\bigcup\limits_{\mathcal{R}_{J_{j}}\cap
K_{k}\not=\emptyset}\mathcal{R}_{J_{j}}\cap(J\cup K)),\end{array}$

where $k=1,\cdots,q$. It is obvious that we have
$\\{M_{\mu}\\}\sqsubset\\{I_{i}\\}$,
$\\{J_{j}\\}\sqsubset(\cdots,\\{I_{i}\\}_{(M_{\mu})},\cdots)$. By a
straightforward calculation we can proved

$(\\{I_{i}\\}\diagup(J_{j}))\diagup(K_{k})=\\{I_{i}\\}\diagup(M_{\mu}),$

and

$(\cdots,(\\{I_{i}\\}\diagup(J_{j}))_{(K_{k})},\cdots)=(\cdots,\\{I_{i}\\}_{(M_{\mu})},\cdots)\diagup(J_{j}).$

∎

As the corollary of proposition 2.4 we have:

######  Proposition 2.5.

The coproduct in definition 2.5 satisfies

$(\bigtriangleup\otimes
id)\bigtriangleup=(id\otimes\bigtriangleup)\bigtriangleup.$ (2.11)

######  Remark 2.3.

It is easy to check that $(\bigtriangleup^{\prime})^{m}=0$ for some positive
integer $m$, where

$\bigtriangleup^{\prime}(\cdot)=\bigtriangleup(\cdot)-(\cdot)\otimes\emptyset-\emptyset\otimes(\cdot).$

Thus, from $V_{\mathbb{K},A}$ we can construct a Hopf algebra in a standard
way (see D. E. Radford [8]).

##  3 Composition and Lie bracket

We now go to the discussion of the composition between $\\{I_{i}\\}$ and
$\\{J_{j}\\}$, where $\\{I_{i}\\},\\{J_{j}\\}\in\mathcal{P}_{dis}^{2}(A)$,
$\mathcal{R}(\\{I_{i}\\})\cap\mathcal{R}(\\{J_{j}\\})=\emptyset$. Similar to
the cases of Feymman diagrams and Kontsevich’s graphs, we have:

######  Definition 3.1.

We define

$\\{I_{i}\\}\circ_{a}\\{J_{j}\\}=\sum\limits_{\iota}\\{I_{i}\\}\circ_{a}^{\iota}\\{J_{j}\\},$
(3.1)

and

$\\{I_{i}\\}\circ\\{J_{j}\\}=\sum\limits_{a}\\{I_{i}\\}\circ_{a}\\{J_{j}\\}.$
(3.2)

From definition 3.1 we can see that we do not consider the travail insertion
when we focus on the composition. The composition $\circ$ defined by (3.2) is
not associative generally. Let
$\\{I_{i}\\},\\{J_{j}\\},\\{K_{k}\\}\in\mathcal{P}_{dis}^{2}(A)$ satisfying
$\mathcal{R}(\\{I_{i}\\})\cap\mathcal{R}(\\{J_{j}\\})\not=\emptyset$,
$\mathcal{R}(\\{I_{i}\\})\cap\mathcal{R}(\\{K_{k}\\})\not=\emptyset$,
$\mathcal{R}(\\{J_{j}\\})\cap\mathcal{R}(\\{K_{k}\\})\not=\emptyset$. We are
interested in the cases of $(\\{I_{i}\\}\circ\\{J_{j}\\})\circ\\{K_{k}\\}$ and
$\\{I_{i}\\}\circ(\\{J_{j}\\}\circ\\{K_{k}\\})$. In general, we have

$(\\{I_{i}\\}\circ\\{J_{j}\\})\circ\\{K_{k}\\}\not=\\{I_{i}\\}\circ(\\{J_{j}\\}\circ\\{K_{k}\\}).$

Roughly speaking, in the first case $\\{K_{k}\\}$ can insert into $I$ part or
$J$ part of $(\\{I_{i}\\}\circ\\{J_{j}\\})$ respectively, but, in the second
case $\\{K_{k}\\}$ can insert $J$ part only.

Firstly, we discuss the case of
$(\\{I_{i}\\}\circ\\{J_{j}\\})\circ\\{K_{k}\\}$ in details. By the formula
(2.7) we know that there are two possibilities which are:

  * •

$(\\{I_{i}\\}\circ_{a}^{\iota}\\{J_{j}\\})\circ_{b}^{\mu_{I}}\\{K_{k}\\}$,
where $1\leq a,b\leq m,\,a\not=b$, $\iota:I_{a}\rightarrow\\{J_{j}\\}$,
$\mu_{I}:I_{b}\rightarrow\\{K_{k}\\}$.

  * •

$(\\{I_{i}\\}\circ_{a}^{\iota}\\{J_{j}\\})\circ_{c}^{\mu_{J}}\\{K_{k}\\}$,
where $1\leq a\leq m,\,1\leq c\leq n$, $\iota:I_{a}\rightarrow\\{J_{j}\\}$,
$\mu_{J}:J_{c}\cup\iota^{-1}(J_{c})\rightarrow\\{K_{k}\\}$.

For example, let $a<b$, due to the formula (2.7) the insertion
$(\\{I_{i}\\}\circ_{a}^{\iota}\\{J_{j}\\})\circ_{b}^{\mu_{I}}\\{K_{k}\\}$ can
be expressed as the following diagram

$\begin{array}[]{ccccc}\\{\cdots,&\hat{I_{a}},&\cdots,&\hat{I_{b}},&\cdots\\}\\\
&\uparrow&&\uparrow&\\\
&\\{J_{j}\cup\iota^{-1}(J_{j})\\}&&\\{K_{k}\cup\mu_{I}^{-1}(K_{k})\\}&.\end{array}$

Therefore we have

######  Lemma 3.1.

Let $\\{I_{i}\\}$, $\\{J_{j}\\}$ and $\\{K_{k}\\}$ be as above,
$\iota:I_{a}\rightarrow\\{J_{j}\\}$, $\mu_{I}:I_{b}\rightarrow\\{K_{k}\\}$
($1\leq a,b\leq m,\,a\not=b$), we have

$(\\{I_{i}\\}\circ_{a}^{\iota}\\{J_{j}\\})\circ_{b}^{\mu_{I}}\\{K_{k}\\}=(\\{I_{i}\\}\circ_{b}^{\mu_{I}}\\{K_{k}\\})\circ_{a}^{\iota}\\{J_{j}\\}.$
(3.3)

For the case of $\\{K_{k}\\}$ inserting into $J$ part of
$\\{I_{i}\\}\circ_{a}^{\iota}\\{J_{j}\\}$ we have the following conclusion.

######  Proposition 3.1.

For each pair $(\iota,\mu_{J})$, $\iota:I_{a}\rightarrow\\{J_{j}\\}$,
$\mu_{J}:J_{c}\cup\iota^{-1}(J_{c})\rightarrow\\{K_{k}\\}$ ($1\leq a\leq
m,\,1\leq c\leq n$), there is an unique pair $(\iota^{\prime},\mu^{\prime})$,
$\mu^{\prime}:J_{c}\rightarrow\\{K_{k}\\}$,
$\iota^{\prime}:I_{a}\rightarrow\\{J_{j}\\}_{j\not=c}\cup\\{K_{k}\cup\mu^{\prime\,-1}(K_{k})\\}$,
such that

$(\\{I_{i}\\}\circ_{a}^{\iota}\\{J_{j}\\})\circ_{c}^{\mu_{J}}\\{K_{k}\\}=\\{I_{i}\\}\circ_{a}^{\iota^{\prime}}(\\{J_{j}\\}\circ_{c}^{\mu^{\prime}}\\{K_{k}\\}),$
(3.4)

and vice versa.

###### Proof.

For two insertions we have:

  * •

$(\\{I_{i}\\}\circ_{a}^{\iota}\\{J_{j}\\})\circ_{c}^{\mu_{J}}\\{K_{k}\\}$:

$\begin{array}[]{ccc}\\{\cdots,&I_{a},&\cdots\\}\\\ &\uparrow&\\\
\\{\cdots,&J_{c}\cup\iota^{-1}(J_{c}),&\cdots\\}\\\ &\uparrow&\\\
&\\{K_{k}\cup\mu_{J}^{-1}(K_{k})\\}&.\end{array}$

  * •

$\\{I_{i}\\}\circ_{a}^{\iota^{\prime}}(\\{J_{j}\\}\circ_{c}^{\mu^{\prime}}\\{K_{k}\\})$:

$\begin{array}[]{ccc}\\{\cdots,&I_{a},&\cdots\\}\\\ &\uparrow&\\\
\\{\cdots,&J_{c}\cup\iota^{\prime\,-1}(J_{c}),&\cdots\\}\\\ &\uparrow&\\\
&\\{K_{k}\cup\mu_{J}^{\prime\,-1}(K_{k})\cup\iota^{\prime\,-1}(K_{k}\cup\mu_{J}^{\prime\,-1}(K_{k}))\\}&.\end{array}$

In order to prove the formula (3.4) we need the conditions which are

  * •

$\iota^{-1}(\\{J_{j}\\}_{j\not=c})=\iota^{\prime\,-1}(\\{J_{j}\\}_{j\not=c})$,
and
$\iota|_{I_{a}\setminus\iota^{-1}(J_{c})}=\iota^{\prime}|_{I_{a}\setminus\iota^{-1}(J_{c})}$.

  * •

$\mu_{J}=\mu^{\prime}\cup\iota^{\prime}|_{\iota^{\prime\,-1}(J_{c})}$, or,
$\mu_{J}|_{J_{c}}=\mu^{\prime}$,
$\mu_{J}|_{\iota^{-1}(J_{c})}=\iota^{\prime}|_{\iota^{-1}(J_{c})}$.

From above conditions we can prove the formula (3.4) immediately.

∎

From lemma 3.1 and proposition 3.1 we have:

######  Proposition 3.2.

$\begin{array}[]{c}(\\{I_{i}\\}\circ\\{J_{j}\\})\circ\\{K_{k}\\}=\\{I_{i}\\}\circ(\\{J_{j}\\}\circ\\{K_{k}\\})\\\
+\sum\limits_{1\leq a,b\leq
m,\,a\not=b}\,\,\sum\limits_{\iota:I_{a}\to\\{J_{j}\\},\,\mu_{I}:I_{b}\to\\{K_{k}\\}}(\\{I_{i}\\}\circ_{a}^{\iota}\\{J_{j}\\})\circ_{b}^{\mu_{I}}\\{K_{k}\\}.\end{array}$
(3.5)

######  Remark 3.1.

The sum on the right side of the formula (3.5) concerns the $I$ part of
$(\\{I_{i}\\}\circ\\{J_{j}\\})\circ\\{K_{k}\\}$. We denote this sum by
$(\\{I_{i}\\}\circ\\{J_{j}\\})\circ\\{K_{k}\\}(K\hookrightarrow I)$ for short,
i.e. we have

$\begin{array}[]{c}(\\{I_{i}\\}\circ\\{J_{j}\\})\circ\\{K_{k}\\}(K\hookrightarrow
I)\\\ =\sum\limits_{1\leq a,b\leq
m,\,a\not=b}\,\,\sum\limits_{\iota:I_{a}\to\\{J_{j}\\},\,\mu_{I}:I_{b}\to\\{K_{k}\\}}(\\{I_{i}\\}\circ_{a}^{\iota}\\{J_{j}\\})\circ_{b}^{\mu_{I}}\\{K_{k}\\}.\end{array}$

Therefore, the formula (3.5) can be rewritten as

$(\\{I_{i}\\}\circ\\{J_{j}\\})\circ\\{K_{k}\\}=\\{I_{i}\\}\circ(\\{J_{j}\\}\circ\\{K_{k}\\})+(\\{I_{i}\\}\circ\\{J_{j}\\})\circ\\{K_{k}\\}(K\hookrightarrow
I).$

Combining lemma 3.1 and following the notation in remark 3.1 we have:

######  Corollary 3.1.

$(\\{I_{i}\\}\circ\\{J_{j}\\})\circ\\{K_{k}\\}(K\hookrightarrow
I)=(\\{I_{i}\\}\circ\\{K_{k}\\})\circ\\{J_{j}\\}(J\hookrightarrow I).$

Based on the discussion as above we are able to define the Lie bracket for
partitions.

######  Definition 3.2.

Let $\\{I_{i}\\},\\{J_{j}\\}\in\mathcal{P}_{dis}^{2}(A)$ with
$\mathcal{R}(\\{I_{i}\\})\cap\mathcal{R}(\\{J_{j}\\})=\emptyset$, their Lie
bracket is defined to be

$[\\{I_{i}\\},\\{J_{j}\\}]=\\{I_{i}\\}\circ\\{J_{j}\\}-\\{J_{j}\\}\circ\\{I_{i}\\}.$
(3.6)

In order to prove the bracket (3.6) is Lie bracket, it is enough for us to
check that Jacobi identity is valid.

######  Theorem 3.1.

The bracket (3.6) satisfies Jacobi identity.

###### Proof.

Let $\\{I_{i}\\},\\{J_{j}\\},\\{K_{k}\\}\in\mathcal{P}_{dis}^{2}(A)$
satisfying
$\mathcal{R}(\\{I_{i}\\})\cap\mathcal{R}(\\{J_{j}\\})\not=\emptyset$,
$\mathcal{R}(\\{I_{i}\\})\cap\mathcal{R}(\\{K_{k}\\})\not=\emptyset$,
$\mathcal{R}(\\{J_{j}\\})\cap\mathcal{R}(\\{K_{k}\\})\not=\emptyset$, we want
to prove Jacobi identity

$[\\{I_{i}\\},[\\{J_{j}\\},\\{K_{k}\\}]]+\,cocycle\,=0.$

With the help of proposition 3.2 and remark 3.1, by a straightforward
calculation we have

$\begin{array}[]{c}[\\{I_{i}\\},[\\{J_{j}\\},\\{K_{k}\\}]]+\,cocycle\\\
=(\\{K_{k}\\}\circ\\{J_{j}\\})\circ\\{I_{i}\\}(I\hookrightarrow
K)-(\\{J_{j}\\})\circ\\{K_{k}\\})\circ\\{I_{i}\\}(I\hookrightarrow J)\\\
+(\\{J_{j}\\}\circ\\{I_{i}\\})\circ\\{K_{k}\\}(K\hookrightarrow
J)-(\\{I_{i}\\}\circ\\{J_{j}\\})\circ\\{K_{k}\\}(K\hookrightarrow I)\\\
+(\\{I_{i}\\}\circ\\{K_{k}\\})\circ\\{J_{j}\\}(J\hookrightarrow
I)-(\\{K_{k}\\}\circ\\{I_{i}\\})\circ\\{J_{j}\\}(J\hookrightarrow
K).\end{array}$

Finally, from corollary 3.1 we get Jacobi identity. ∎

######  Remark 3.2.

In previous discussions we do not pay attention to the order of a partition
$\\{I_{i}\\}\in\mathcal{P}_{dis}^{2}(A)$, although the indices $i$ appear. If
we make an order in $\\{I_{i}\\}$ according to indices $\\{i\\}$, similar to
L. M. Ionescu [4] (definition 4.2 in [4]), in definition 3.1 we replace (3.1)
by

$\\{I_{i}\\}\circ\\{J_{j}\\}=\sum\limits_{a}(-1)^{a}\\{I_{i}\\}\circ_{a}\\{J_{j}\\},$
(3.7)

we can prove the Jacobi identity is valid still.

##  4 Applications to graphs

The construction discussed in section 2 and section 3 is suitable for graphs
including Feymman diagrams, Kontesvich’s graphs and the ordinary graphs in the
sense of graphic theory. For Feymman diagrams, we follow the notations in
Jean-Louis Loday and N. M. Nikolov [5], actually, which is one of our
motivation for the construction in this article. For simplicity, we do not
consider the coloured Feymman diagrams.

######  Definition 4.1.

  * •

A Feymman diagram is a pair $(\sigma,\\{I_{i}\\})$, where
$\\{I_{i}\\}\in\mathcal{P}_{dis}^{2}(A)$, $\sigma$ is a map from $I$ to
itself, $\sigma^{2}=\sigma$.

  * •

A ordinary graph is a pair $(\sigma,\\{I_{i}\\})$, where
$\\{I_{i}\\}\in\mathcal{P}_{dis}^{2}(A)$, $\sigma$ is a map from $I$ to itself
without fixed points, $\sigma^{2}=\sigma$.

  * •

An admissible graph is a triple $(\sigma,\\{I_{i}\\},\\{J_{j}\\})$, where
$\\{I_{i}\\},\\{J_{j}\\}\in\mathcal{P}_{dis}^{2}(A)$, $I\cap J=\emptyset$,
$\sigma$ is a map from $I\cup J$ to itself without fixed points,
$\sigma^{2}=\sigma$. $\\{I_{i}\\}$ and $\\{J_{j}\\}$ satisfy
$\sigma(I_{i})\cap I_{i}=\emptyset$, $\sigma(J_{j})\cap
J_{j^{\prime}}=\emptyset$, $\\#\sigma(I_{i})\cap I_{i^{\prime}}\leq 1$,
$\sigma(I_{i})\cap J_{j}\leq 1$, for all
$i,\,i^{\prime},\,j,\,j^{\prime},\,i\not=i^{\prime},\,j\not=j^{\prime}$.

Where $I=\mathcal{R}(\\{I_{i}\\})$, $J=\mathcal{R}(\\{J_{j}\\})$.

######  Remark 4.1.

  * •

In the cases of Feymman diagrams and ordinary graphs, the pair
$(\sigma,\\{I_{i}\\})$ determines the graph completely. The ordinary graphs is
a special case of Feymman diagrams. In those cases we denote the graph by
$\Gamma_{\sigma,\\{I_{i}\\}}$, or, $\Gamma_{\\{I_{i}\\}}$ sometime for short.
We call $\\{I_{i}\\}$ the set of vertices of $\Gamma_{\\{I_{i}\\}}$, denoted
by $\mathbf{vert}(\Gamma_{\\{I_{i}\\}})$. Actually, for a graph
$\Gamma_{\\{I_{i}\\}}$, there are two structure maps, $\sigma$ and projection
$p:\mathcal{R}(\\{I_{i}\\})\rightarrow\\{I_{i}\\}$,
$p(e)=I_{i}\Longleftrightarrow e\in I_{i}$. $I=\mathcal{R}(\\{I_{i}\\})$ is
called the total set of edges, $I_{ext}=\\{e\in I|\sigma(e)=e\\}$ is the set
of external lines. The set of internal lines is taken to be
$I_{int}=(I\setminus I_{ext})\diagup\sim$, where $\sim$ is an equivalent
relation on $I\setminus I_{ext}$, $e_{1}\sim e_{2}\Longleftrightarrow
e_{1}=\sigma(e_{2})$, ($e_{1},e_{2}\in I\setminus I_{ext}$,
$e_{1}\not=e_{2}$). A Feymman diagram without external lines can be regarded
as an ordinary graph in the sense of graphic theory.

  * •

$\Gamma_{\\{I_{i}\\}}$ is a disconnected graph if and only if there is a non-
travail proper subset $\\{I_{i^{\prime}}\\}$ of $\\{I_{i}\\}$ such that
$\sigma(\mathcal{R}(\\{I_{i^{\prime}}\\}))\cap\mathcal{R}(\\{I_{i}\\}\setminus\\{I_{i^{\prime}}\\})=\emptyset$.

  * •

For the case of Kontesvich’s graphs, we ignore the orientation of lines in
definition 4.1. We now discuss that in details here. In this case we divide
the vertices into two groups, $\\{I_{i}\\}$ and $\\{J_{j}\\}$. We call
$\\{I_{i}\\}$ the set of vertices of the first type, $\\{J_{j}\\}$ the set of
vertices of the second type. We consider the equivalent relation mentioned
above. Under this equivalent relation, each equivalent class consists of two
elements $(e,\sigma(e))$ and $(\sigma(e),e)$ ($e\in I\cup J$). We can only
choose one element in an equivalent class, for example, $(e,\sigma(e))$, to
represent a line, where $e$ is starting point of the line $(e,\sigma(e))$, and
$\sigma(e)$ is end point of this line. Furthermore, if $e\in J$, $e$ can not
be the starting point of some line, actually, from definition 4.1 we know
$\sigma(J)\cap J=\emptyset$. We denote the admissible graph
$(\sigma,\\{I_{i}\\},\\{J_{j}\\})$ by
$\Gamma_{\sigma,\\{I_{i}\\},\\{J_{j}\\}}$, or,
$\Gamma_{\\{I_{i}\\},\\{J_{j}\\}}$ sometime for short.

We now pay attention to subgraphs.

######  Definition 4.2.

  * •

Let $(\sigma,\\{I_{i}\\})$ be a Feymman diagram, $\\{J_{j}\\}$ be a subset of
$\\{I_{i}\\}$. A subgraph of $\Gamma_{\\{I_{i}\\}}$ relevant to $\\{J_{j}\\}$
is a pair $(\sigma_{\\{J_{j}\\}},\\{J_{j}\\})$, denoted by
$\Gamma_{\\{J_{j}\\}}\subset\Gamma_{\\{I_{i}\\}}$ also.
$\sigma_{\\{J_{j}\\}}:J\to J$ ($J=\mathcal{R}(\\{J_{j}\\})$) is defined as:

$\begin{array}[]{c}\sigma_{\\{J_{j}\\}}(e)=\sigma(e),\,e\in\sigma(J)\cap J,\\\
\sigma_{\\{J_{j}\\}}(e)=e,\,e\in J\setminus(\sigma(J)\cap J).\end{array}$

  * •

Let $(\sigma,\\{I_{i}\\})$ be an ordinary graph, $\\{J_{j}\\}$ be a subset of
$\\{I_{i}\\}$. A subgraph of $\Gamma_{\\{I_{i}\\}}$ relevant to $\\{J_{j}\\}$
is a pair $(\sigma|_{J^{\prime}},\\{J_{j}^{\prime}\\})$ denoted by
$\Gamma_{\\{J_{j}^{\prime}\\}}\subset\Gamma_{\\{I_{i}\\}}$ as well, where
$J^{\prime}=\sigma(J)\cap J$, and $\\{J_{j}^{\prime}\\}=J_{j}\cap J^{\prime}$.

  * •

Let $(\sigma,\\{I_{i}\\},\\{J_{j}\\})$ be an admissible graph, $\\{L_{l}\\}$
be a subset of $\\{I_{i}\\}$, $\\{K_{k}\\}$ be a subset of $\\{J_{j}\\}$,
satisfying $K_{k}\cap\sigma(L)\not=\emptyset$ for all $k$
($L=\mathcal{R}(\\{L_{l}\\})$). A subgraph of
$\Gamma_{\sigma,\\{I_{i}\\},\\{J_{j}\\}}$ relevant to $\\{L_{l}\\}$ and
$\\{K_{k}\\}$ is a triple
$(\sigma|_{I_{L,K}\cup(K\cap\sigma(L))},\\{L_{l}^{\prime}\\},\\{K_{k}^{\prime}\\})$,
denoted by $\Gamma_{\\{L_{l}^{\prime}\\},\\{K_{k}^{\prime}\\}}$ also, where

$I_{L,K}=(\sigma^{-1}(L)\cup\sigma^{-1}(K))\cap L,$

$L_{l}^{\prime}=L_{l}\cap I_{L,K}$, $K_{k}^{\prime}=K_{k}\cap\sigma(L)$,
$K=\mathcal{R}(\\{K_{k}\\})$. The orientation of lines in
$\Gamma_{\\{I_{i}^{\prime}\\},\\{K_{k}^{\prime}\\}}$ inherits one of lines in
$\Gamma_{\sigma,\\{I_{i}\\},\\{J_{j}\\}}$.

######  Remark 4.2.

  * •

In the case of Feymman diagrams, we have
$vert(\Gamma_{\\{J_{j}\\}})=\\{J_{j}\\}$, and the set of internal lines of
$\Gamma_{\\{J_{j}\\}}$ should be
$[(\sigma(\mathcal{R}(\\{J_{j}\\})\cap\mathcal{R}(\\{J_{j}\\}))\setminus\Gamma_{\\{I_{i}\\},ext}]\diagup\sim$.

  * •

For the case of ordinary graphs, the definition of subgraph is different from
the case of Feymman diagrams, because there are not external lines in the case
of ordinary graphs.

Now we discuss the quotient. We will see that the quotient of the partitions
defined in section 2 is compatible with the quotient of graphs.

######  Definition 4.3.

  * •

Let $\Gamma_{\\{I_{i}\\}}$ be a connected Feymman diagram, and
$\Gamma_{\\{J_{j}\\}}\subset\Gamma_{\\{I_{i}\\}}$ be a connected subgraph,
where $\\{J_{j}\\}$ is a subset of $\\{I_{i}\\}$. We define the quotient of
$\Gamma_{\\{I_{i}\\}}$ by $\Gamma_{\\{J_{j}\\}}$ to be a pair
$(\sigma_{\\{I_{i}\\}\diagup\\{J_{j}^{\prime}\\}},\\{I_{i}\\}\diagup\\{J_{j}^{\prime}\\})$,
denoted by $\Gamma_{\\{I_{i}\\}}\diagup\Gamma_{\\{J_{j}\\}}$ also, where
$J_{j}^{\prime}=J_{j}\cap[(\sigma(J)\cap J)\setminus I_{ext}]$,
$\sigma_{\\{I_{i}\\}\diagup\\{J_{j}^{\prime}\\}}=\sigma|_{\mathcal{R}(\\{I_{i}\\}\diagup\\{J_{j}^{\prime}\\})}$.

  * •

Let $\Gamma_{\\{I_{i}\\}}$ be a connected ordinary graph, $\\{J_{j}\\}$ is a
subset of $\\{I_{i}\\}$, and
$\Gamma_{\\{J_{j}^{\prime}\\}}\subset\Gamma_{\\{I_{i}\\}}$ be a connected
subgraph. We define the quotient of $\Gamma_{\\{I_{i}\\}}$ by
$\Gamma_{\\{J_{j}^{\prime}\\}}$ to be a pair
$(\sigma_{\\{I_{i}\\}\diagup\\{J_{j}^{\prime}\\}},\\{I_{i}\\}\diagup\\{J_{j}^{\prime}\\})$,
denoted by $\Gamma_{\\{I_{i}\\}}\diagup\Gamma_{\\{J_{j}^{\prime}\\}}$ also,
where $J_{j}^{\prime}=J_{j}\cap(\sigma(J)\cap J)$,
$\sigma_{\\{I_{i}\\}\diagup\\{J_{j}^{\prime}\\}}=\sigma|_{\mathcal{R}(\\{I_{i}\\}\diagup\\{J_{j}^{\prime}\\})}$.

  * •

Let $\Gamma_{\sigma,\\{I_{i}\\},\\{J_{j}\\}}$ be a connected admissible graph,
$\Gamma_{\\{L_{l}^{\prime}\\},\\{K_{k}^{\prime}\\}}$ be a connected subgraph
relevant to $\\{L_{l}\\}$ and $\\{K_{k}\\}$, where $\\{L_{l}\\}$ be a subset
of $\\{I_{i}\\}$, $\\{K_{k}\\}$ be a subset of $\\{J_{j}\\}$. We define the
quotient of $\Gamma_{\sigma,\\{I_{i}\\},\\{J_{j}\\}}$ by
$\Gamma_{\\{L_{l}^{\prime}\\},\\{K_{k}^{\prime}\\}}$ to be a triple

$(\sigma|_{(I\setminus L^{\prime})\cup(J\cup
K^{\prime})},\\{I_{i}\\}\diagup\\{L_{l}^{\prime}\\},\\{J_{j}\\}\diagup\\{K_{k}^{\prime}\\})$

denoted by
$\Gamma_{\sigma,\\{I_{i}\\},\\{J_{j}\\}}\diagup\Gamma_{\\{L_{l}^{\prime}\\},\\{K_{k}^{\prime}\\}}$
also, where $L_{l}^{\prime}=L_{l}\cap I_{L,K}$,
$K_{k}^{\prime}=K_{k}\cap\sigma(L)$,
$L^{\prime}=\mathcal{R}(\\{L_{l}^{\prime}\\})$,
$K^{\prime}=\mathcal{R}(\\{K_{k}^{\prime}\\})$, $L,\,K,\,I_{L,K}$ is same as
in definition 4.2. The orientation of lines in
$\Gamma_{\sigma,\\{I_{i}\\},\\{J_{j}\\}}\diagup\Gamma_{\\{L_{l}^{\prime}\\},\\{K_{k}^{\prime}\\}}$
inherits one of lines in $\Gamma_{\sigma,\\{I_{i}\\},\\{J_{j}\\}}$.

######  Remark 4.3.

  * •

In the cases of Feymman diagrams and ordinary graphs, because
$\Gamma_{\\{I_{i}\\}}$ is connected in above definition, we have
$\mathcal{R}(\\{J_{j}\\})\not=\sigma(\mathcal{R}(\\{J_{j}\\})\cap\mathcal{R}(\\{J_{j}\\})$.
Thus, $\\{J_{j}^{\prime}\\}$ is not a subset of $\\{I_{i}\\}$, recalling the
discussion in section 2, we know that
$\\{J_{j}^{\prime}\\}\sqsubset\\{I_{i}\\}$. It is obvious that

$\Gamma_{\\{I_{i}\\}}\diagup\Gamma_{\\{J_{j}\\}}=\Gamma_{\\{I_{i}\\}\diagup\\{J_{j}^{\prime}\\}},$

where $\Gamma_{\\{I_{i}\\}\diagup\\{J_{j}^{\prime}\\}}$ is endowed with
structure map $\sigma_{\\{I_{i}\\}\diagup\\{J_{j}^{\prime}\\}}$.

  * •

Similarly, in the case of Kontesvich’s graphs we have

$\Gamma_{\sigma,\\{I_{i}\\},\\{J_{j}\\}}\diagup\Gamma_{\\{L_{l}^{\prime}\\},\\{K_{k}^{\prime}\\}}=\Gamma_{\\{I_{i}\\}\diagup\\{L_{l}^{\prime}\\},\\{J_{j}\\}\diagup\\{K_{k}^{\prime}\\}},$

where
$\Gamma_{\\{I_{i}\\}\diagup\\{L_{l}^{\prime}\\},\\{J_{j}\\}\diagup\\{K_{k}^{\prime}\\}}$
is endowed with structure map $\sigma|_{(I\setminus L^{\prime})\cup(J\cup
K^{\prime})}$.

If subgraph $\Gamma_{\\{J_{j}\\}}$ is not connected, it admits of a
decomposition $\\{J_{j}\\}=\bigcup_{l=1}^{q}\\{J_{j_{l}}^{(l)}\\}$, therefore
$\\{J_{j}^{\prime}\\}=\bigcup_{l=1}^{q}\\{J_{j_{l}}^{\prime\,(l)}\\}$, such
that each $\Gamma_{\\{J_{j_{l}}^{(l)}\\}}$ is connected subgraph. Moreover,
$\Gamma_{\\{J_{j}\\}}=\bigcup_{l}\Gamma_{\\{J_{j_{l}}^{(l)}\\}}$. The quotient
$\Gamma_{\\{I_{i}\\}}\diagup\Gamma_{\\{J_{j}^{\prime}\\}}$ is defined to be

$\Gamma_{\\{I_{i}\\}}\diagup\Gamma_{\\{J_{j}\\}}=(\cdots((\Gamma_{\\{I_{i}\\}}\diagup\Gamma_{\\{J_{j_{1}}^{\prime(1)}\\}})\diagup\Gamma_{\\{J_{j_{2}}^{\prime(2)}\\}})\cdots)\diagup\Gamma_{\\{J_{j_{q}}^{\prime(q)}\\}}.$

On the other hand, from viewpoint of partition,
$\Gamma_{\\{J_{j}^{\prime}\\}}=\bigcup_{l}\Gamma_{\\{J_{j_{l}}^{\prime(l)}\\}}$
corresponds to
$(\cdots,\\{I_{i}\\}_{\mathcal{R}(\\{J_{j_{l}}^{\prime\,(l)}\\})},\cdots)$,
and we have

$\Gamma_{\\{I_{i}\\}}\diagup\Gamma_{\\{J_{j}\\}}=\Gamma_{\\{I_{i}\\}\diagup(\mathcal{R}(\\{J_{j_{l}}^{\prime\,(l)}\\}))}.$

Similar to the situation of quotient, the insertion of the partitions is
compatible with the insertion of Feymman diagrams as well.

######  Definition 4.4.

  * •

Let $(\sigma,\\{I_{i}\\}_{i=1}^{m})$, $(\lambda,\\{J_{j}\\}_{j=1}^{n})$ be two
Feymman diagrams, or, two ordinary graphs, with structure maps $\sigma$ and
$\lambda$ ($I\cap J=\emptyset$). Then we define
$(\delta,\\{I_{i}\\}\circ_{a}^{\iota}\\{J_{j}\\})$ to be the insertion of
$\Gamma_{\\{J_{j}\\}}$ into $\Gamma_{\\{I_{i}\\}}$ at $I_{a}$ by $\iota$,
denoted by $\Gamma_{\\{I_{i}\\}}\circ_{a}^{\iota}\Gamma_{\\{J_{j}\\}}$ also.
Where $1\leq a\leq m$, $\iota:I_{a}\to\\{J_{j}\\}$, $\delta|_{I}=\sigma$,
$\delta|_{J}=\lambda$, $I=\mathcal{R}(\\{I_{i}\\})$,
$J=\mathcal{R}(\\{J_{j}\\})$.

  * •

Let $\Gamma_{\\{I_{i}\\},\\{J_{j}\\}}$ and $\Gamma_{\\{L_{l}\\},\\{K_{k}\\}}$
be two admissible graphs with structure maps $\sigma$ and $\lambda$ ($(I\cup
J)\cap(L\cup K)=\emptyset$). We define the insertion of
$\Gamma_{\\{L_{l}\\},\\{K_{k}\\}}$ into $\Gamma_{\\{I_{i}\\},\\{J_{j}\\}}$ in
two ways.

    * –

Let $1\leq a\leq\\#\\{I_{i}\\}$, $1\leq b\leq\\#\\{J_{j}\\}$,
$\iota:I_{a}\to\\{L_{l}\\}$, $\kappa:J_{b}\to\\{K_{k}\\}$, we define the
insertion to be the triple

$(\delta,\\{I_{i}\\}\circ_{a}^{\iota}\\{L_{l}\\},\\{J_{j}\\}\circ_{b}^{\kappa}\\{K_{k}\\}),$

where $\delta$ satisfies $\delta|_{I\cup J}=\sigma$, $\delta|_{L\cup
K}=\lambda$, $I=\mathcal{R}(\\{I_{i}\\})$, $J=\mathcal{R}(\\{J_{j}\\})$,
$L=\mathcal{R}(\\{L_{l}\\})$, $K=\mathcal{R}(\\{K_{k}\\})$.

    * –

Let $1\leq a\leq\\#\\{I_{i}\\}$, $\iota:I_{a}\to\\{L_{l}\\}$,
$\kappa:K\to\\{K_{k}\\}$ ($\kappa^{-1}(K_{k})=K_{k}$), we define the insertion
to be a triple

$(\delta,\\{I_{i}\\}\circ_{a}^{\iota}\\{L_{l}\\},(\\{J_{j}\\}\cup\\{K\\})\circ_{K}\\{K_{k}\\}),$

where $\delta$ is same as above. We call the second insertion is travail case.

For two Feymman diagrams $(\sigma,\\{I_{i}\\})$, $(\lambda,\\{J_{j}\\})$, if
$\mathcal{R}(\\{I_{i}\\})=\mathcal{R}(\\{I_{i}\\})$, and $\sigma=\delta$, we
define

$\alpha(\sigma,\\{I_{i}\\})+\beta(\lambda,\\{J_{j}\\})=(\sigma,\alpha\\{I_{i}\\}+\beta\\{J_{j}\\}).$

In formal way, above formula can expressed as

$\alpha\Gamma_{\\{I_{i}\\}}+\beta\Gamma_{\\{J_{j}\\}}=\Gamma_{\alpha\\{I_{i}\\}+\beta\\{J_{j}\\}}.$

Following above notations, under the assumption about
$\sigma,\,\lambda,\,\delta$, we have

$\Gamma_{\\{I_{i}\\}}\circ_{a}^{\iota}\Gamma_{\\{J_{j}\\}}=\Gamma_{\\{I_{i}\\}\circ_{a}^{\iota}\\{J_{j}\\}}.$

Furthermore, we have

$\begin{array}[]{c}\Gamma_{\\{I_{i}\\}}\circ_{a}\Gamma_{\\{J_{j}\\}}=\Gamma_{\\{I_{i}\\}\circ_{a}\\{J_{j}\\}},\\\
\Gamma_{\\{I_{i}\\}}\circ\Gamma_{\\{J_{j}\\}}=\Gamma_{\\{I_{i}\\}\circ\\{J_{j}\\}},\end{array}$

and

$[\Gamma_{\\{I_{i}\\}},\Gamma_{\\{J_{j}\\}}]=\Gamma_{[\\{I_{i}\\},\\{J_{j}\\}]}.$

The case of Kontesvich’s graphs is similar.

## References

  * [1] A. Connes, D. Kreimer, Renormalization in quantum field theory and the Riemann-Hilbert problem. I. The Hopf algebra structure of graphs and the main theorem. Comm. Math. Phys. 210 (2000), no. 1, 249–273.
  * [2] A. Connes, D. Kreimer, Renormalization in quantum field theory and the Riemann-Hilbert problem. II. The $\beta$-function, diffeomorphisms and the renormalization group. Comm. Math. Phys. 216 (2001), no. 1, 215–241.
  * [3] A. Connes, M. Marcolli, Noncommutative Geometry, Quantum Fields and Motives. American Mathematical Society, 2007-12-20.
  * [4] L. M. Ionescu, _A combinatorial approach to coefficients in deformation quantization_ , [arXiv:math/0404389v1].
  * [5] Jean-Louis Loday and N. M. Nikolov, Operadic construction of the renormalization group. [arXiv:math-ph.1202.1206v1]
  * [6] D. Kreimer,On the Hopf algebra structure of perturbative quantum field theories. Adv. Theor. Math.Phy. 2 (1998), no. 2, 303-334.
  * [7] M. Kontsevich, _Deformation quantization of Poisson manifolds_ , Letters Math. Phys. 66 (2003), no.3, 157-216,[arXiv:q-alg/9709040].
  * [8] D. E. Radford, _Hopf Algebras_ , World Scientific Publishing Co. Pte. Ltd. 2012.
  * [9] ZhouMai, _Hopf Algebras Concerning Matrices or Finite Sets and Their Application to Star Product of Scalar fields_ , [arXiv:math-ph/2006.11786v3]