On the rank of a random binary matrix
On the rank of a random binary matrix
复制标题
关于随机二元矩阵的秩
DOI：
10.1137/1.9781611975482.58
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Pegden, Wesley
中科院分区：
文献类型：
--
作者：
Cooper, Colin;Frieze, Alan;Pegden, Wesley
我们研究了随机n×mmatrixAn，m；k的秩次，其中每列有来自GF(2)的条目，且精确地yk个单位条目，其他条目为零。列是从所有(Nk)列的集合中独立且均匀地随机选择的.我们得到了作为列数目fc，n，k的函数的秩渐近正确的估计，其中=Cn/k.矩阵An，m；k形成了Ak-均匀随机超图H的点-边关联矩阵.Fan，m；k的等级可以表示如下。设|C2|为2-核的顶点数，|E(C2)|为边数。设m*是|C2|=|E(C2)|的m值。然后是W.HP。形式<；m*Fan，m；k与m渐近，形式≥m*该秩渐近于-|E(C2)|+|C2|。此外，指定i.i.d.U[0，1]权重xi，i∊1，2，…MTO列，并定义一组列的权重SasX(S)=∑j∊SXj。将基准定义为一组n-1(K)个线性独立的柱。我们得到了最小权基的渐近正确估计。这推广了Frieze[关于随机最小生成树问题的值，离散应用数学，(1985年)]的著名结果，即，当Fork=2时，最小权重生成树的预期长度趋于ζ(3)∼1.202。
We study the rank of a randomn×mmatrixAn, m; kwith entries fromGF(2), and exactlykunit entries in each column, the other entries being zero. The columns are chosen independently and uniformly at random from the set of all (nk) such columns.We obtain an asymptotically correct estimate for the rank as a function of the number of columnsmin terms ofc, n, k, and wherem=cn/k.The matrixAn, m; kforms the vertex-edge incidence matrix of ak-uniform random hypergraphH. The rank ofAn, m; kcan be expressed as follows. Let |C2| be the number of vertices of the 2-core ofH, and |E(C2)| the number of edges. Letm*be the value ofmfor which |C2| = |E(C2)|. Then w.h.p. form<m* the rank ofAn, m; kis asymptotic to m, and form≥m* the rank is asymptotic tom– |E(C2)| + |C2|.In addition, assign i.i.d.U[0, 1] weightsXi,i∊ 1, 2, …mto the columns, and define the weight of a set of columnsSasX(S) = ∑j∊SXj. Define a basis as a set ofn– 1 (keven) linearly independent columns. We obtain an asymptotically correct estimate for the minimum weight basis. This generalises the well-known result of Frieze [On the value of a random minimum spanning tree problem, Discrete Applied Mathematics, (1985)] that, fork= 2, the expected length of a minimum weight spanning tree tends to ζ(3) ∼ 1.202.
登录
查看更多内容
k-XORSAT 的可满足性阈值
DOI：
10.1017/s0963548315000097
发表时间：
2012
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
B. Pittel;G. Sorkin
通讯作者：
G. Sorkin
将禁止未成年人纳入随机可表示拟阵中
影响因子：
0.8
作者：
Jason M. Altschuler;E. Yang
通讯作者：
E. Yang
关于随机可表示拟阵
DOI：
--
发表时间：
1984
期刊：
影响因子：
--
作者：
D. G. Kelly;J. Oxley
通讯作者：
J. Oxley
关于几乎所有拟阵的性质
影响因子：
1.1
作者：
L. Lowrance;J. Oxley;C. Semple;D. Welsh
通讯作者：
D. Welsh
随机二元拟阵的次数
DOI：
--
发表时间：
2019
期刊：
Random structures algorithms
影响因子：
--
作者：
Cooper, C.;Frieze, A.;Pegden, W.
通讯作者：
Pegden, W.