Intersecting families of polynomials over finite fields
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909362570657792 |
|---|---|
| author | Salia, Nika Tóth, Dávid |
| author_facet | Salia, Nika Tóth, Dávid |
| contents | This paper establishes an analog of the Erdős-Ko-Rado theorem to polynomial rings over finite fields, affirmatively answering a conjecture of C. Tompkins.
A $k$-uniform family of subsets of a set of finite size $n$ is $l$-intersecting if any two subsets in the family intersect in at least $l$ elements. The study of such intersecting families is a core subject of extremal set theory, tracing its roots to the seminal 1961 Erdős-Ko-Rado theorem, which establishes a sharp upper bound on the size of these families.
As an analog of the Erdős-Ko-Rado theorem, we determine the largest possible size of a family of monic polynomials, each of degree $n$, over a finite field $F_q$, where every pair of polynomials in the family shares a common factor of degree at least $l$. We establish that the upper bound for this size is $q^{n-l}$ and characterize all extremal families that achieve this maximum size.
Further extending our study to triple-intersecting families, where every triplet of polynomials shares a common factor of degree at least $l$, we prove that only trivial families achieve the corresponding upper bound. Moreover, by relaxing the conditions to include polynomials of degree at most $n$, we affirm that only trivial families achieve the corresponding upper bound. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_17821 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Intersecting families of polynomials over finite fields Salia, Nika Tóth, Dávid Number Theory Combinatorics 11T06 05D05 This paper establishes an analog of the Erdős-Ko-Rado theorem to polynomial rings over finite fields, affirmatively answering a conjecture of C. Tompkins. A $k$-uniform family of subsets of a set of finite size $n$ is $l$-intersecting if any two subsets in the family intersect in at least $l$ elements. The study of such intersecting families is a core subject of extremal set theory, tracing its roots to the seminal 1961 Erdős-Ko-Rado theorem, which establishes a sharp upper bound on the size of these families. As an analog of the Erdős-Ko-Rado theorem, we determine the largest possible size of a family of monic polynomials, each of degree $n$, over a finite field $F_q$, where every pair of polynomials in the family shares a common factor of degree at least $l$. We establish that the upper bound for this size is $q^{n-l}$ and characterize all extremal families that achieve this maximum size. Further extending our study to triple-intersecting families, where every triplet of polynomials shares a common factor of degree at least $l$, we prove that only trivial families achieve the corresponding upper bound. Moreover, by relaxing the conditions to include polynomials of degree at most $n$, we affirm that only trivial families achieve the corresponding upper bound. |
| title | Intersecting families of polynomials over finite fields |
| topic | Number Theory Combinatorics 11T06 05D05 |
| url | https://arxiv.org/abs/2409.17821 |