Two extremal problems in the light of Lex graphs

2021/06/29 by Kristina Dedndreaj, Dedndreaj, Kristina
Computer Science · Mathematics · #05A18 #05C30 #05C35 #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Mathematical Approximation and Integration

paper · pdf · doi:10.48550/arxiv.2106.15668

openalex publication_date 2021/06/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Extremal problems involving independent sets are much studied. Two of the most important extremal problems in this context are concerned with the sharp upper bounds for the number of independent sets of fixed size and the independence number. In literature, these sharp upper bounds are derived in completely different contexts. In this paper, we show that both of these sharp upper bounds can be derived by considering Lex graphs. More exactly, they depend on two parameters of a sequence defined on them.

Citations

• On cliques in graphs
• On the Activities and Partitions of the Vertex Subsets of Graphs

Related

• Large independent sets from local considerations
• Maximizing the number of maximal independent sets of a fixed size
• Extremal Threshold Graphs for Matchings and Independent Sets
• Uniqueness of the extremal graph in the problem of maximizing the number of independent sets in regular graphs
• High dimensional Hoffman bound and applications in extremal combinatorics