Parity check matrices and product representations of squares
type: Item
instance of: scholarly article
title: Parity check matrices and product representations of squares
zbMATH Open document ID: 1164.05005
author: Assaf Naor
author: J. Verstraëte
published in: Combinatorica
publication date: 2008-10-21T00:00:00Z
review text: Let \(N_{F}(n,k,r)\) denote the maximum number of columns in an \(n\)-row matrix with entries in a finite field \(F\) in which each column has at most \(r\) nonzero entries and every \(k\) columns are linearly independent over \(F\). In this paper it is shown that \(N_{F}(n,k,r)\ll n^{r/2+cr/k}\) where \(c\approx 4/3\) for large \(k\) and \(a_n\ll b_n\) means that there exists a constant \(C>0\) such that for all \(n\), \(a_n\leq Cb_n\). The proof of this result is based on a novel reduction of the problem to the following Turán type problem: What is the maximum number of edges in an \(n\)-vertex graph which does not contain an even cycle of length \(2k\)? and the method yields a fast algorithm for finding short linear dependencies. Some applications of this method to a problem on hypergraphs which do not contain an even cover of a given size and a problem on product representations of squares in combinatorial number theory are presented.
reviewed by: Ioan Tomescu
Mathematics Subject Classification ID: 05B20
Mathematics Subject Classification ID: 94B65
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 5355093
zbMATH Keywords: finite field
zbMATH Keywords: parity check matrix
zbMATH Keywords: linear dependency
zbMATH Keywords: even hypergraph cover
zbMATH Keywords: forbidden cycle
zbMATH Keywords: product representations of squares
zbMATH Keywords: Turan type problem
MaRDI profile type: Publication
full work available at URL: s00493-008-2195-2
OpenAlex ID: W2033490419
cites work: A fast and simple randomized parallel algorithm for the maximal independent set problem
cites work: Simple Constructions of Almost k-wise Independent Random Variables
cites work: The Moore bound for irregular graphs
cites work: Color-coding
cites work: Finding and counting given length cycles
cites work: Sparse 0−1 Matrices and Forbidden Hypergraphs
cites work: Q4500687
cites work: Q4376259
cites work: Q4830805
cites work: Cycles of even length in graphs
cites work: A logarithmic upper bound on the minimum distance of turbo codes
cites work: Q4871762
cites work: Asymptotically Fast Factorization of Integers
cites work: On product representation of powers. I
cites work: \(C_ 6\)-free bipartite graphs and product representation of squares
cites work: The size of bipartite graphs with a given girth
cites work: Sparse Parity-Check Matrices over Finite Fields
cites work: On sparse parity check matrices
cites work: Good error-correcting codes based on very sparse matrices
cites work: Q4146667
cites work: A Note on Bipartite Graphs Without 2 k -Cycles
cites work: A tale of two sieves.
cites work: Q4871768
cites work: Cycles in bipartite graphs and an application in number theory
cites work: Expander codes
cites work: Linear-time encodable and decodable error-correcting codes
cites work: On arithmetic progressions of cycle lengths in graphs
DOI: 10.1007/S00493-008-2195-2
description: scientific article; zbMATH DE number 5355093