Generalized Turán densities in the hypercube

2022/01/12 by Maria Axenovich, Axenovich, Maria, Laurin Benz +5
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2201.04598

openalex publication_date 2022/01/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A classical extremal, or Turán-type problem asks to determine \rm ex(G, H), the largest number of edges in a subgraph of a graph G which does not contain a subgraph isomorphic to H. Alon and Shikhelman introduced the so-called generalized extremal number \rm ex(G,T,H), defined to be the maximum number of subgraphs isomorphic to T in a subgraph of G that contains no subgraphs isomorphic to H. In this paper we investigate the case when G = Q_n, the hypercube of dimension n, and T and H are smaller hypercubes or cycles.

Related

• Extremal numbers for cycles in a hypercube
• On the extremal graphs in generalized Turán problems
• An extremal theorem in the hypercube
• Unified approach to the generalized Turán problem and supersaturation
• Survey of generalized Turán problems -- counting subgraphs