|
|
Additive combinatorics and number theory
Hančl, Jaroslav ; Klazar, Martin (advisor)
We present several results for growth functions of ideals of different com- binatorial structures. An ideal is a set downward closed under a containment relation, like the relation of subpartition for partitions, or the relation of induced subgraph for graphs etc. Its growth function (GF) counts elements of given size. For partition ideals we establish an asymptotics for GF of ideals that do not use parts from a finite set S and use this to construct ideal with highly oscillating GF. Then we present application characterising GF of particular partition ideals. We generalize ideals of ordered graphs to ordered uniform hypergraphs and show two dichotomies for their GF. The first result is a constant to linear jump for k-uniform hypergraphs. The second result establishes the polynomial to exponential jump for 3-uniform hypergraphs. That is, there are no ordered hypergraph ideals with GF strictly inside the constant-linear and polynomial- exponential range. We obtain in both dichotomies tight upper bounds. Finally, in a quite general setting we present several methods how to generate for various combinatorial structures pairs of sets defining two ideals with iden- tical GF. We call these pairs Wilf equivalent pairs and use the automorphism method and the replacement method to obtain such pairs. 1
|
|
|
Additive combinatorics and number theory
Hančl, Jaroslav ; Klazar, Martin (advisor)
We present several results for growth functions of ideals of different com- binatorial structures. An ideal is a set downward closed under a containment relation, like the relation of subpartition for partitions, or the relation of induced subgraph for graphs etc. Its growth function (GF) counts elements of given size. For partition ideals we establish an asymptotics for GF of ideals that do not use parts from a finite set S and use this to construct ideal with highly oscillating GF. Then we present application characterising GF of particular partition ideals. We generalize ideals of ordered graphs to ordered uniform hypergraphs and show two dichotomies for their GF. The first result is a constant to linear jump for k-uniform hypergraphs. The second result establishes the polynomial to exponential jump for 3-uniform hypergraphs. That is, there are no ordered hypergraph ideals with GF strictly inside the constant-linear and polynomial- exponential range. We obtain in both dichotomies tight upper bounds. Finally, in a quite general setting we present several methods how to generate for various combinatorial structures pairs of sets defining two ideals with iden- tical GF. We call these pairs Wilf equivalent pairs and use the automorphism method and the replacement method to obtain such pairs. 1
|
|
|
Additive combinatorics and number theory
Hančl, Jaroslav ; Klazar, Martin (advisor) ; Balogh, Jozsef (referee) ; Nedela, Roman (referee)
We present several results for growth functions of ideals of different com- binatorial structures. An ideal is a set downward closed under a containment relation, like the relation of subpartition for partitions, or the relation of induced subgraph for graphs etc. Its growth function (GF) counts elements of given size. For partition ideals we establish an asymptotics for GF of ideals that do not use parts from a finite set S and use this to construct ideal with highly oscillating GF. Then we present application characterising GF of particular partition ideals. We generalize ideals of ordered graphs to ordered uniform hypergraphs and show two dichotomies for their GF. The first result is a constant to linear jump for k-uniform hypergraphs. The second result establishes the polynomial to exponential jump for 3-uniform hypergraphs. That is, there are no ordered hypergraph ideals with GF strictly inside the constant-linear and polynomial- exponential range. We obtain in both dichotomies tight upper bounds. Finally, in a quite general setting we present several methods how to generate for various combinatorial structures pairs of sets defining two ideals with iden- tical GF. We call these pairs Wilf equivalent pairs and use the automorphism method and the replacement method to obtain such pairs. 1
|
guest ::
