* [45] Y. Li, S. Lyu, Exposing deepfake videos by detecting face warping artifacts, arXiv preprint arXiv:1811.00656.
  * [46] D. Afchar, V. Nozick, J. Yamagishi, I. Echizen, Mesonet: a compact facial video forgery detection network, in: 2018 IEEE International Workshop on Information Forensics and Security (WIFS), IEEE, 2018, pp. 1–7.
  * [47] I. Amerini, L. Galteri, R. Caldelli, A. Del Bimbo, Deepfake Video Detection through Optical Flow Based CNN, in: Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV) Workshops, 2019, pp. 1–3.
  * [48] S. A. Gowda, N. Thillaiarasu, Investigation of comparison on modified cnn techniques to classify fake face in deepfake videos, in: 8th International Conference on Advanced Computing and Communication Systems (ICACCS), Vol. 1, 2022, pp. 702–707.
  * [49] S. Agarwal, T. El-Gaaly, H. Farid, S. Lim, Detecting deep-fake videos from appearance and behavior, in: IEEE Workshop on Image Forensics and Security, IEEExplore, 2020, pp. 1–12.
  * [50] S. Agarwal, H. Farid, O. Fried, M. Agrawala, Detecting deep-fake videos from phoneme-viseme mismatches, in: IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), 2020, pp. 2814–2822.
  * [51] M. C. El Rai, H. Al Ahmad, O. Gouda, D. Jamal, M. A. Talib, Q. Nasir, Fighting Deepfake by Residual Noise Using Convolutional Neural Networks, in: 3rd International Conference on Signal Processing and Information Security (ICSPIS), IEEE, 2020, pp. 1–4.
  * [52] B. Malolan, A. Parekh, F. Kazi, Explainable deep-fake detection using visual interpretability methods, in: 3rd International Conference on Information and Computer Technologies (ICICT), IEEExplore, 2020, pp. 289–293.
  * [53] P. Ranjan, S. Patil, F. Kazi, Improved generalizability of deep-fakes detection using transfer learning based cnn framework, in: 3rd International Conference on Information and Computer Technologies (ICICT), 2020, pp. 86–90.
  * [54] H. Mittal, M. Saraswat, J. C. Bansal, A. Nagar, Fake-face image classification using improved quantum-inspired evolutionary-based feature selection method, in: IEEE Symposium Series on Computational Intelligence (SSCI), 2020, pp. 989–995.
  * [55] B. Zi, M. Chang, J. Chen, X. Ma, Y.-G. Jiang, Wilddeepfake: A challenging real-world dataset for deepfake detection, in: Proceedings of the 28th ACM International Conference on Multimedia, 2020, pp. 2382–2390.
  * [56] U. A. Ciftci, I. Demir, L. Yin, Fakecatcher: Detection of synthetic portrait videos using biological signals, IEEE Transactions on Pattern Analysis and Machine Intelligence.
  * [57] Y. Wang, A. Dantcheva, A video is worth more than 1000 lies. Comparing 3DCNN approaches for detecting deepfakes, in: 15th IEEE International Conference on Automatic Face and Gesture Recognition (FG), IEEE, 2020, pp. 515–519.
  * [58] D. Wodajo, S. Atnafu, Deepfake video detection using convolutional vision transformer (2021).  arXiv:2102.11126.
  * [59] Q. ul ain, N. Nida, A. Irtaza, N. Ilyas, Forged face detection using ela and deep learning techniques, in: 2021 International Bhurban Conference on Applied Sciences and Technologies (IBCAST), 2021, pp. 271–275.  doi:10.1109/IBCAST51254.2021.9393234.
  * [60] J. B. Awotunde, R. G. Jimoh, A. L. Imoize, A. T. Abdulrazaq, C. Li, C. Lee, An enhanced deep learning-based deepfake video detection and classification system, Electronics 12 (1).
  * [61] A. Das, L. Sebastian, A comparative analysis and study of a fast parallel cnn based deepfake video detection model with feature selection (fpc-dfm), in: 2023 Advanced Computing and Communication Technologies for High Performance Applications (ACCTHPA), IEEE, 2023, pp. 1–9.
  * [62] M. Masood, M. Nawaz, A. Javed, T. Nazir, A. Mehmood, R. Mahum, Classification of deepfake videos using pre-trained convolutional neural networks, in: 2021 International Conference on Digital Futures and Transformative Technologies (ICoDT2), IEEE, 2021, pp. 1–6.
  * [63] A. Mitra, S. P. Mohanty, P. Corcoran, E. Kougianos, A novel machine learning based method for deepfake video detection in social media, in: 2020 IEEE International Symposium on Smart Electronic Systems (iSES)(Formerly iNiS), IEEE, 2020, pp. 91–96.
  * [64] M. Patel, A. Gupta, S. Tanwar, M. Obaidat, Trans-df: a transfer learning-based end-to-end deepfake detector, in: 2020 IEEE 5th international conference on computing communication and automation (ICCCA), IEEE, 2020, pp. 796–801.
  * [65] R. Rafique, M. Nawaz, H. Kibriya, M. Masood, Deepfake detection using error level analysis and deep learning, in: 2021 4th International Conference on Computing & Information Sciences (ICCIS), IEEE, 2021, pp. 1–4.
  * [66] J. Wang, X. Li, Y. Zhao, A novel face forgery detection method based on edge details and reused-network, in: 2021 IEEE 9th International Conference on Computer Science and Network Technology (ICCSNT), IEEE, 2021, pp. 100–104.
  * [67] E. Sabir, J. Cheng, A. Jaiswal, W. AbdAlmageed, I. Masi, P. Natarajan, Recurrent convolutional strategies for face manipulation detection in videos, Interfaces (GUI) 3 (1) (2019) 80–87.
  * [68] D. M. Montserrat, H. Hao, S. K. Yarlagadda, S. Baireddy, R. Shao, J. Horváth, E. Bartusiak, J. Yang, D. Guera, F. Zhu, et al., Deepfakes detection with automatic face weighting, in: Proceedings of the IEEE/CVF conference on computer vision and pattern recognition workshops, 2020, pp. 668–669.
  * [69] G. Jaiswal, Hybrid recurrent deep learning model for deepfake video detection, in: 2021 IEEE 8th Uttar Pradesh Section International Conference on Electrical, Electronics and Computer Engineering (UPCON), IEEE, 2021, pp. 1–5.
  * [70] Y. Tu, Y. Liu, X. Li, Deepfake video detection by using convolutional gated recurrent unit, in: 2021 13th International Conference on Machine Learning and Computing, 2021, pp. 356–360.
  * [71] H. Hao, E. R. Bartusiak, D. Güera, D. Mas Montserrat, S. Baireddy, Z. Xiang, S. K. Yarlagadda, R. Shao, J. Horváth, J. Yang, et al., Deepfake detection using multiple data modalities, in: Handbook of Digital Face Manipulation and Detection: From DeepFakes to Morphing Attacks, Springer International Publishing Cham, 2022, pp. 235–254.
  * [72] A. Ismail, M. Elpeltagy, M. S. Zaki, K. Eldahshan, An integrated spatiotemporal-based methodology for deepfake detection, Neural Computing and Applications 34 (24) (2022) 21777–21791.
  * [73] W. Pu, J. Hu, X. Wang, Y. Li, S. Hu, B. Zhu, R. Song, Q. Song, X. Wu, S. Lyu, Learning a deep dual-level network for robust deepfake detection, Pattern Recognition 130 (2022) 108832.
  * [74] M. Elpeltagy, A. Ismail, M. S. Zaki, K. Eldahshan, A novel smart deepfake video detection system, International Journal of Advanced Computer Science and Applications 14 (1).
  * [75] Y. Sun, Z. Zhang, I. Echizen, H. H. Nguyen, C. Qiu, L. Sun, Face forgery detection based on facial region displacement trajectory series, in: IEEE/CVF Winter Conference on Applications of Computer Vision Workshops (WACVW), IEEE Computer Society, Los Alamitos, CA, USA, 2023, pp. 633–642.
  * [76] D. Güera, E. J. Delp, Deepfake video detection using recurrent neural networks, in: 15th IEEE International Conference on Advanced Video and Signal Based Surveillance (AVSS), IEEE, 2018, pp. 1–6.
  * [77] Y. Li, M. Chang, S. Lyu, In ictu oculi: Exposing AI created fake videos by detecting eye blinking, in: IEEE International Workshop on Information Forensics and Security (WIFS), IEEExplore, 2018, pp. 1–7.
  * [78] C. C. Ki Chan, V. Kumar, S. Delaney, M. Gochoo, Combating deepfakes: Multi-lstm and blockchain as proof of authenticity for digital media, in: 2020 IEEE / ITU International Conference on Artificial Intelligence for Good (AI4G), 2020, pp. 55–62.  doi:10.1109/AI4G50087.2020.9311067.
  * [79] Y. Al-Dhabi, S. Zhang, Deepfake video detection by combining convolutional neural network (cnn) and recurrent neural network (rnn), in: 2021 IEEE International Conference on Computer Science, Artificial Intelligence and Electronic Engineering (CSAIEE), 2021, pp. 236–241.  doi:10.1109/CSAIEE54046.2021.9543264.
  * [80] D.-C. Stanciu, B. Ionescu, Deepfake Video Detection with Facial Features and Long-Short Term Memory Deep Networks, in: 2021 International Symposium on Signals, Circuits and Systems (ISSCS), IEEE, 2021, pp. 1–4.
  * [81] Z. Zhang, C. Mal, B. Ding, M. Gao, Detecting manipulated facial videos: A time series solution, in: 2020 25th International Conference on Pattern Recognition (ICPR), IEEE, 2021, pp. 2817–2823.
  * [82] H. Ilyas, A. Irtaza, A. Javed, K. M. Malik, Deepfakes examiner: An end-to-end deep learning model for deepfakes videos detection, in: 2022 16th International Conference on Open Source Systems and Technologies (ICOSST), 2022, pp. 1–6.
  * [83] K. Jalui, A. Jagtap, S. Sharma, G. Mary, R. Fernandes, M. Kolhekar, Synthetic content detection in deepfake video using deep learning, in: 2022 IEEE 3rd Global Conference for Advancement in Technology (GCAT), IEEE, 2022, pp. 01–05.
  * [84] V. Jolly, M. Telrandhe, A. Kasat, A. Shitole, K. Gawande, Cnn based deep learning model for deepfake detection, in: 2022 2nd Asian Conference on Innovation in Technology (ASIANCON), 2022, pp. 1–5.  doi:10.1109/ASIANCON55314.2022.9908862.
  * [85] A. Khedkar, A. Peshkar, A. Nagdive, M. Gaikwad, S. Baudha, Exploiting spatiotemporal inconsistencies to detect deepfake videos in the wild, in: 2022 10th International Conference on Emerging Trends in Engineering and Technology-Signal and Information Processing (ICETET-SIP-22), IEEE, 2022, pp. 1–6.
  * [86] L. Kuang, Y. Wang, T. Hang, B. Chen, G. Zhao, A dual-branch neural network for deepfake video detection by detecting spatial and temporal inconsistencies, Multimedia Tools and Applications 81 (29) (2022) 42591–42606.
  * [87] L. S, K. Sooda, DeepFake Detection Through Key Video Frame Extraction using GAN, in: 2022 International Conference on Automation, Computing and Renewable Systems (ICACRS), 2022, pp. 859–863.  doi:10.1109/ICACRS55517.2022.10029095.
  * [88] D. Liu, Z. Yang, R. Zhang, J. Liu, A robust deepfake video detection method based on continuous frame face-swapping, in: 2022 International Conference on Artificial Intelligence, Information Processing and Cloud Computing (AIIPCC), 2022, pp. 188–191.  doi:10.1109/AIIPCC57291.2022.00048.
  * [89] N. Patel, N. Jethwa, C. Mali, J. Deone, Deepfake video detection using neural networks, in: ITM Web of Conferences, Vol. 44, EDP Sciences, 2022, p. 03024.
  * [90] S. J. Pipin, R. Purba, M. F. Pasha, Deepfake Video Detection Using Spatiotemporal Convolutional Network and Photo Response Non Uniformity, in: 2022 IEEE International Conference of Computer Science and Information Technology (ICOSNIKOM), IEEE, 2022, pp. 1–6.
  * [91] A. M. Saber, M. T. Hassan, M. S. Mohamed, R. ELHusseiny, Y. M. Eltaher, M. Abdelrazek, Y. M. Kamal Omar, Deepfake video detection, in: 2022 2nd International Mobile, Intelligent, and Ubiquitous Computing Conference (MIUCC), 2022, pp. 425–431.  doi:10.1109/MIUCC55081.2022.9781791.
  * [92] S. Saif, S. Tehseen, S. S. Ali, S. Kausar, A. Jameel, Generalized deepfake video detection through time-distribution and metric learning, IT Professional 24 (2) (2022) 38–44.  doi:10.1109/MITP.2022.3168351.
  * [93] P. Saikia, D. Dholaria, P. Yadav, V. Patel, M. Roy, A hybrid cnn-lstm model for video deepfake detection by leveraging optical flow features (2022).  arXiv:2208.00788.
  * [94] R. V. Saraswathi, M. Gadwalkar, S. S. Midhun, G. N. Goud, A. Vidavaluri, Detection of synthesized videos using cnn, in: 2022 International Conference on Augmented Intelligence and Sustainable Systems (ICAISS), IEEE, 2022, pp. 01–05.
  * [95] J. Wang, X. Li, Y. Zhao, D3: A novel face forgery detector based on dual-stream and dual-utilization methods, in: Advances in Artificial Intelligence and Security: 8th International Conference on Artificial Intelligence and Security, ICAIS 2022, Qinghai, China, July 15–20, 2022, Proceedings, Part I, Springer, 2022, pp. 413–425.
  * [96] S. R. B. R, P. Kumar Pareek, B. S, G. G, Deepfake video detection system using deep neural networks, in: IEEE International Conference on Integrated Circuits and Communication Systems (ICICACS), 2023, pp. 1–6.
  * [97] S. A. Khan, D.-T. Dang-Nguyen, Hybrid transformer network for deepfake detection, in: Proceedings of the 19th international conference on content-based multimedia indexing, 2022, pp. 8–14.
  * [98] D. A. Coccomini, N. Messina, C. Gennaro, F. Falchi, Combining efficientnet and vision transformers for video deepfake detection, in: Image Analysis and Processing (ICIAP 2022), Springer International Publishing, Cham, 2022, pp. 219–229.
  * [99] J. Feinland, J. Barkovitch, D. Lee, A. Kaforey, U. A. Ciftci, Poker bluff detection dataset based on facial analysis, in: International Conference on Image Analysis and Processing, Springer, 2022, pp. 400–410.
  * [100] Z. Xue, Q. Liu, H. Shi, R. Zou, X. Jiang, A transformer-based deepfake-detection method for facial organs, Electronics 11 (24).
  * [101] Y. Zhang, T. Wang, M. Shu, Y. Wang, A robust lightweight deepfake detection network using transformers, in: Pacific Rim International Conference on Artificial Intelligence, Springer, 2022, pp. 275–288.
  * [102] A. Khormali, J.-S. Yuan, DFDT: an end-to-end deepfake detection framework using vision transformer, Applied Sciences 12 (6) (2022) 2953.
  * [103] D. A. Coccomini, R. Caldelli, F. Falchi, C. Gennaro, G. Amato, Cross-Forgery Analysis of Vision Transformers and CNNs for Deepfake Image Detection, in: Proceedings of the 1st International Workshop on Multimedia AI against Disinformation, 2022, pp. 52–58.
  * [104] J. Wang, Z. Wu, W. Ouyang, X. Han, J. Chen, Y.-G. Jiang, S.-N. Li, M2tr: Multi-modal multi-scale transformers for deepfake detection, in: Proceedings of the 2022 international conference on multimedia retrieval, 2022, pp. 615–623.
  * [105] M. A. Raza, K. M. Malik, I. U. Haq, Holisticdfd: Infusing spatiotemporal transformer embeddings for deepfake detection, Information Sciences (2023) 119352\.
  * [106] Y. Heo, W. Yeo, B. Kim, Deepfake detection algorithm based on improved vision transformer, Applied Intelligence 53 (2023) 7512–7527.
  * [107] H. Lin, W. Huang, W. Luo, W. Lu, Deepfake detection with multi-scale convolution and vision transformer, Digital Signal Processing 134 (2023) 103895\.
  * [108] F. Khalid, M. H. Akbar, S. Gul, Swynt: Swin y-net transformers for deepfake detection, in: 2023 International Conference on Robotics and Automation in Industry (ICRAI), 2023, pp. 1–6.  doi:10.1109/ICRAI57502.2023.10089585.
  * [109] T. Wang, H. Cheng, K. P. Chow, L. Nie, Deep convolutional pooling transformer for deepfake detection, ACM Transactions on Multimedia Computing, Communications and Applications 19 (6) (2023) 1–20.
  * [110] Real and fake face detection, https://www.kaggle.com/ciplab/real-and-fake-face-detection, accessed: 2021-06-11 (2019).
  * [111] R. Andreas, C. Davide, V. Luisa, R. Christian, T. Justus, N. Matthias, Faceforensics: A large-scale video dataset for forgery detection in human faces, CoRR abs/1803.09179.
  * [112] A. Rossler, D. Cozzolino, L. Verdoliva, C. Riess, J. Thies, M. Nießner, Faceforensics++: Learning to detect manipulated facial images, in: Proceedings of the IEEE/CVF International Conference on Computer Vision, 2019, pp. 1–11.
  * [113] L. Yuezun, Y. Xin, S. Pu, Q. Honggang, L. Siwei, Celeb-df: A large-scale challenging dataset for deepfake forensics, in: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2020, pp. 3207–3216.
  * [114] B. Dolhansky, R. Howes, B. Pflaum, N. Baram, C. Canton-Ferrer, The deepfake detection challenge (dfdc) preview dataset, ArXiv abs/1910.08854.
  * [115] N. Dufour, A. Gully, Contributing data to deepfake detection research, https://ai.googleblog.com/2019/09/contributing-data-to-deepfake-detection.html, accessed: 2023-06-12 (2019).
  * [116] T. Karras, T. Aila, S. Laine, J. Lehtinen, Progressive growing of gans for improved quality, stability, and variation, arXiv preprint arXiv:1710.10196.
  * [117] X. Tan, Y. Li, J. Liu, L. Jiang, Face liveness detection from a single image with sparse low rank bilinear discriminative model, in: European Conference on Computer Vision, Springer, 2010, pp. 504–517.
  * [118] Z. Zhang, J. Yan, S. Liu, Z. Lei, D. Yi, S. Z. Li, A face antispoofing database with diverse attacks, in: 2012 5th IAPR international conference on Biometrics (ICB), IEEE, 2012, pp. 26–31.
  * [119] S. Agarwal, H. Farid, Y. Gu, M. He, K. Nagano, H. Li, Protecting world leaders against deep fakes, in: CVPR Workshops, 2019, pp. 38–45.
  * [120] Z. Liu, P. Luo, X. Wang, X. Tang, Deep learning face attributes in the wild, in: Proceedings of International Conference on Computer Vision (ICCV), 2015, pp. 3730–3738.
  * [121] G. Haiying, K. Mark, R. Eric, L. Yooyoung, Y. Amy, D. Andrew, Z. Daniel, K. Timothee, S. Jeff, F. Jonathan, MFC datasets: Large-scale benchmark datasets for media forensic challenge evaluation, in: IEEE Winter Applications of Computer Vision Workshops (WACVW), IEEE, 2019, pp. 63–72.
  * [122] F. Yu, A. Seff, Y. Zhang, S. Song, T. Funkhouser, J. Xiao, LSUN: Construction of a Large-scale Image Dataset using Deep Learning with Humans in the Loop (2016).  arXiv:1506.03365.
  * [123] S.-Y. Wang, O. Wang, R. Zhang, A. Owens, A. A. Efros, Cnn-generated images are surprisingly easy to spot… for now, in: Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, 2020, pp. 8695–8704.
  * [124] F. Song, X. Tan, X. Liu, S. Chen, Eyes closeness detection from still images with multi-scale histograms of principal oriented gradients, Pattern Recognition 47 (9) (2014) 2825–2838.
  * [125] S. A. Khan, H. Dai, Video transformer for deepfake detection with incremental learning, 9th ACM International Conference on Multimedia.
  * [126] Y. He, B. Gan, S. Chen, Y. Zhou, G. Yin, L. Song, L. Sheng, J. Shao, Z. Liu, ForgeryNet: A Versatile Benchmark for Comprehensive Forgery Analysis, in: 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), IEEE Computer Society, Los Alamitos, CA, USA, 2021, pp. 4358–4367.  doi:10.1109/CVPR46437.2021.00434.
  * [127] I. Laptev, M. Marszalek, C. Schmid, B. Rozenfeld, Learning realistic human actions from movies, in: IEEE Conference on Computer Vision and Pattern Recognition, IEEE, 2008, pp. 1–8.
  * [128] faceswap-GAN Github, https://github.com/shaoanlu/faceswap-GAN, accessed: 2021-06-23 (2019).
  * [129] L. Yuezun, C. Ming-Ching, L. Siwei, In ictu oculi: Exposing ai created fake videos by detecting eye blinking, in: IEEE International Workshop on Information Forensics and Security (WIFS), IEEE, 2018, pp. 1–7.
  * [130] P. Korshunov, M. Sébastien, Deepfakes: a new threat to face recognition? assessment and detection, arXiv preprint arXiv:1812.08685.
  * [131] T. Justus, Z. Michael, S. Marc, T. Christian, N. Matthias, Face2face: Real-time face capture and reenactment of rgb videos, in: Proceedings of the IEEE conference on computer vision and pattern recognition, 2016, pp. 2387–2395.
  * [132] J. Liming, L. Ren, W. Wayne, Q. Chen, L. Chen Change, Deeperforensics-1.0: A large-scale dataset for real-world face forgery detection, in: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2020, pp. 2889–2898.
  * [133] C. Chen, W. Yanlin, Z. Shun, T. Yiying, Z. Kun, Facewarehouse: A 3d facial expression database for visual computing, IEEE Transactions on Visualization and Computer Graphics 20 (3) (2013) 413–425.
  * [134] V. Wesselkamp, K. Rieck, D. Arp, E. Quiring, Misleading Deep-Fake Detection with GAN Fingerprints, in: IEEE Security and Privacy Workshops (SPW), 2022, pp. 59–65.
  * [135] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly, J. Uszkoreit, N. Houlsby, An image is worth 16x16 words: Transformers for image recognition at scale (2020).  arXiv:2010.11929.
  * [136] J. Loeffler, Deepfaked voice of ceo used to steal almost $ 250,000 from company, https://interestingengineering.com/deepfaked-voice-of-ceo-used-to-steal-almost-250000-from-company, accessed: 2021-03-30 (2019).
  * [137] J. Wojewidka, The deepfake threat to face biometrics, Biometric Technology Today 2020 (2) (2020) 5–7.
  * [138] G. Ishank, P. Niladri, M. Bappaditya, Deep convolutional neural network for double-identity fingerprint detection, IEEE Sensors Letters 4 (5) (2020) 17–20.
  * [139] R. Rombach, A. Blattmann, D. Lorenz, P. Esser, B. Ommer, High-resolution image synthesis with latent diffusion models, in: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2022, pp. 10684–10695.
  * [140] J. Ho, A. Jain, P. Abbeel, Denoising diffusion probabilistic models, in: H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, H. Lin (Eds.), Advances in Neural Information Processing Systems, Vol. 33, Curran Associates, Inc., 2020, pp. 6840–6851.
URL
https://proceedings.neurips.cc/paper_files/paper/2020/file/4c5bcfec8584af0d967f1ab10179ca4b-Paper.pdf

  * [141] J. Sohl-Dickstein, E. Weiss, N. Maheswaranathan, S. Ganguli, Deep unsupervised learning using nonequilibrium thermodynamics, in: F. Bach, D. Blei (Eds.), Proceedings of the 32nd International Conference on Machine Learning, Vol. 37 of Proceedings of Machine Learning Research, PMLR, Lille, France, 2015, pp. 2256–2265.
  * [142] S. Mandelli, D. Cozzolino, E. D. Cannas, J. P. Cardenuto, D. Moreira, P. Bestagini, W. J. Scheirer, A. Rocha, L. Verdoliva, S. Tubaro, E. J. Delp, Forensic analysis of synthetically generated western blot images, IEEE Access 10 (2022) 59919–59932.  doi:10.1109/ACCESS.2022.3179116.
  * [143] Y. Jeong, D. Kim, Y. Ro, P. Kim, J. Choi, Fingerprintnet: Synthesized fingerprints for generated image detection, in: S. Avidan, G. Brostow, M. Cissé, G. M. Farinella, T. Hassner (Eds.), Computer Vision – ECCV 2022, Springer Nature Switzerland, Cham, 2022, pp. 76–94.

Leandro Aparecido Passos is graduated in Informatics, has M.Sc. and Ph.D. in
Computer Science, and worked as a post-doctorate researcher at the University
of Wolverhampton (UK). Currently, is engaged as a researcher at UNESP. Has
experience in Machine Learning, and most of his works employ graph- and
energy-based approaches, as well as more biologically plausible algorithms.

Danilo Samuel Jodas has B.Sc. and M.Sc. in Computer Science, and holds a Ph.D.
in Informatics Engineering from the Faculty of Engineering of the University
of Porto (FEUP), Portugal. He has experience in image processing and machine
learning. He is currently a postdoctoral researcher at the São Paulo State
University.

Kelton Augusto Pontara da Costa is graduated in Systems Analysis, has M.Sc.
and Ph.D. in Computer Science, and Post-doctoral in Computer Networks by
UNICAMP and UNESP. Currently works as Reseacher/Professor at UNESP and as M.Sc
and PhD advisor at UNESP. Has experience in Computer Science with emphasis in
Cybersecurity and is a senior member of the IEEE.

Luis Antonio de Souza Júnior has B.Sc. and M.Sc. in Computer Science by UNESP.
Current Ph.D. student by the ”Universidade Federal de São Carlos (UFScar)”,
Member of the Recogna group (UNESP-Bauru) and fellow member of ReMIC group
from the Technical University of Applied Sciences - Regensburg, Germany.

Douglas Rodrigues majored in Business Management and Informatics at FATEC -
Botucatu’s Faculty of Technology, SP, Brazil (2009). In 2014, he received his
M.Sc. in Computer Science from São Paulo State University (UNESP). In 2019, he
received his Ph.D. in Computer Science from the Federal University of São
Carlos (UFSCar), SP, Brazil. Currently, he is working as post-doctorate
researcher at São Paulo State University (UNESP), SP, Brazil. His interests
include machine learning, single and multi-objective optimization.

Javier Del Ser joined the Faculty of Engineering of the University of the
Basque Country to study Electrical Engineering, obtaining his combined B.S.
and M.S. degree. He became a recipient of the Fundacion de Centros
Tecnologicos Inaki Goenaga doctoral grant and received his first PhD in
Telecommunication Engineering (Cum Laude) from the University of Navarra and a
second PhD in Computational Intelligence (Summa Cum Laude, Extraordinary
Prize) from the University of Alcala. Currently he is a principal researcher
in data analytics and optimization at TECNALIA (Spain), and a part-time
lecturer at the University of the Basque Country (UPV/EHU). He is a senior
member of the IEEE, and a recipient of the Bizkaia Talent prize for his
research career.

David Camacho is currently a Full Professor at the Computer Systems
Engineering Department of the Technical University of Madrid (Spain), and the
Head of the Applied Intelligence & Data Analysis group. He received a Ph.D.
with honors in Computer Science from Universidad Carlos III de Madrid in 2001.
He has published more than 350 journals, books, and conference papers. His
expertise comprises: Big Data; Machine Learning: Clustering, Hidden Markov
Models, Classification and Deep Learning; Computational Intelligence:
Evolutionary computation, Swarm Intelligence; Pattern and Process modeling and
mining; Graph Computing and Social Mining, and Data Analysis for complex
industrial applications for companies, such as: Airbus Defence & Space, Codice
Technologies, ImpactWare, or Jobssy S.L among others.

João Paulo Papa received his B.Sc. in Information Systems and his M.Sc. and
Ph.D. in Computer Science. Had worked as a post-doctorate at UNICAMP and as a
visiting scholar at Harvard. Actually, is a Computer Science Professor at
UNESP. Also, the recipient of the Alexander von Humboldt research fellowship
and is a senior member of the IEEE.


# Bijections for Ranked Tree-Child Networks

Alessandra Caraceni
Istituto Nazionale di Alta Matematica
Unità di ricerca SNS
P.zza dei Cavalieri 7, Pisa
Italy  Michael Fuchs
Department of Mathematical Sciences
National Chengchi University
Taipei 116
Taiwan Supported by MOST under the research grant MOST-109-2115-M-004-003-MY2.
Guan-Ru Yu
Department of Mathematics
National Kaohsiung Normal University
Kaohsiung 824
Taiwan

###### Abstract

The class of ranked tree-child networks, tree-child networks arising from an
evolution process with a fixed embedding into the plane, has recently been
introduced by Bienvenu, Lambert, and Steel. These authors derived counting
results for this class. In this note, we will give bijective proofs of three
of their results. Two of our bijections answer questions raised in their
paper.

##  1 Introduction

Phylogenetic trees and networks are important discrete structures from biology
where they are used to model evolution; see [9, 10, 11]. Of these two types of
structures, phylogenetic trees are simpler and more classical but they are
less suitable to model evolutionary scenarios that involve reticulation
events. Thus, in many recent studies, they have been replaced by (the more
general) phylogenetic networks. However, the majority of the classes of
phylogenetic networks are not recursive and thus they are a poor model for
processes that evolve over time. In order to be able to model such processes,
Bienvenu et al. recently proposed the class of ranked tree-child networks; see
[1].

We recall some definitions. First, a (rooted, binary) phylogenetic network is
a simple DAG (directed acyclic graph) with a unique root of indegree $0$ and
outdegree $1$ such that all other nodes belong to one of the following types:

  * •

leaves, which are nodes with indegree $1$ and outdegree $0$; these are
bijectively labeled by the set $\\{1,\ldots,\ell\\}$ where $\ell$ is the total
number of leaves;

  * •

tree nodes, which are nodes with indegree $1$ and outdegree $2$; and

  * •

reticulation nodes, which are nodes with indegree $2$ and outdegree $1$.

A phylogenetic network is called a tree-child network if each internal (i.e.,
non-leaf) node has at least one child which is not a reticulation node. For
such a network, we call a tree node whose two children are both not
reticulation nodes a branching event and a reticulation node together with
both its parents a reticulation event; see Figure 1-(a). A ranked tree-child
network (or RTCN for short) is now a tree-child network which is drawn in such
a way that one starts with a branching event and then successively adds either
a branching event or a reticulation event until the leaves are reached; see
Figure 1-(b).

Figure 1: (a) The two types of events of a ranked tree-child network; (b) An
example of a RTCN.

The class of RTCNs has the advantage over other network classes that the
special embedding into the plane makes counting relatively straightforward.
(In contrast, few of the other classes of phylogenetic networks have so far
been counted; see, e.g., [2, 3, 4, 5, 6, 7, 8] for some recent progress.) For
instance, the following simple formula was obtained in [1] for the number
$\mathrm{RTC}_{\ell}$ of RTCNs with $\ell$ leaves:

$\mathrm{RTC}_{\ell}=\frac{\ell!(\ell-1)!^{2}}{2^{\ell-1}}.$ (1)

Curiously, the same number is the answer to the following counting problem:
find the number of ways for $\ell$ people to cross a river with a two-person
boat where the boat trips follow the pattern $2$ send, $1$ returns, $2$ send,
$1$ returns, etc; see A167484 in the OEIS. Thus, one can ask for a bijection
between RTCNs and such boat sequences; however, in Remark 2.8 in [1] it was
claimed that a natural bijection seems to be unlikely because for $\ell=3$,
$3$ out of the $6$ RTCNs contain a reticulation event and $3$ do not (see
bottom resp. top row of Figure 2) whereas all $6$ possible boat trips are
completely equivalent. Nevertheless, we will give a simple bijection in the
next section; again see Figure 2 for the correspondence between RTCNs and boat
sequences for $\ell=3$ arising from our bijection.

Figure 2: All RTCNs and their corresponding boat sequences for $\ell=3$.

Using this bijection, branching events are, e.g., mapped to the following
events of boat sequences. Assume that the $\ell$ people are ranked according
to their skill at steering the boat. Then, the number of branching events
corresponds to the number $X_{\ell}$ of return trips where the most skilled
person among those on the opposite shore takes the boat back. Since it was
proved in Corollary 2.7 in [1] that the number of branching events in a RTCN
chosen uniformly at random from all RTCNs with $\ell$ leaves satisfies a
central limit theorem, we obtain the following result.

######  Theorem 1.

For a boat sequence of $\ell$ people chosen uniformly at random from all boat
sequences, the number of times $X_{\ell}$ that the most skilled person takes
the boat back satisfies the limit law:

$\frac{X_{\ell}-\log\ell}{\sqrt{\log\ell}}\stackrel{{\scriptstyle
d}}{{\longrightarrow}}N(0,1),$

where $\stackrel{{\scriptstyle d}}{{\longrightarrow}}$ denotes convergence in
distribution and $N(0,1)$ denotes the standard normal distribution.

In fact, the number $\mathrm{RTC}_{\ell,b}$ of RTCNs with $\ell$ leaves and
$b$ branching events was counted in [1] as well:

$\mathrm{RTC}_{\ell,b}=\genfrac{[}{]}{0.0pt}{}{\ell-1}{b}\cdot\mathrm{RT}_{\ell},$

where the bracket denotes the (signless) Stirling numbers of the first kind
and $\mathrm{RT}_{\ell}=\ell!(\ell-1)!/2^{\ell-1}$ is the number of ranked
trees (i.e., RTCNs without reticulation events). Since the Stirling numbers of
the first kind count permutations with a fixed number of cycles, this result
suggests that there should be a simple bijection between RTCNs with a fixed
number of branching events and pairs consisting of permutations with a fixed
number of cycles and ranked trees. We will give such a bijection in Section 3.

Figure 3: A ranked tree $T$ (upper left corner) with $\ell=4$ leaves and all
$15$ RTCNs which contain $T$ where incoming edges of reticulation nodes which
need to be removed to obtain $T$ are indicated by arrows. (Note that one of
the RTCNs is $T$ itself.)

A final bijection discussed in this note is related to another result in [1]
which concerns containment of ranked trees in RTCNs. Here, we say that a
ranked tree $T$ is contained in a RTCN $N$, in symbols $T\sqsubset N$, if $T$
can be obtained from $N$ by choosing one of the incoming edges of each
reticulation node of $N$, removing them, and then suppressing resulting nodes
with indegree $1$ and outdegree $1$; see Figure 3.

For a fixed ranked tree $T$ with $\ell$ leaves, it was proved in [1] that

$\\#\\{N\ :\ T\sqsubset N\\}=1\cdot 3\cdot 5\cdots(2\ell-3)=:(2\ell-3)!!.$ (2)

Note that $(2\ell-3)!!$ is the number of phylogenetic trees with $\ell$ leaves
where a phylogenetic tree is a phylogenetic network without reticulation
nodes; see, e.g., Corollary 2.2.4 in [10]. Thus, one again would like to have
a simple bijection between RTCNs which contain $T$ and phylogetetic trees; see
Remark 3.7 in [1]. In the final section of this note, we will give such a
bijection.

##  2 RTCNs and boat sequences

In this section, we will describe a bijection between RTCNs with $\ell$ leaves
and boat sequences involving $\ell$ people. This will be done in three steps.
First, we will explain how to construct all RTCNs with $\ell+1$ leaves from
those with $\ell$ leaves; then, we will do the same for boat sequences; and
finally we will synchronize these two constructions to get the desired
bijection.

### Recursive construction of RTCNs.

Here, we give a top-down construction which (uniquely) produces all RTCNs with
$\ell+1$ leaves. A similar construction was described in [1] where the authors
used the concept of decorated RTCNs. We will sidestep this concept which gives
a (slightly) simpler construction.

Figure 4: The two operations (O-i) and (O-ii) in the recursive construction of
RTCNs.

Assume we have a given RTCN with $\ell$ leaves. Then, we perform either one of
the following two operations (see Figure 4 for examples).

(O-i)

Pick two labels $a,b$ from the set $\\{1,\ldots,\ell+1\\}$, remove the label
$\ell$ from the RTCN and attach to its leaf two children with labels $a,b$.
Finally, relabel all the other leaves of the RTCN in an order-consistent way
with the remaining labels from $\\{1,\ldots,\ell+1\\}\setminus\\{a,b\\}$.

(O-ii)

Pick two labels $a<b$ from $\\{1,\ldots,\ell+1\\}$ and a label $c$ from
$\\{1,\ldots,\ell+1\\}\setminus\\{a,b\\}$. Next, find the relative ranks, say
$a^{\prime}<b^{\prime}$, of $a<b$ in $\\{1,\ldots,\ell+1\\}\setminus\\{c\\}$.
Remove $a^{\prime},b^{\prime}$ from the RTCN and attach a reticulation event
to their leaves with the children corresponding to the leaf which had the
label $a^{\prime}$ being a leaf with label $a$ and the reticulation vertex,
the children corresponding to the leaf which had the label $b^{\prime}$ being
a leaf with label $b$ and the (same) reticulation vertex and the child of the
reticulation vertex being a leaf with label $c$. Finally, relabel all the
other leaves of the RTCN in an order-consistent way with the labels from
$\\{1,\ldots,\ell+1\\}\setminus\\{a,b,c\\}$.

Since both of these operations are reversible, we have the following result.

######  Proposition 1.

Starting from all RTCNs with $\ell$ leaves and performing for each of them all
the operations above gives (exactly once) all the RTCNs with $\ell+1$ leaves.

Moreover, this construction also immediately gives (1).

######  Corollary 1.

We have

$\mathrm{RTC}_{\ell}=\frac{\ell!(\ell-1)!^{2}}{2^{\ell-1}}.$

###### Proof.

The number of different ways to perform (i) and (ii) above is

$\binom{\ell+1}{2}+\binom{\ell+1}{2}(\ell-1)=\frac{(\ell+1)\ell^{2}}{2}.$

Thus,

$\mathrm{RTC}_{\ell}=\prod_{j=1}^{\ell-1}\frac{(\ell+1)\ell^{2}}{2}=\frac{\ell!(\ell-1)!^{2}}{2^{\ell-1}}$

which proves the claim.

Figure 5: An example of a boat sequence involving $5$ people. Top: the people
on both sides of the shores after each step. Bottom: the representation of the
boat sequence as array and the array of rankings obtained from it by applying
the map $r$.

### Recursive construction of boat sequences.

Here, we explain how all boat sequences involving $\ell+1$ people can be
constructed from those involving $\ell$ people. (Note that this reveals a
recursive structure inherent to boat sequences that was not considered in
[1].)

First, note that a boat sequence involving $\ell$ people can be represented by
an array with $2$ rows where the first row has $\ell-1$ entries and the second
has $\ell-2$ entries, namely, the first row contains the set of numbers of the
people sent in the $i$-th step and the second row contains the singleton of
the number of the person who returned in the $i$-th step; see bottom left
array in Figure 5 for an example.

Now, each such array can be mapped to a corresponding array where the numbers
are replaced by the relative ranks of the people within the group on their
shore, e.g., if $\\{2,5\\}$ are sent with $\\{2,3,5,6\\}$ at the same shore,
then $\\{2,5\\}$ is replaced by $\\{1,3\\}$. Call the resulting map $r$; see
bottom of Figure 5.

Note that the map $r$ is clearly a bijection from the above arrays
representing boat sequences to arrays where in the first row, we have a subset
of size $2$ of $\\{1,\ldots,\ell\\}$, followed by a subset of size $2$ of
$\\{1,\ldots,\ell-1\\}$, etc. until the set $\\{1,2\\}$ and in the second row,
we have a subset of size $1$ of $\\{1,2\\}$, followed by a subset of size $1$
of $\\{1,2,3\\}$, etc. until a subset of size $1$ of $\\{1,\ldots,\ell-1\\}$.

Now, we apply the following operations on the latter arrays: we shift all
entries of the first row to the right by one position, add a subset of size
$2$ of $\\{1,\ldots,\ell+1\\}$ in the (now empty) first position and add a
subset of size $1$ of $\\{1,\ldots,\ell\\}$ at the end of the second row; see
the downwards arrow in Figure 6.

Finally, by using the inverse of $r$, we obtain an array for a boat sequence
involving $\ell+1$ people; see the bottom left array in Figure 6.

Figure 6: A boat sequence with $6$ people constructed from the boat sequence
with $5$ people from Figure 5.

Since the above process is reversible, we obtain the following result.

######  Proposition 2.

Starting from a boat sequence involving $\ell$ people and using the map $r$,
all possible operations above, and the inverse of $r$, we obtain (exactly
once) all boat sequences involving $\ell+1$ people.

Figure 7: A RTCN (top left corner) with $\ell=4$ and the process of
constructing its image under the bijection. Top: the two steps of reducing the
RTCN to the one with $\ell=2$. Right-most column: The boat sequence
corresponding to the initial case and its array of rankings. Bottom: the
process of extending the array of rankings. Left-most column: applying
$r^{-1}$ gives the desired result (middle).

### Synchronization of the two constructions.

We will now explain how to synchronize the constructions from the above two
paragraphs to get a bijection between RTCNs and boat sequences. This bijection
is defined recursively.

Assume we have given a RTCN on $\ell+1$ leaves. Reverse the recursive
construction from Proposition 1 to obtain a RTCN on $\ell$ leaves. By
induction hypothesis, this RTCN is mapped on a boat sequence which is
represented by an array as described in the previous paragraph. We apply the
map $r$ to this array. Now, depending on which of the two operations was used
in Proposition 1 to construct the RTCN on $\ell+1$ leaves from that of $\ell$
leaves, we do the following to the array of ranks.

(i)

If Operation (O-i) was used, then move all the pairs from the first row by one
position and add $\\{a,b\\}$ as the first entry. Also, add $\\{\ell\\}$ at the
end of the second row.

(ii)

If Operation (O-ii) was used, then again move all the pairs from the first row
by one position and add $\\{a,b\\}$ as the first entry. Add the relative rank
of $c$ in $\\{1,\ldots,\ell+1\\}\setminus\\{a,b\\}$ to the end of the second
row.

Finally, apply the inverse of $r$ to the above array to obtain the desired
boat sequence.

More generally, in order to get the corresponding boat sequence for a RTCN on
$\ell$ leaves, we first have to reduce it to the RTCN on $2$ leaves by
applying Proposition 1 $\ell-2$ times and retain the operations from the first
paragraph for each step. Then, we can start from the (trivial) boat sequence
and use the above procedure $\ell-2$ times to construct the corresponding boat
sequence; see Figure 7 for an example.

Also, from the above, it is clear that branching events correspond to steps
where the person with the maximal rank was picked for the return trip (or,
using the language introduced just before Theorem 1, the most skilled person
on the opposite shore). This proves Theorem 1 from the introduction.

##  3 Branching events, permutations and ranked binary trees

Figure 8:  Left: a RTCN with $\ell=6$ leaves and $k=3$ reticulation events;
the profile equals $(q_{i})_{i=1}^{5}=(1,0,1,1,0)$ and the sequence of
positions of reticulation events equals $(a_{i})_{i=1}^{3}=(1,3,4)$. Right:
the same RTCN redrawn as described in Section 3.

In this section, we describe an explicit bijection between the set of RTCNs
with $\ell$ leaves and $k$ reticulation events (equivalently, with $\ell-1-k$
branching events) and the set of pairs $(T,\sigma)$ where $T$ is a ranked
binary tree with $\ell$ leaves and $\sigma$ is a permutation of
$\\{1,\ldots,\ell-1\\}$ consisting of $\ell-1-k$ disjoint cycles.

### From a RTCN to a ranked binary tree and permutation.

Given a RTCN with $\ell$ leaves labeled $1$ to $\ell$, define its profile as
the sequence $(q_{i})_{i=1}^{\ell-1}\in\\{0,1\\}^{\ell-1}$ where $q_{i}=0$ if
and only if the $i$-th event from the bottom is a branching event (see left of
Figure 8). Note that we necessarily have $q_{\ell-1}=0$, as only two lineages
(i.e., vertical edges) are available to merge for the last event. Suppose
$\sum_{i=1}^{\ell-1}q_{i}=k$, that is, that the RTCN under consideration has
$k$ reticulation events, and let $a_{1}<a_{2}<\ldots<a_{k}$ be the indices
$i\in\\{1,\ldots,\ell-2\\}$ such that $q_{i}=1$, corresponding to the
reticulation events in question (note that the reticulation event $a_{i}$
happens at time $\ell-a_{i}$, with the notation from Figure 1-(b)).

Next, note that we can consider lineages above (and below) each event to be
naturally ordered as follows. Assuming that lineages just below event $i$ are
labeled $1$ to $\ell-i+1$ and that the event is a branching event, label the
$\ell-i$ lineages just above the event with the integers $1$ to $\ell-i$ so
that their order reflects the order after the branching event, with the parent
lineage identified with its child whose label is smaller. Similarly, assuming
$i$ is a reticulation event, order the lineages present just above the event
$i$ consistently with their order after the event (ignoring the hybrid lineage
resulting from the reticulation event). This is by no means the only possible
convention (other conventions would yield equivalent bijections), but we may
use it to determine the left-to-right order of lineages when the RTCN is drawn
in the plane (so that we can say that the $\ell-i$ lineages above event $i$
are labeled “left-to-right” with the numbers $1$ to $\ell-i$). The planar
embedding induced by this convention is depicted on the right of Figure 8: the
RTCN on the left is redrawn on the right with lineages ordered left to right
according to their current labels, which are explicitly indicated above and
below each event; in the representation on the right, parent lineages of
reticulation events are drawn directly above the respective non-hybrid child
lineages.

In order to obtain a ranked binary tree, we will replace each of the $k$
reticulation events of the RTCN with a branching event; at the same time, we
shall keep track of additional information allowing the recovery of the
original reticulation event.

$L_{1}$$L_{3}$$L_{2}$$l_{1}$$l_{2}$$L_{1}$$L_{3}$$L_{2}$$l_{1}^{\prime}$$l_{2}^{\prime}$
Figure 9: A reticulation event is replaced by a branching event: the hybrid
lineage $L_{3}$ becomes the future of the former rightmost parent lineage,
which is no longer involved in the event. Note that the number $L_{3}$ need
not be between $L_{1}$ and $L_{2}$: for examples where it is not, see the
second and third transformations performed in Figure 10. Figure 10: From the
RTCN displayed to the far left to its corresponding ranked binary tree
obtained on the right, with its accompanying permutation
$\sigma=(a_{1},a_{1}+b_{1})(a_{2},a_{2}+b_{2})(a_{3},a_{3}+b_{3})=(1,4)(3,5)(4,5)=(1,5,3,4)(2)$,
which is the product of $\ell-1-k=6-1-3=2$ disjoint cycles. The three
subsequent steps turn reticulation events 1, 3, 4 into branching events. The
values of $(L_{1},L_{2},L_{3},l_{1},l_{2},l_{1}^{\prime},l_{2}^{\prime})$ are
$(1,5,4,1,4,1,4)$ for the first step, $(1,2,4,1,2,1,3)$ for the second, and
$(2,3,1,1,2,2,1)$ for the third.

Build the corresponding ranked binary tree to our RTCN by considering in turn
the events $a_{1},\ldots,a_{k}$. The result of the reticulation event $a_{1}$
is given by two lineages $L_{1}<L_{2}$, labeled $l_{1}<l_{2}$ _above_ the
reticulation event, and a third hybrid lineage $L_{3}$; replace this by a
branching event that yields $L_{1},L_{2}$ from a single parent lineage $P$ and
leaves $L_{3}$ intact. Some convention is needed in order to match lineages
$P,L_{3}$ to lineages $l_{1},l_{2}$; we identify $P$ with $l_{1}$ and assign
the evolution of the hybrid lineage $L_{3}$ to the lineage $l_{2}$ (Figure 9).
Labels assigned to lineages below event $a_{1}$ are unchanged by this
procedure, but labels above the event are recomputed according to the rules we
explained previously. In particular, labels immediately above the event
$a_{1}$ range between $1$ and $\ell-a_{1}$; the lineage that used to be
labeled $l_{1}$ is now labeled $l_{1}^{\prime}$ and the lineage that used to
be labeled $l_{2}$ is now labeled $l_{2}^{\prime}$ where the values of
$l_{1}^{\prime},l_{2}^{\prime}$ depend on $L_{1},L_{2},L_{3}$: if
$L_{3}<L_{1}$, then $l_{1}^{\prime}=L_{1}=l_{1}+1$ and $l_{2}^{\prime}=L_{3}$;
if $L_{2}<L_{3}$, then $l_{1}^{\prime}=L_{1}=l_{1}$ and
$l_{2}^{\prime}=L_{3}-1$; if $L_{1}<L_{3}<L_{2}$, then
$l_{1}^{\prime}=L_{1}=l_{1}$ and $l_{2}^{\prime}=L_{3}$.

The result of this operation is a RTCN $T_{1}$ with $k-1$ reticulation events.
In order to be able to reinstate the original reticulation, it is enough to
keep track of $a_{1}$ (identifying the branching event to be turned back into
a reticulation event) and a number $b_{1}$ that identifies the lineage to turn
back into the original hybrid. Note that the label $l_{2}^{\prime}$, for
example, would allow the recovery of the original RTCN; $l_{2}^{\prime}$ is an
integer between $1$ and $\ell-a_{1}$, but cannot take all values in the range
independently of $T_{1}$, as it cannot be equal to $l_{1}^{\prime}$, that is,
to the label of the parent lineage of the branching event $a_{1}$. We
therefore define the number $b_{1}$ as $l_{2}^{\prime}$ if
$l_{2}^{\prime}<l_{1}^{\prime}$ and $l_{2}^{\prime}-1$ otherwise. This way, we
have $1\leq b_{1}\leq\ell-1-a_{1}$; since $l_{1}^{\prime}$ can be determined
from $T_{1}$, the pair $(a_{1},b_{1})$ is enough to recover $l_{2}^{\prime}$
and thus the original RTCN (as we will further discuss later).

We repeat this operation for each reticulation to obtain a final ranked binary
tree $T_{k}$ and a sequence $(a_{1},b_{1}),\ldots,(a_{k},b_{k})$ where $1\leq
b_{i}\leq\ell-1-a_{i}$: see Figure 10 for an example.

This sequence of $k$ pairs can be naturally encoded by the permutation
$\sigma_{k}=(a_{1},b_{1}+a_{1})\cdot(a_{2},b_{2}+a_{2})\cdot\ldots\cdot(a_{k},a_{k}+b_{k})$
in the symmetric group $\mathcal{S}_{\ell-1}$ (where we adopt the convention
that composition of permutations is obtained via multiplication from the
right); this is the product of $k$ transpositions such that
$a_{1}<\ldots<a_{k}$ and $b_{i}+a_{i}>a_{i}$. The latter condition is actually
equivalent to the permutation being a product of $\ell-1-k$ disjoint cycles,
as clarified by the following lemma:

######  Lemma 1.

For all integers $n>k>0$, a permutation $\sigma\in\mathcal{S}_{n}$ is the
product of $n-k$ disjoint cycles if and only if it can be expressed as a
product of transpositions of the form
$(x_{1},y_{1})\cdot\ldots\cdot(x_{k},y_{k})$ where $0<x_{1}<\ldots<x_{k}<n$
and $x_{i}<y_{i}\leq n$ for $1\leq i\leq k$; moreover, if such an expression
for $\sigma$ exists, then it is unique.

###### Proof.

First of all, given a positive integer $n$, we show the fact that any product
of $k<n$ transpositions with the properties described in the statement is the
product of $n-k$ disjoint cycles by induction on $k$. Given a positive integer
$i<n$, consider a permutation $\tau\in\mathcal{S}_{n}$ of the form
$\tau=(\alpha_{1},\beta_{1})\cdot\ldots\cdot(\alpha_{i-1},\beta_{i-1})$ where
$\alpha_{1}<\alpha_{2}<\ldots<\alpha_{i-1}$ and $\alpha_{j}<\beta_{j}$ for
$1\leq j\leq i-1$; assume that $\tau$ has $n-i+1$ cycles and that each $j$ in
$\\{1,\ldots,n\\}\setminus\\{\alpha_{1},\ldots,\alpha_{i-1}\\}$ is the maximum
element of the cycle it belongs to in the factorisation of $\tau$ as a product
of disjoint cycles. Consider any permutation of the form
$\tau\cdot(\alpha_{i},\beta_{i})$ where
$n\geq\beta_{i}>\alpha_{i}>\alpha_{i-1}$. The elements $\alpha_{i},\beta_{i}$
must belong to separate cycles in $\tau$ and each must be the maximum of its
own cycle, as neither can be in $\\{\alpha_{1},\ldots,\alpha_{i-1}\\}$. Denote
by $c_{\alpha}$ the cycle of $\tau$ containing $\alpha_{i}$ and by $c_{\beta}$
the one containing $\beta_{i}$; the disjoint cycles of the permutation
$\tau\cdot(\alpha_{i},\beta_{i})$ are those of $\tau$, with the cycles
$c_{\alpha}$ and $c_{\beta}$ merged into one.

Note that the property that elements not in
$\\{\alpha_{1},\ldots,\alpha_{i}\\}$ are maximal in their cycles holds for
$\tau\cdot(\alpha_{i},\beta_{i})$. Indeed, if some element is not in
$\\{\alpha_{1},\ldots,\alpha_{i-1}\\}$ and does not belong to $c_{\alpha}$ or
$c_{\beta}$, then it is maximal in its cycle in $\tau$, and thus it is maximal
in the same cycle of $\tau\cdot(\alpha_{i},\beta_{i})$. The elements
$\alpha_{i}$ and $\beta_{i}$, which do not appear in the list
$\\{\alpha_{1},\ldots,\alpha_{i-1}\\}$, are the maximums of the cycles
$c_{\alpha}$ and $c_{\beta}$, respectively. It follows that the element
$\beta_{i}$ is maximal in its cycle of $\tau\cdot(\alpha_{i},\beta_{i})$,
which is the union of $c_{\alpha}$ and $c_{\beta}$. Finally, suppose by
contradiction that an element of the new cycle other than $\beta_{i}$ belongs
to $\\{1,\ldots,n\\}\setminus\\{\alpha_{1},\ldots,\alpha_{i}\\}$; this would
imply that it was maximal in its cycle in $\tau$, and therefore in
$c_{\alpha}$ or $c_{\beta}$; it would thus belong to
$\\{\beta_{i},\alpha_{i}\\}$, which we have excluded.

It follows from the fact that the identity of $\mathcal{S}_{n}$ (the product
of zero transpositions) consists of $n$ disjoint cycles of length one (and is
thus such that each element in $\\{1,\ldots,n\\}$ is maximal in its cycle)
that any permutation of the form described in the statement is the product of
$n-k$ disjoint cycles.

Conversely, consider a permutation $\sigma\in\mathcal{S}_{n}$ made up of
$n-k<n$ disjoint cycles; let us determine positive integers
$x_{1},\ldots,x_{k},y_{1},\ldots,y_{k}$ between $1$ and $n$ such that
$x_{1}<\ldots<x_{k}$, $x_{i}<y_{i}$ for $1\leq i\leq k$, and
$\sigma=(x_{1},y_{1})\cdot\ldots\cdot(x_{k},y_{k})$. The element $x_{1}$ must
necessarily be the smallest one that is not fixed by $\sigma$. The element
$y_{1}$ must be such that $\sigma(y_{1})=x_{1}$, as $x_{1}$ is not moved by
any of the other transpositions. Consequently, we have
$y_{1}=\sigma^{-1}(x_{1})>x_{1}$. We can repeat this procedure recursively on
the permutation $(x_{1},\sigma^{-1}(x_{1}))\cdot\sigma$ (which fixes all
elements up to and including $x_{1}$) to obtain the subsequent transpositions
$(x_{2},y_{2}),\ldots,(x_{k},y_{k})$.

As a result, from our initial RTCN we have constructed a pair given by a
ranked binary tree and a permutation in $\mathcal{S}_{\ell-1}$ which, by
applying Lemma 1 with $n=\ell-1$, we find to be a product of as many disjoint
cycles as the number of branching events in the original RTCN (that is,
$\ell-1-k$). We have already sketched how we can revert each change made to
recover the original RTCN, but we give a more complete description of the
inverse construction below.

### From a ranked binary tree and a permutation to a RTCN.

We are given a ranked binary tree with $\ell$ labeled leaves and a permutation
$\sigma$ in $\mathcal{S}_{\ell-1}$ with $\ell-1-k$ cycles.

First of all, by Lemma 1 we can express $\sigma$ in a unique way as a product
of transpositions of the form previously described, as
$(x_{1},y_{1})\cdot\ldots\cdot(x_{k},y_{k})$ with $0<x_{1}<\ldots<x_{k}$ and
$x_{i}<y_{i}\leq n$ for $1\leq i\leq k$. We then obtain our pairs
$(a_{i},b_{i})_{i=1}^{k}$ as $a_{i}=x_{i}$, $b_{i}=y_{i}-x_{i}$.

All that is left to do is replace the branching events $a_{k},\ldots,a_{1}$ in
our ranked binary tree (numbered from the bottom) by reticulation events. We
can still number our lineages from $1$ to $\ell-i$ above branching event $i$
(again, think of the order induced by assigning to the parent the label of the
smaller child).

For $i=k,\ldots,1$ in turn, consider lineages $1$ to $\ell-a_{i}$ right above
branching event $a_{i}$ and let $l$ be the label assigned to the parent of the
branching event $a_{i}$; pick the past of lineage $b_{i}+s$ where $s=1$ if
$b_{i}\geq l$ and $s=0$ otherwise, to become the past of the larger child
issued from the branching event (while the past of the branching event becomes
the past of the smaller child), and make the future of lineage $b_{i}+s$ into
a hybridised version of the two lineages involved in the branching event.

This operation yields a RTCN and is precisely the inverse of the one
previously described (see again Figure 10 where one can follow the steps
backwards to recover the RTCN from the final ranked binary tree).

##  4 Ranked tree containment and phylogenetic trees

In this final section, we give a bijection between the set of RTCNs which
contain a fixed ranked tree and the set of phylogenetic trees; see the last
two paragraphs of Section 1.

We first recall how all RTCNs which contain a fixed ranked tree $T$ are
constructed from $T$; see [1] where this was used to prove (2). Starting from
the leaves and moving back in time, for every branching event of $T$ a
decision is taken whether or not the branching event is turned into a
reticulation event and if yes, which of the (future) lineages not in the
branching event is connected with which of the (future) lineages from the
branching event; see Figure 11-(b) for an example. We will call the resulting
RTCN $N$ and will directly translate each step in the above process of
building $N$ from $T$ into a corresponding step for building a phylogenetic
tree (time will, however, be reversed).

Figure 11: (a) A ranked tree $T$ on $6$ leaves which is redrawn such that the
leaf labels are in increasing order; (b) A RTCN $N$ containing the ranked
tree.

In order to describe this, we first draw the ranked tree $T$ so that all the
leaves are in increasing order when read from left to right; see Figure
11-(a). Then, we consider the resulting $N$ (with the same order of the
leaves). Now, starting from a tree consisting of a root with one child labeled
by $1$, we build the (rooted) tree $\tau$ with leaf labeled by $1,\ldots,\ell$
and internal nodes labeled by $\overline{1},\ldots,\overline{\ell-1}$ where
$\ell$ is the number of labels of $T$ and we assume that
$1<\cdots<\ell<\overline{1}<\cdots<\overline{\ell-1}$, by processing the
events from $N$ top-down. More precisely, for the $k$-th event in $N$, we do
the following:

(a)

If the $k$-th event is a branching event, we insert a node with label
$\overline{k}$ into the root edge of $\tau$ and attach to this node a leaf
with label $k+1$;

(b)

If the $k$-th event is a reticulation event that was created from the $k$-th
branching event of $T$ by connecting the $i$-th (future) lineage (not counting
the lineages of the $k$-th branching event), then, we insert a node with label
$\overline{k}$ into one of the edges to the children of the internal node with
label $\overline{i}$ of $\tau$ where the child with the smaller (larger) label
is chosen depending on whether the left or the right lineage of the $k$-th
branching event of $T$ was used to form the reticulation event; moreover, we
again attach a leaf with label $k+1$ to the inserted node.

See Figure 12 for a visualization of the the above construction for the RTCN
from Figure 11-(b).

Figure 12: The rooted labeled tree constructed from the RTCN from Figure
11-(b) which contains the ranked tree from Figure 11-(a).

Next, we remove the labels of all international nodes and the root edge of
$\tau$. The resulting tree is a phylogenetic tree; see the tree on the right
of Figure 13. This tree is the image of $N$.

Figure 13: The image of the RTCN from Figure 11-(b) under the bijection.

Finally, it is not hard to see that the above construction is reversible:
e.g., if the phylogenetic tree on the right of Figure 13 is given, find the
largest label ($5$); its parent will have label $\overline{4}$. Then, remove
the largest label, the parent label and the edge which joins them. Continue
until all internal nodes have received a label (where the number of the label
is decreased by $1$ in every step). This gives the right-most tree in Figure
12 which unambiguously encodes the whole tree construction process from Figure
12. Clearly, this process can be used to re-construct $N$.

## Acknowledgments

We thank François Bienvenu for putting us into contact. Moreover, we thank the
two anonymous referees for a careful reading. The second author acknowledges
financial support by the Ministry of Science and Technology, Taiwan under the
research grant MOST-109-2115-M004-003-MY2; the third author was partially
supported by the same funding agency under the grant
MOST-110-2115-M-017-003-MY3.

## References

  * [1] F. Bienvenu, A. Lambert, M. Steel. Combinatorial and stochastic properties of ranked tree-child networks, Random Struct. Algor., in press. https://doi.org/10.1002/rsa.21048
  * [2] M. Bouvel, P. Gambette, M. Mansouri (2020). Counting phylogenetic networks of level 1 and 2, J. Math. Biol., 81:6-7, 1357–1395.
  * [3] C. McDiarmid, C. Semple, D. Welsh (2015). Counting phylogenetic networks, Ann. Comb., 19:1, 205–224.
  * [4] M. Fuchs, B. Gittenberger, M. Mansouri (2019). Counting phylogenetic networks with few reticulation vertices: tree-child and normal networks, Australas. J. Combin., 73, 385–423.
  * [5] M. Fuchs, B. Gittenberger, M. Mansouri (2021). Counting phylogenetic networks with few reticulation vertices: exact enumeration and corrections, Australas. J. Combin., 82:2, 257–282.
  * [6] M. Fuchs, E.-Y. Huang, G.-R. Yu. Counting phylogenetic networks with few reticulation vertices: a second approach, arXiv:2104.07842.
  * [7] M. Fuchs, G.-R. Yu, L. Zhang (2021). On the asymptotic growth of the number of tree-child networks, European J. Combin., 93, 103278, 20pp.
  * [8] M. Fuchs, G.-R. Yu, L. Zhang. Asymptotic enumeration and distributional properties of galled networks, arXiv:2010.13324.
  * [9] D. H. Huson, R. Rupp, C. Scornavacca. Phylogenetic Networks: Concepts, Algorithms and Applications, Cambridge University Press, 1st edition, 2010.
  * [10] C. Semple and M. Steel. Phylogenetics, Oxford University Press, Oxford, 2003.
  * [11] M. Steel. Phylogeny—Discrete and Random Processes in Evolution, CBMS-NSF Regional Conference Series in Applied Mathematics, 89, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2016.