Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBounds on the Diameter of Graph Associahedra
374
0
0.0
(
0
)
Added by
Jean Cardinal
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Graph associahedra are generalized permutohedra arising as special cases of nestohedra and hypergraphic polytopes. The graph associahedron of a graph $G$ encodes the combinatorics of search trees on $G$, defined recursively by a root $r$ together with search trees on each of the connected components of $G-r$. In particular, the skeleton of the graph associahedron is the rotation graph of those search trees. We investigate the diameter of graph associahedra as a function of some graph parameters. It is known that the diameter of the associahedra of paths of length $n$, the classical associahedra, is $2n-6$ for a large enough $n$. We give a tight bound of $Theta(m)$ on the diameter of trivially perfect graph associahedra on $m$ edges. We consider the maximum diameter of associahedra of graphs on $n$ vertices and of given tree-depth, treewidth, or pathwidth, and give lower and upper bounds as a function of these parameters. Finally, we prove that the maximum diameter of associahedra of graphs of pathwidth two is $Theta (nlog n)$.
rate research
Read More
Let $P$ be a set of $n$ points in general position in the plane. A subset $I$ of $P$ is called an emph{island} if there exists a convex set $C$ such that $I = P cap C$. In this paper we define the emph{generalized island Johnson graph} of $P$ as the graph whose vertex consists of all islands of $P$ of cardinality $k$, two of which are adjacent if their intersection consists of exactly $l$ elements. We show that for large enough values of $n$, this graph is connected, and give upper and lower bounds on its diameter.
Geometrical objects with integral sides have attracted mathematicians for ages. For example, the problem to prove or to disprove the existence of a perfect box, that is, a rectangular parallelepiped with all edges, face diagonals and space diagonals of integer lengths, remains open. More generally an integral point set $mathcal{P}$ is a set of $n$ points in the $m$-dimensional Euclidean space $mathbb{E}^m$ with pairwise integral distances where the largest occurring distance is called its diameter. From the combinatorial point of view there is a natural interest in the determination of the smallest possible diameter $d(m,n)$ for given parameters $m$ and $n$. We give some new upper bounds for the minimum diameter $d(m,n)$ and some exact values.
We prove upper bounds on the graph diameters of polytopes in two settings. The first is a worst-case bound for integer polytopes in terms of the length of the description of the polytope (in bits) and the minimum angle between facets of its polar. The second is a smoothed analysis bound: given an appropriately normalized polytope, we add small Gaussian noise to each constraint. We consider a natural geometric measure on the vertices of the perturbed polytope (corresponding to the mean curvature measure of its polar) and show that with high probability there exists a giant component of vertices, with measure $1-o(1)$ and polynomial diameter. Both bounds rely on spectral gaps -- of a certain Schrodinger operator in the first case, and a certain continuous time Markov chain in the second -- which arise from the log-concavity of the volume of a simple polytope in terms of its slack variables.
For a family $mathcal F$, let $mathcal D(mathcal F)$ stand for the family of all sets that can be expressed as $Fsetminus G$, where $F,Gin mathcal F$. A family $mathcal F$ is intersecting if any two sets from the family have non-empty intersection. In this paper, we study the following question: what is the maximum of $|mathcal D(mathcal F)|$ for an intersecting family of $k$-element sets? Frankl conjectured that the maximum is attained when $mathcal F$ is the family of all sets containing a fixed element. We show that this holds if $n>50klog k$ and $k>50$. At the same time, we provide a counterexample for $n< 4k.$
We give upper bounds on the order of the automorphism group of a simple graph
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
