MANY CLIQUES IN BOUNDED-DEGREE HYPERGRAPHS

被引:1
|
作者
Kirsch, Rachel [1 ]
Radcliffe, Jamie [2 ]
机构
[1] George Mason Univ, Dept Math Sci, Fairfax, VA 22030 USA
[2] Univ Nebraska Lincoln, Dept Math, Lincoln, NE 68588 USA
关键词
cliques; enumeration; hypergraph; extremal; degree; MAXIMUM NUMBER; COMPLETE SUBGRAPHS; GRAPH;
D O I
10.1137/22M1507565
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Recently Chase determined the maximum possible number of cliques of size t in a graph on n vertices with given maximum degree. Soon afterward, Chakraborti and Chen answered the version of this question in which we ask that the graph have m edges and fixed maximum degree (without imposing any constraint on the number of vertices). In this paper we address these problems on hypergraphs. For s -graphs with s \geq 3 a number of issues arise that do not appear in the graph case. For instance, for general s -graphs we can assign degrees to any i-subset of the vertex set with 1 \leq i \leq s -1. We establish bounds on the number of t -cliques in an s -graph \scrH with i-degree bounded by \Delta in three contexts: \scrH has n vertices; \scrH has m (hyper)edges; and (generalizing the previous case) \scrH has a fixed number p of u -cliques for some u with s \leq u \leq t. When \Delta is of a special form we characterize the extremal s -graphs and prove that the bounds are tight. These extremal examples are the shadows of either Steiner systems or partial Steiner systems. On the way to proving our uniqueness results, we extend results of Fu"\redi and Griggs on uniqueness in Kruskal-Katona from the shadow case to the clique case.
引用
收藏
页码:1436 / 1456
页数:21
相关论文
共 50 条
  • [41] SHADOWS OF 3-UNIFORM HYPERGRAPHS UNDER A MINIMUM DEGREE CONDITION
    Furedi, Zoltan
    Zhao, Yi
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2022, 36 (04) : 2523 - 2533
  • [42] Perfect matchings in large uniform hypergraphs with large minimum collective degree
    Roedl, Vojtech
    Rucinski, Andrzej
    Szemeredi, Endre
    JOURNAL OF COMBINATORIAL THEORY SERIES A, 2009, 116 (03) : 613 - 636
  • [43] A note on perfect matchings in uniform hypergraphs with large minimum collective degree
    Rodl, Vojtech
    Rucinski, Andrzej
    Schacht, Mathias
    Szemeredi, Endre
    COMMENTATIONES MATHEMATICAE UNIVERSITATIS CAROLINAE, 2008, 49 (04): : 633 - 636
  • [44] The Fano Plane and the Strong Independence Ratio in Hypergraphs of Maximum Degree 3
    Henning, Michael A.
    Loewenstein, Christian
    JOURNAL OF GRAPH THEORY, 2016, 83 (02) : 196 - 208
  • [45] Maximum number of colors in hypertrees of bounded degree
    Csilla Bujtás
    Zsolt Tuza
    Central European Journal of Operations Research, 2015, 23 : 867 - 876
  • [46] Maximum number of colors in hypertrees of bounded degree
    Bujtas, Csilla
    Tuza, Zsolt
    CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH, 2015, 23 (04) : 867 - 876
  • [47] The Glauber Dynamics for Colourings of Bounded Degree Trees
    Lucier, Brendan
    Molloy, Michael
    Peres, Yuval
    APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES, 2009, 5687 : 631 - +
  • [48] On the number of connected sets in bounded degree graphs
    Kangas, Kustaa
    Kaski, Petteri
    Korhonen, Janne H.
    Koivisto, Mikko
    ELECTRONIC JOURNAL OF COMBINATORICS, 2018, 25 (04):
  • [49] Lagrangian densities of 4-uniform matchings and degree stability of extremal hypergraphs
    Yan, Zilong
    Peng, Yuejian
    DISCRETE MATHEMATICS, 2025, 348 (01)
  • [50] SPECTRAL MEASURES AND DOMINANT VERTICES IN GRAPHS OF BOUNDED DEGREE
    Bruchez, Claire
    De La Harpe, Pierre
    Nagnibeda, Tatiana
    JOURNAL OF OPERATOR THEORY, 2024, 92 (01) : 215 - 256