اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدList-Distinguishing Cartesian Products of Cliques
85
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 C
artesian 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).
Hellys theorem and its variants show that for a family of convex sets in Euclidean space, local intersection patterns influence global intersection patterns. A classical result of Eckhoff in 1988 provided an optimal fractional Helly theorem for axis-
aligned boxes, which are Cartesian products of line segments. Answering a question raised by Barany and Kalai, and independently Lew, we generalize Eckhoffs result to Cartesian products of convex sets in all dimensions. In particular, we prove that given $alpha in (1-frac{1}{t^d},1]$ and a finite family $mathcal{F}$ of Cartesian products of convex sets $prod_{iin[t]}A_i$ in $mathbb{R}^{td}$ with $A_isubset mathbb{R}^d$ if at least $alpha$-fraction of the $(d+1)$-tuples in $mathcal{F}$ are intersecting then at least $(1-(t^d(1-alpha))^{1/(d+1)})$-fraction of sets in $mathcal{F}$ are intersecting. This is a special case of a more general result on intersections of $d$-Leray complexes. We also provide a construction showing that our result on $d$-Leray complexes is optimal. Interestingly the extremal example is representable as a family of cartesian products of convex sets, implying the bound $alpha>1-frac{1}{t^d}$ and the fraction $(1-(t^d(1-alpha))^{1/(d+1)})$ above are also best possible. The well-known optimal construction for fractional Helly theorem for convex sets in $mathbb{R}^d$ does not have $(p,d+1)$-condition for sublinear $p$. Inspired by this we give constructions showing that, somewhat surprisingly, imposing additional $(p,d+1)$-condition has negligible effect on improving the quantitative bounds in neither the fractional Helly theorem for convex sets nor Cartesian products of convex sets. Our constructions offer a rich family of distinct extremal configurations for fractional Helly theorem, implying in a sense that the optimal bound is stable.
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 $f
colon 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.
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.
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].
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
