A discrete variation of the Littlewood-Offord problem

DOI10.37236/11956MaRDI QIDQ6194235zbMATH OpenOpenAlexFDO

Authors Hossein Esmailian, E. Ghorbani

Publication date 19 March 2024

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2103.13489

zbMATH Keywords

rank-order problems for graphsSperner's theorem

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Structural characterization of families of graphs (05C75) Vector spaces, linear dependence, rank, lineability (15A03) Random matrices (algebraic aspects) (15B52)

Abstract: The Littlewood--Offord problem concerns the number of subsums of a set of vectors that fall in a given convex set. We present a discrete variation of the Littlewood--Offord problem and then utilize that for finding the the maximum order of graphs with given rank or corank. The rank of a graph $G$ is the rank of its adjacency matrix $A(G)$ and the corank of $G$ is $mrank(A(G)+I)$.

Review text

Summary: The Littlewood-Offord problem concerns the number of subsums of a set of vectors that fall in a given convex set. We present a discrete variation of the Littlewood-Offord problem where we estimate the number of subsums that are \((0,1)\)-vectors. We then utilize this to find the maximum order of graphs with given rank or corank. The rank of a graph \(G\) is the rank of its adjacency matrix \(A(G)\) and the corank of \(G\) is the rank of \(A(G)+I\).

Recommendations

• scientific article; zbMATH DE number 1341909
• On the Littlewood-Offord problem
• On a lemma of Littlewood and Offord
• On the counting problem in inverse Littlewood-Offord theory
• Maximum order of graphs with a given corank

Cites work

• scientific article; zbMATH DE number 540115 (Why is no real title available?)
• scientific article; zbMATH DE number 6125590 (Why is no real title available?)
• scientific article; zbMATH DE number 3230288 (Why is no real title available?)
• scientific article; zbMATH DE number 3099315 (Why is no real title available?)
• Inverse Littlewood-Offord problems for quasi-norms
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• Maximum order of graphs with a given corank
• Maximum order of trees and bipartite graphs with a given rank
• Maximum order of triangle-free graphs with a given rank
• On a lemma of Littlewood and Offord
• On a lemma of Littlewood and Offord on the distribution of certain sums
• On a lemma of Littlewood and Offord on the distributions of linear combinations of vectors
• ON A PROBLEM RELATED TO ONE OF LITTLEWOOD AND OFFORD
• On graphs with multiple eigenvalues
• On order and rank of graphs
• On the distribution of sums of residues
• ON THE MULTIPLICITIES OF GRAPH EIGENVALUES
• Singularity of random Bernoulli matrices
• Star partitions and regularity in graphs
• The Littlewood-Offord problem and invertibility of random matrices
• The maximum order of adjacency matrices of graphs with a given rank
• The rank and size of graphs

This page was built for publication: A discrete variation of the Littlewood-Offord problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6194235)