The Turán problem asks for the largest number of edges ex(n,H)in an n-vertex graph not containing a fixed forbidden subgraph H,which is one of the most important problems in extremal graph theory.However,the orde...The Turán problem asks for the largest number of edges ex(n,H)in an n-vertex graph not containing a fixed forbidden subgraph H,which is one of the most important problems in extremal graph theory.However,the order of magnitude of ex(n,H)for bipartite graphs is known only in a handful of cases.In particular,giving explicit constructions of extremal graphs is very challenging in this field.In this paper,we develop a polynomial resultant approach to the algebraic construction of explicit extremal graphs,which can efficiently decide whether a specified structure exists.A key insight in our approach is the multipolynomial resultant,which is a fundamental tool of computational algebraic geometry.Our main results include the matched lower bounds on the Turán number of 1-subdivision of K3,t1and the linear Turán number of the Berge theta hypergraph■_(3,t_(2))^(B).where t_(1)=25 and t_(2)=217.Moreover,the constant t1improves the random algebraic construction of Bukh and Conlon(2018)and makes the known estimation better on the smallest value of t1concerning a problem posed by Conlon et al.(2021)by reducing the value from a magnitude of 10^(56)to the number 25,while the constant t_(2)improves a result of He and Tait(2019).展开更多
This letter gives a random construction for Low Density Parity Check (LDPC) codes, which uses an iterative algorithm to avoid short cycles in the Tanner graph. The construction method has great flexible choice in LDPC...This letter gives a random construction for Low Density Parity Check (LDPC) codes, which uses an iterative algorithm to avoid short cycles in the Tanner graph. The construction method has great flexible choice in LDPC code's parameters including codelength, code rate, the least girth of the graph, the weight of column and row in the parity check matrix. The method can be applied to the irregular LDPC codes and strict regular LDPC codes. Systemic codes have many applications in digital communication, so this letter proposes a construction of the generator matrix of systemic LDPC codes from the parity check matrix. Simulations show that the method performs well with iterative decoding.展开更多
An algebraic construction methodology is proposed to design binary time-invariant convolutional low-density parity-check(LDPC)codes.Assisted by a proposed partial search algorithm,the polynomialform parity-check matri...An algebraic construction methodology is proposed to design binary time-invariant convolutional low-density parity-check(LDPC)codes.Assisted by a proposed partial search algorithm,the polynomialform parity-check matrix of the time-invariant convolutional LDPC code is derived by combining some special codewords of an(n,2,n−1)code.The achieved convolutional LDPC codes possess the characteristics of comparatively large girth and given syndrome former memory.The objective of our design is to enable the time-invariant convolutional LDPC codes the advantages of excellent error performance and fast encoding.In particular,the error performance of the proposed convolutional LDPC code with small constraint length is superior to most existing convolutional LDPC codes.展开更多
For two r-graphs T and H,let ex_(r)(n,T,H)be the maximum number of copies of T in an n-vertex H r-graph.The determination of the Turán number ex_(r)(n,T,H)has become the fundamental core problem in extremal graph...For two r-graphs T and H,let ex_(r)(n,T,H)be the maximum number of copies of T in an n-vertex H r-graph.The determination of the Turán number ex_(r)(n,T,H)has become the fundamental core problem in extremal graph theory ever since the pioneering work of Turán’s theorem was published in 1941.Although we have some rich results for the simple graph case,only sporadic results have been known for the hypergraph Turán problems.In this paper,we mainly focus on the function ex_(r)(n,T,H)when H is one of two different hypergraph extensions of the complete bipartite graph K_(s,t).The first extension is the complete bipartite r-graph K^((r))_(s,t),which was introduced by Mubayi and Verstraëte(2004).Using the powerful random algebraic method,we show that if s is sufficiently larger than t,then ex_(r)(n,T,K^((r))_(s,t))=Ω(n^(v−e/t)),where T is an r-graph with v vertices and e edges.In particular,when T is an edge or some specified complete bipartite r-graph,we can determine their asymptotics.The second important extension is the complete r-partite r-graph K^((r))_(s1,s2,…,sr,)which has been widely studied.When r=3,we provide an explicit construction giving ex_(3)(n,K^((3))_(2,2,7))≥1/27n19/7+o(n19/7).Our construction is based on the norm graph,and improves the lower boundΩ(n73/27)obtained by the probabilistic method.展开更多
基金supported by the Institute for Basic Science(IBS-R029-C4)supported by the National Key Research and Development Program of China(Grant No.2020YFA0712100)+1 种基金National Natural Science Foundation of China(Grant No.12231014)Beijing Scholars Program。
文摘The Turán problem asks for the largest number of edges ex(n,H)in an n-vertex graph not containing a fixed forbidden subgraph H,which is one of the most important problems in extremal graph theory.However,the order of magnitude of ex(n,H)for bipartite graphs is known only in a handful of cases.In particular,giving explicit constructions of extremal graphs is very challenging in this field.In this paper,we develop a polynomial resultant approach to the algebraic construction of explicit extremal graphs,which can efficiently decide whether a specified structure exists.A key insight in our approach is the multipolynomial resultant,which is a fundamental tool of computational algebraic geometry.Our main results include the matched lower bounds on the Turán number of 1-subdivision of K3,t1and the linear Turán number of the Berge theta hypergraph■_(3,t_(2))^(B).where t_(1)=25 and t_(2)=217.Moreover,the constant t1improves the random algebraic construction of Bukh and Conlon(2018)and makes the known estimation better on the smallest value of t1concerning a problem posed by Conlon et al.(2021)by reducing the value from a magnitude of 10^(56)to the number 25,while the constant t_(2)improves a result of He and Tait(2019).
基金Supported by the National Natural Science Foundation of China(No.60472053)
文摘This letter gives a random construction for Low Density Parity Check (LDPC) codes, which uses an iterative algorithm to avoid short cycles in the Tanner graph. The construction method has great flexible choice in LDPC code's parameters including codelength, code rate, the least girth of the graph, the weight of column and row in the parity check matrix. The method can be applied to the irregular LDPC codes and strict regular LDPC codes. Systemic codes have many applications in digital communication, so this letter proposes a construction of the generator matrix of systemic LDPC codes from the parity check matrix. Simulations show that the method performs well with iterative decoding.
基金the National Natural Science Foundation of China(No.61401164)。
文摘An algebraic construction methodology is proposed to design binary time-invariant convolutional low-density parity-check(LDPC)codes.Assisted by a proposed partial search algorithm,the polynomialform parity-check matrix of the time-invariant convolutional LDPC code is derived by combining some special codewords of an(n,2,n−1)code.The achieved convolutional LDPC codes possess the characteristics of comparatively large girth and given syndrome former memory.The objective of our design is to enable the time-invariant convolutional LDPC codes the advantages of excellent error performance and fast encoding.In particular,the error performance of the proposed convolutional LDPC code with small constraint length is superior to most existing convolutional LDPC codes.
基金supported by the National Key Research and Development Program of China(Grant No.2020YFA0712100)National Natural Science Foundation of China(Grant No.11971325)+1 种基金supported by National Natural Science Foundation of China(Grant No.11801109)Beijing Scholars Program。
文摘For two r-graphs T and H,let ex_(r)(n,T,H)be the maximum number of copies of T in an n-vertex H r-graph.The determination of the Turán number ex_(r)(n,T,H)has become the fundamental core problem in extremal graph theory ever since the pioneering work of Turán’s theorem was published in 1941.Although we have some rich results for the simple graph case,only sporadic results have been known for the hypergraph Turán problems.In this paper,we mainly focus on the function ex_(r)(n,T,H)when H is one of two different hypergraph extensions of the complete bipartite graph K_(s,t).The first extension is the complete bipartite r-graph K^((r))_(s,t),which was introduced by Mubayi and Verstraëte(2004).Using the powerful random algebraic method,we show that if s is sufficiently larger than t,then ex_(r)(n,T,K^((r))_(s,t))=Ω(n^(v−e/t)),where T is an r-graph with v vertices and e edges.In particular,when T is an edge or some specified complete bipartite r-graph,we can determine their asymptotics.The second important extension is the complete r-partite r-graph K^((r))_(s1,s2,…,sr,)which has been widely studied.When r=3,we provide an explicit construction giving ex_(3)(n,K^((3))_(2,2,7))≥1/27n19/7+o(n19/7).Our construction is based on the norm graph,and improves the lower boundΩ(n73/27)obtained by the probabilistic method.
