Page 308 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 308
GRAPHS, POLYNOMIALS, SURFACES, AND KNOTS (MS-49)
Marked Graphs, marked polynomials and relationships with chromatic
symmetric functions and W-polynomials
Jose Aliste Prieto, jose.aliste@unab.cl
Universidad Andres Bello, Chile
Coauthors: José Zamora, Rosa Orellana, Anna de Mier
We will introduce marked graphs and marked graph polynomials. A marked graph is a graph
where each vertex is annotated with two numbers: A weight to keep track of the original number
of vertices, and a number of dots, to keep track of the contractions taken in order to create this
vertex from the original graph. Marked graph polynomials are polynomials that satisfy a marked
deletion-contraction property and a new property called dot-removal formula. This dot removal
formula + the marked. deletion-contraction allows us to encode 4T relations of chromatic sym-
metric functions into these polynomials and hence understanding these new polynomials allows
us for a better understanding of the chromatic symmetric function.
On the symmetry groups of the neighborly polytopes
Djordje Baralic´, djbaralic@mi.sanu.ac.rs
Mathematical Institute SANU, Serbia
An n-polytope P is said to be k-neighborly if any subset of k or less vertices is the vertex set of a
face of P . The polytopes that are n -neighborly are of particular interests and are called neigh-
2
borly polytopes. They are very important objects in combinatorics because they are solutions of
various extremal properties such as the upper bound predicted by Motzkin for maximal number
of i-faces of an n-polytope with m vertices. A classical example of a neighborly n-polytope
with m vertices is the cyclic polytope Cn(m). The cyclic polytope Cn(m) is the convex hull
Cn(m) := conv {γ(t1), γ(t2), . . . , γ(tm)} ,
for m distinct points γ(ti) with t1 < t2 < · · · < tm on the moment curve which is a curve in Rn
defined by γ : R → Rn, t → γ(t) = (t, t2, . . . , tn) ∈ Rn. The combinatorial class of Cn(m)
does not depend on the specific choices of the parameters ti due to Gale’s evenness condition.
If the number of vertices m of a neighborly n-polytope is not grater than n + 3 then combi-
natorially the polytope is isomorphic to a cyclic polytope. However, there are many neighborly
polytopes which are not cyclic. Barnette in 1981 constructed an infinite family of duals of
neighborly n-polytopes by using an operation called ‘facet splitting’ and Shemer in 1982 intro-
duced a sewing construction that allows to add a vertex to a neighborly polytope in such a way
as to obtain a new neighborly polytope. Both constructions show that for a fixed n the number
of combinatorially different neighborly polytopes grows superexponentially with the number of
vertices m, but our knowledge about the combinatorics of this important objects is considerable
small. The number of combinatorial types of neighborly polytopes in dimensions 4, 5, 6 and 7
with ‘small’ number of vertices is extensively studied in the last decades and following these
results we determine their symmetry groups which are found to be very diverse. There exist not
only the examples of the neighborly polytopes with trivial symmetry groups or Z/2Z, but also
those with relatively big number of symmetries which rises questions of constructions of the
neighborly polytopes with nontrivial symmetry group in arbitrary dimension.
306
Marked Graphs, marked polynomials and relationships with chromatic
symmetric functions and W-polynomials
Jose Aliste Prieto, jose.aliste@unab.cl
Universidad Andres Bello, Chile
Coauthors: José Zamora, Rosa Orellana, Anna de Mier
We will introduce marked graphs and marked graph polynomials. A marked graph is a graph
where each vertex is annotated with two numbers: A weight to keep track of the original number
of vertices, and a number of dots, to keep track of the contractions taken in order to create this
vertex from the original graph. Marked graph polynomials are polynomials that satisfy a marked
deletion-contraction property and a new property called dot-removal formula. This dot removal
formula + the marked. deletion-contraction allows us to encode 4T relations of chromatic sym-
metric functions into these polynomials and hence understanding these new polynomials allows
us for a better understanding of the chromatic symmetric function.
On the symmetry groups of the neighborly polytopes
Djordje Baralic´, djbaralic@mi.sanu.ac.rs
Mathematical Institute SANU, Serbia
An n-polytope P is said to be k-neighborly if any subset of k or less vertices is the vertex set of a
face of P . The polytopes that are n -neighborly are of particular interests and are called neigh-
2
borly polytopes. They are very important objects in combinatorics because they are solutions of
various extremal properties such as the upper bound predicted by Motzkin for maximal number
of i-faces of an n-polytope with m vertices. A classical example of a neighborly n-polytope
with m vertices is the cyclic polytope Cn(m). The cyclic polytope Cn(m) is the convex hull
Cn(m) := conv {γ(t1), γ(t2), . . . , γ(tm)} ,
for m distinct points γ(ti) with t1 < t2 < · · · < tm on the moment curve which is a curve in Rn
defined by γ : R → Rn, t → γ(t) = (t, t2, . . . , tn) ∈ Rn. The combinatorial class of Cn(m)
does not depend on the specific choices of the parameters ti due to Gale’s evenness condition.
If the number of vertices m of a neighborly n-polytope is not grater than n + 3 then combi-
natorially the polytope is isomorphic to a cyclic polytope. However, there are many neighborly
polytopes which are not cyclic. Barnette in 1981 constructed an infinite family of duals of
neighborly n-polytopes by using an operation called ‘facet splitting’ and Shemer in 1982 intro-
duced a sewing construction that allows to add a vertex to a neighborly polytope in such a way
as to obtain a new neighborly polytope. Both constructions show that for a fixed n the number
of combinatorially different neighborly polytopes grows superexponentially with the number of
vertices m, but our knowledge about the combinatorics of this important objects is considerable
small. The number of combinatorial types of neighborly polytopes in dimensions 4, 5, 6 and 7
with ‘small’ number of vertices is extensively studied in the last decades and following these
results we determine their symmetry groups which are found to be very diverse. There exist not
only the examples of the neighborly polytopes with trivial symmetry groups or Z/2Z, but also
those with relatively big number of symmetries which rises questions of constructions of the
neighborly polytopes with nontrivial symmetry group in arbitrary dimension.
306
