Article
Mathematics, Applied
Jun Gao, Hongliang Lu, Jie Ma, Xingxing Yu
Summary: Researchers proposed a rainbow version of the Erdos matching conjecture and proved its validity for n>=n(0) and k=3. They transformed the problem into a matching problem on a special hypergraph and utilized various techniques to solve it.
SCIENCE CHINA-MATHEMATICS
(2022)
Article
Mathematics
Hongliang Lu, Xingxing Yu, Xiaofan Yuan
Summary: The study presents a significant theorem regarding 3-uniform hypergraphs and transforms the rainbow matching problem into a perfect matching problem in a special class of uniform hypergraphs.
JOURNAL OF COMBINATORIAL THEORY SERIES A
(2021)
Article
Multidisciplinary Sciences
Ning Zhao, Haixing Zhao, Yinkui Li
Summary: This paper investigates a method for measuring the vulnerability of linear hypergraphs, which is the rupture degree of graphs. The bounds of the rupture degrees of k-uniform linear hypergraphs are discussed. Additionally, a recursive algorithm for computing the rupture degree of k-uniform hypertrees is proposed.
Article
Mathematics, Applied
Hongliang Lu, Xingxing Yu, Xiaofan Yuan
Summary: In this paper, we prove the existence of a matching of size m + 1 for a hypergraph H under certain conditions. This result tightens the bound on delta(l)(H) for near perfect matchings, and also implies results on perfect matchings in 3-uniform hypergraphs in specific cases.
SIAM JOURNAL ON DISCRETE MATHEMATICS
(2021)
Article
Multidisciplinary Sciences
Sakina Ashraf, Muhammad Imran, Syed Ahtsham Ul Haq Bokhary, Shehnaz Akhter
Summary: Topological invariants, such as Wiener index, degree distance index, and Gutman index, are numerical parameters that indicate the topology of graphs or hypergraphs. This paper focuses on calculating these indices for certain composite hypergraphs and applies the results to sunflower hypergraphs and linear uniform hyper-paths.
Article
Computer Science, Artificial Intelligence
Giulia Palma, Andrea Frosini, Simone Rinaldi
Summary: This research discusses restricting and designing algorithms for testing the graphical properties of degree sequences in polynomial time. A combinatorial characterization spanning two sequences is provided to reconstruct related 3-uniform hypergraphs. The results are likely easily generalized to k >= 4 and other families of degree sequences with simple characterization.
JOURNAL OF MATHEMATICAL IMAGING AND VISION
(2022)
Article
Mathematics, Applied
Ailian Chen, Liping Zhang
Summary: A graph has Hamiltonicity if it contains a cycle that covers every vertex. Hamiltonicity is a classical problem in graph theory. In 1952, Dirac proved that an n-vertex graph with minimum degree at least n/2 has Hamiltonicity. In 2012, Lee and Sudakov proved that for a random graph with minimum degree (1/2 + o(1))np and p >> log n/n, each subgraph with n vertices almost surely has Hamiltonicity. In this paper, we extend Dirac's theorem to random 3-uniform hypergraphs and prove that if p >> log n/n(2), then almost surely every subgraph of H-3(n, p) with minimum degree (1/4 + o(1))(n/2) p has Berge Hamiltonicity. The values log n/n(2) and constant 1/4 are both optimal.
Article
Mathematics, Applied
Lu Hongliang, Wang Yan, Yu Xingxing
Summary: This article proves the existence of a rainbow matching for subsets F-i that satisfy certain conditions for large integers n. This result generalizes a previous study on perfect matchings in 4-uniform hypergraphs.
SIAM JOURNAL ON DISCRETE MATHEMATICS
(2022)
Article
Mathematics
Hiep Han, Jie Han, Yi Zhao
Summary: For any even integer k greater than 6, a strict minimum degree condition is identified to ensure the existence of a Hamilton (k/2)-cycle in every k-uniform hypergraph on n vertices. Our result strengthens previous findings when n is an element of kN, aligning with conditions for perfect matchings proposed by other researchers.
JOURNAL OF COMBINATORIAL THEORY SERIES B
(2022)
Article
Mathematics, Applied
Rui Sun, Wen-Huan Wang, Zhen-Yu Ni
Summary: In this study, the maximal spectral radii of three types of hypergraphs were determined by using techniques of transformations and constructing incidence matrices. These hypergraphs include the k-uniform connected linear and nonlinear unicyclic hypergraphs having perfect matchings with n vertices, where n >= k(k-1) and k >= 3.
Article
Engineering, Multidisciplinary
Juyi Li, Xiaoqun Wu, Su Zhong, Ruguo Fan, Jie Hu, Jinhu Lu
Summary: This paper introduces the use of hypergraphs and game theory to study the investment environment. The results obtained from empirical analysis provide meaningful insights for corporate decision-making and government regulation.
IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING
(2023)
Article
Mathematics, Applied
Mingyang Guo, Hongliang Lu, Dingjia Mao
Summary: In this paper, we prove a conjecture proposed by Frankl and Kupavskii, which states that when k = 3 and n is sufficiently large, there exists a conclusion that supports their conjecture.
SIAM JOURNAL ON DISCRETE MATHEMATICS
(2022)
Article
Computer Science, Theory & Methods
Andrea Frosini, Christophe Picouleau, Simone Rinaldi
Summary: The study of degree sequences of k-uniform hypergraphs has long been an open problem, with the case of k > 2 recently proven to be NP-complete. Necessary or sufficient conditions for a sequence to be k-graphic are found in the literature. This paper introduces new conditions for k-uniform and (almost) regular hypergraphs and proves sufficient conditions for k = 3.
THEORETICAL COMPUTER SCIENCE
(2021)
Article
Computer Science, Theory & Methods
Catherine Greenhill, Mikhail Isaev, Tamas Makai, Brendan D. McKay
Summary: In this article, we present an asymptotic enumeration formula for the number of simple r-uniform hypergraphs with a given degree sequence, when the number of edges is sufficiently large. We also find a solution to the system of equations and give an explicit asymptotic formula when the degree sequence is close to regular. Furthermore, we compare the degree sequence of a random r-uniform hypergraph with a given number of edges to certain models involving sequences of binomial or hypergeometric random variables conditioned on their sum.
COMBINATORICS PROBABILITY & COMPUTING
(2022)
Article
Mathematics
Guorong Gao, An Chang, Qi Sun
Summary: This paper introduces the concept of linear r-uniform hypergraphs and linear Turan numbers, discusses linear k-cycle hypergraphs, and further studies and proves ex(3)(lin)(n, C-5) based on existing research.
DISCRETE MATHEMATICS
(2023)
Article
Mathematics
Niraj Khare, Nishali Mehta, Naushad Puliyambalath
EUROPEAN JOURNAL OF COMBINATORICS
(2015)
Article
Mathematics
Niranjan Balachandran, Niraj Khare
DISCRETE MATHEMATICS
(2009)
Article
Mathematics, Applied
Niraj Khare, Rudolph Lorentz, Catherine Huafei Yan
SCIENCE CHINA-MATHEMATICS
(2014)
Article
Mathematics, Applied
Niraj Khare, Rudolph Lorentz, Catherine H. Yan
JOURNAL OF COMBINATORICS
(2017)
Article
Mathematics
Weijun Fang, Jiejing Wen, Fang-Wei Fu
Summary: This paper proposes a sufficient condition to ensure that a Hermitian self-orthogonal GRS code is still a Hermitian self-orthogonal code. Based on this, a new general construction of infinitely families of quantum MDS codes is presented, and two new constructions of quantum MDS codes with flexible parameters are given using the trace function and norm function over finite fields. The constructed quantum MDS codes have different lengths from previous known results, and the minimum distances of all the q-ary quantum MDS codes are larger than q/2 + 1.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Hoa T. Bui, Guillermo Pineda-Villavicencio, Julien Ugon
Summary: The paper examines the linkedness of the graphs of cubical polytopes and proves that every cubical d-polytope has [d/2] and strong [d/2] linkedness, for every d = 3. These results are optimal for this class of polytopes.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Julia Carrigan, Isaiah Hollars, Eric Rowland
Summary: Two words p and q are avoided by the same number of length-n words, for all n, precisely when p and q have the same set of border lengths. Previous proofs of this theorem use generating functions but do not provide an explicit bijection. We give a bijective proof for all pairs p, q that have the same set of proper borders, establishing a natural bijection from the set of words avoiding p to the set of words avoiding q.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Luke Nelson, Kevin Treat
Summary: We define a poset called the Outer Tamari poset, which is shown to be isomorphic to a subposet of the Tamari lattice introduced by Pallo (1986) and further studied as the Comb poset by Csar, Sengupta, and Suksompong (2014). By using the Outer Tamari poset, we develop recursive formulas for the number of triangulations of the 3-dimensional cyclic polytopes. These triangulations can be considered as elements of both the higher Stasheff-Tamari orders in dimension three and the Tamari Block lattices defined in a previous article. Therefore, our work here can be seen as constructing recursive enumerations of these posets.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Nicholas A. Loehr, Gregory S. Warrington
Summary: This study explores variants of chromatic symmetric functions for rooted graphs and investigates the combinatorial identities and recursions satisfied by these rooted chromatic polynomials. It proves the irreducibility of Stanley's polynomial under certain conditions, establishes conditions for isomorphism of rooted trees as rooted graphs, and provides a combinatorial interpretation of the monomial expansion of pointed chromatic functions.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Shira Zerbib
Summary: This article studies the property of a family of sets and proves that when a family of compact convex sets has a specific intersection property, it can be pierced by a certain number of lines. The proofs are based on the topological KKM theorem.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
David Sossa, Vilmar Trevisan
Summary: The study focuses on the complementarity spectrum and separability index of graphs, demonstrating the relationship between the largest complementarity eigenvalues of graphs of a specific order and deducing the growth trend of the separability index of the set of connected graphs.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Anita Keszler, Zsolt Tuza
Summary: This study considers edge decompositions of K-v((3)) - I and provides decomposition results satisfying certain conditions, complementing previous research findings.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Ping Li
Summary: This paper explores the relationship between monochromatic connection coloring and the connectivity of a graph, providing a method and upper bounds for computing the monochromatic connection number. Additionally, the paper discusses the characteristics of MC-colorings for graphs with specific connectivity requirements.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Santiago Guzman-Pro
Summary: This article discusses the concepts of full-homomorphism, full H-colouring, and minimal H-obstruction. It proves the existence of a finite number of minimal H obstructions for every graph H. Furthermore, it describes the properties of minimal obstructions and poses some related questions.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Rongzhong Xiao
Summary: We prove that for any finite coloring of Q, there exist non-zero elements that satisfy certain conditions.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Robert Lukot'ka
Summary: The article studies the circular flow problem, gives the circular flow number of Goldberg snark G2k+1, and proves a conjecture.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Benjamin Egan, Yuri Nikolayevsky
Summary: A simple graph is called triangular if every edge of it belongs to a triangle. We conjecture that any graphical degree sequence all terms of which are greater than or equal to 4 has a triangular realisation, and establish this conjecture for a class of biregular graphical degree sequences.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Jakub Przybylo
Summary: We improve upon Molloy's breakthrough result by adapting Bernshteyn's proof, achieving a stronger result that states triangle-free graphs can be colored from lists of size (1 +o(1))A/ log A, where vertices sharing a common color do not induce a triangle in G. We also extend this result to graphs of maximum degree A by proving the sufficiency of list sizes (1000 + o(1))A/ log A, as implied by a more general result due to Amini and Reed. Furthermore, we demonstrate that lists of length 2(r - 2)A log2 log2 A/ log2 A are sufficient if one replaces the triangle with any Kr with r >= 4. All of these bounds hold in the context of correspondence colorings.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Hongwei Zhu, Minjia Shi
Summary: This paper studies the b-symbol weight hierarchy of Kasami codes and discusses their applications in high density data storage systems.
DISCRETE MATHEMATICS
(2024)