Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userExtension complexities of Cartesian products involving a pyramid
109
0
0.0
(
0
)
Added by
Stefan Weltge
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
It is an open question whether the linear extension complexity of the Cartesian product of two polytopes P, Q is the sum of the extension complexities of P and Q. We give an affirmative answer to this question for the case that one of the two polytopes is a pyramid.
rate research
Read More
We study several problems concerning convex polygons whose vertices lie in a Cartesian product (for short, grid) of two sets of n real numbers. First, we prove that every such grid contains a convex polygon with $Omega$(log n) vertices and that this bound is tight up to a constant factor. We generalize this result to d dimensions (for a fixed d $in$ N), and obtain a tight lower bound of $Omega$(log d--1 n) for the maximum number of points in convex position in a d-dimensional grid. Second, we present polynomial-time algorithms for computing the largest convex chain in a grid that contains no two points of the same x-or y-coordinate. We show how to efficiently approximate the maximum size of a supported convex polygon up to a factor of 2. Finally, we present exponential bounds on the maximum number of convex polygons in these grids, and for some restricted variants. These bounds are tight up to polynomial factors.
A clique minor in a graph G can be thought of as a set of connected subgraphs in G that are pairwise disjoint and pairwise adjacent. The Hadwiger number h(G) is the maximum cardinality of a clique minor in G. This paper studies clique minors in the Cartesian product G*H. Our main result is a rough structural characterisation theorem for Cartesian products with bounded Hadwiger number. It implies that if the product of two sufficiently large graphs has bounded Hadwiger number then it is one of the following graphs: - a planar grid with a vortex of bounded width in the outerface, - a cylindrical grid with a vortex of bounded width in each of the two `big faces, or - a toroidal grid. Motivation for studying the Hadwiger number of a graph includes Hadwigers Conjecture, which states that the chromatic number chi(G) <= h(G). It is open whether Hadwigers Conjecture holds for every Cartesian product. We prove that if |V(H)|-1 >= chi(G) >= chi(H) then Hadwigers Conjecture holds for G*H. On the other hand, we prove that Hadwigers Conjecture holds for all Cartesian products if and only if it holds for all G * K_2. We then show that h(G * K_2) is tied to the treewidth of G. We also develop connections with pseudoachromatic colourings and connected dominating sets that imply near-tight bounds on the Hadwiger number of grid graphs (Cartesian products of paths) and Hamming graphs (Cartesian products of cliques).
The distinguishing number of a graph $G$, denoted $D(G)$, is the minimum number of colors needed to produce a coloring of the vertices of $G$ so that every nontrivial isomorphism interchanges vertices of different colors. A list assignment $L$ on a graph $G$ is a function that assigns each vertex of $G$ a set of colors. An $L$-coloring of $G$ is a coloring in which each vertex is colored with a color from $L(v)$. The list distinguishing number of $G$, denoted $D_{ell}(G)$ is the minimum $k$ such that every list assignment $L$ that assigns a list of size at least $k$ to every vertex permits a distinguishing $L$-coloring. In this paper, we prove that when and $n$ is large enough, the distinguishing and list-distinguishing numbers of $K_nBox K_m$ agree for almost all $m>n$, and otherwise differ by at most one. As a part of our proof, we give (to our knowledge) the first application of the Combinatorial Nullstellensatz to the graph distinguishing problem and also prove an inequality for the binomial distribution that may be of independent interest.
Given smooth manifolds $M_1,ldots, M_n$ (which may have a boundary or corners), a smooth manifold $N$ modeled on locally convex spaces and $alphain({mathbb N}_0cup{infty})^n$, we consider the set $C^alpha(M_1timescdotstimes M_n,N)$ of all mappings $fcolon M_1timescdotstimes M_nto N$ which are $C^alpha$ in the sense of Alzaareer. Such mappings admit, simultaneously, continuous iterated directional derivatives of orders $leq alpha_j$ in the $j$th variable for $jin{1,ldots, n}$, in local charts. We show that $C^alpha(M_1timescdotstimes M_n,N)$ admits a canonical smooth manifold structure whenever each $M_j$ is compact and $N$ admits a local addition. The case of non-compact domains is also considered.
Given a collection of pairwise co-prime integers $% m_{1},ldots ,m_{r}$, greater than $1$, we consider the product $Sigma =Sigma _{m_{1}}times cdots times Sigma _{m_{r}}$, where each $Sigma _{m_{i}}$ is the $m_{i}$-adic solenoid. Answering a question of D. P. Bellamy and J. M. L ysko, in this paper we prove that if $M$ is a subcontinuum of $Sigma $ such that the projections of $M$ on each $Sigma _{m_{i}}$ are onto, then for each open subset $U$ in $Sigma $ with $Msubset U$, there exists an open connected subset $V$ of $Sigma $ such that $Msubset Vsubset U$; i.e. any such $M$ is ample in the sense of Prajs and Whittington [10]. This contrasts with the property of Cartesian squares of fixed solenoids $Sigma _{m_{i}}times Sigma _{m_{i}}$, whose diagonals are never ample [1].
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
