Scholars@Duke publication: Thresholds in the Lattice of Subspaces of Fqn

Thresholds in the Lattice of Subspaces of Fqn

Publication , Conference

Rossman, B

Published in: Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics

January 1, 2020

Published version (DOI)

Let Q be an ideal (downward-closed set) in the lattice of linear subspaces of Fqn, ordered by inclusion. For 0 ⩽ k⩽ n, let μk(Q) denote the fraction of k-dimensional subspaces that belong to Q. We show that these densities satisfyμk(Q)=11+z⟹μk+1(Q)⩽11+qz.This implies a sharp threshold theorem: if μk(Q) ⩽ 1 - ε, then μℓ(Q) ⩽ ε for ℓ= k+ O(logq(1 / ε) ).

Duke Scholars

Author Benjamin Rossman Computer Science

Published In

Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics

DOI

10.1007/978-3-030-61792-9_40

EISSN

1611-3349

ISSN

0302-9743

Publication Date

January 1, 2020

Volume

12118 LNCS

Start / End Page

504 / 515

Related Subject Headings

Artificial Intelligence & Image Processing
46 Information and computing sciences

Citation

APA

Chicago

ICMJE

MLA

NLM

Rossman, B. (2020). Thresholds in the Lattice of Subspaces of Fqn. In Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics (Vol. 12118 LNCS, pp. 504–515). https://doi.org/10.1007/978-3-030-61792-9_40

Rossman, B. “Thresholds in the Lattice of Subspaces of Fqn.” In Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics, 12118 LNCS:504–15, 2020. https://doi.org/10.1007/978-3-030-61792-9_40.

Rossman B. Thresholds in the Lattice of Subspaces of Fqn. In: Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics. 2020. p. 504–15.

Rossman, B. “Thresholds in the Lattice of Subspaces of Fqn.” Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics, vol. 12118 LNCS, 2020, pp. 504–15. Scopus, doi:10.1007/978-3-030-61792-9_40.

Rossman B. Thresholds in the Lattice of Subspaces of Fqn. Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics. 2020. p. 504–515.

Published In

Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics

DOI

10.1007/978-3-030-61792-9_40

EISSN

1611-3349

ISSN

0302-9743

Publication Date

January 1, 2020

Volume

12118 LNCS

Start / End Page

504 / 515

Related Subject Headings

Artificial Intelligence & Image Processing
46 Information and computing sciences