Maximal intersecting families and affine regular polygons in PG(2, q)

Endre Boros; Zoltán Füredi; Jeff Kahn

doi:10.1016/0097-3165(89)90057-5

Maximal intersecting families and affine regular polygons in PG(2, q)

Endre Boros, Zoltán Füredi, Jeff Kahn

Research output: Contribution to journal › Article › peer-review

10 Scopus citations

Abstract

A family of mutually intersecting k-sets is called a k-clique. A k-clique is maximal if it is not contained in any larger k-clique. Using a classification result of Wettl we give a new upper bound for m(k), the minimum number of members of a maximal k-clique, proving m(k) ≤ k² 2 + 5k + o(k) whenever k - 1 is a rime power. The proof is based on finite geometric results which are thought to be of independent interest.

Original language	English (US)
Pages (from-to)	1-9
Number of pages	9
Journal	Journal of Combinatorial Theory, Series A
Volume	52
Issue number	1
DOIs	https://doi.org/10.1016/0097-3165(89)90057-5
State	Published - Sep 1989

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/0097-3165(89)90057-5

Cite this

@article{e41a7b2794f84626ba6184e2382a0ad1,

title = "Maximal intersecting families and affine regular polygons in PG(2, q)",

abstract = "A family of mutually intersecting k-sets is called a k-clique. A k-clique is maximal if it is not contained in any larger k-clique. Using a classification result of Wettl we give a new upper bound for m(k), the minimum number of members of a maximal k-clique, proving m(k) ≤ k2 2 + 5k + o(k) whenever k - 1 is a rime power. The proof is based on finite geometric results which are thought to be of independent interest.",

author = "Endre Boros and Zolt{\'a}n F{\"u}redi and Jeff Kahn",

note = "Funding Information: * Work supported by NSF Grant ECS 85-03212. + Work supported by NSF Grant MCS 83-01867, AFOSR Grant 0271, and a Sloan Research Fellowship.",

year = "1989",

month = sep,

doi = "10.1016/0097-3165(89)90057-5",

language = "English (US)",

volume = "52",

pages = "1--9",

journal = "Journal of Combinatorial Theory - Series A",

issn = "0097-3165",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Maximal intersecting families and affine regular polygons in PG(2, q)

AU - Boros, Endre

AU - Füredi, Zoltán

AU - Kahn, Jeff

N1 - Funding Information: * Work supported by NSF Grant ECS 85-03212. + Work supported by NSF Grant MCS 83-01867, AFOSR Grant 0271, and a Sloan Research Fellowship.

PY - 1989/9

Y1 - 1989/9

N2 - A family of mutually intersecting k-sets is called a k-clique. A k-clique is maximal if it is not contained in any larger k-clique. Using a classification result of Wettl we give a new upper bound for m(k), the minimum number of members of a maximal k-clique, proving m(k) ≤ k2 2 + 5k + o(k) whenever k - 1 is a rime power. The proof is based on finite geometric results which are thought to be of independent interest.

AB - A family of mutually intersecting k-sets is called a k-clique. A k-clique is maximal if it is not contained in any larger k-clique. Using a classification result of Wettl we give a new upper bound for m(k), the minimum number of members of a maximal k-clique, proving m(k) ≤ k2 2 + 5k + o(k) whenever k - 1 is a rime power. The proof is based on finite geometric results which are thought to be of independent interest.

UR - http://www.scopus.com/inward/record.url?scp=38249004983&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38249004983&partnerID=8YFLogxK

U2 - 10.1016/0097-3165(89)90057-5

DO - 10.1016/0097-3165(89)90057-5

M3 - Article

AN - SCOPUS:38249004983

SN - 0097-3165

VL - 52

SP - 1

EP - 9

JO - Journal of Combinatorial Theory - Series A

JF - Journal of Combinatorial Theory - Series A

IS - 1

ER -

Maximal intersecting families and affine regular polygons in PG(2, q)

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this