A note on the transversal size of a series of families constructed over Cycle Graph

2015/01/09 by Kaushik Majumder, Majumder, Kaushik, Satyaki Mukherjee +1
Computer Science · Engineering · Mathematics · #05D15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Primary: 05B30 #Secondary: 05C65 #graph theory and CDMA systems #math.CO #msc:05B30 #msc:05C65 #msc:05D15

paper · pdf · doi:10.48550/arxiv.1501.02178

Comments are welcome

arxiv created 2015/01/09 · openalex publication_date 2015/01/09 · arxiv updated 2015/01/12 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

Paul Erdős and László Lovász established by means of an example that there exists a maximal intersecting family of k-sets with approximately (e-1)k! blocks. László Lovász conjectured that their example is best known example which has the maximum number of blocks. Later it was disproved. But the quest for such examples remain valid till this date. In this short note, by computing transversal size of a certain series of uniform intersecting families constructed over the cycle graph, we provide an example which has more than ((k)/(2))^k-1 (approximately) blocks.

Related

• Closed Intersecting Families of finite sets and their applications
• On the maximum number of points in a maximal intersecting family of finite sets
• A note on uniform intersecting families with maximum transversal size
• The exact bound for the Erdős-Ko-Rado theorem for t-cycle-intersecting permutations
• Most Probably Intersecting Hypergraphs