اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدPolynomial treewidth forces a large grid-like-minor
96
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Robertson and Seymour proved that every graph with sufficiently large treewidth contains a large grid minor. However, the best known bound on the treewidth that forces an $elltimesell$ grid minor is exponential in $ell$. It is unknown whether polynomial treewidth suffices. We prove a result in this direction. A emph{grid-like-minor of order} $ell$ in a graph $G$ is a set of paths in $G$ whose intersection graph is bipartite and contains a $K_{ell}$-minor. For example, the rows and columns of the $elltimesell$ grid are a grid-like-minor of order $ell+1$. We prove that polynomial treewidth forces a large grid-like-minor. In particular, every graph with treewidth at least $cell^4sqrt{logell}$ has a grid-like-minor of order $ell$. As an application of this result, we prove that the cartesian product $Gsquare K_2$ contains a $K_{ell}$-minor whenever $G$ has treewidth at least $cell^4sqrt{logell}$.
قيم البحث
اقرأ أيضاً
A 1993 result of Alon and Furedi gives a sharp upper bound on the number of zeros of a multivariate polynomial over an integral domain in a finite grid, in terms of the degree of the polynomial. This result was recently generalized to polynomials ove
r an arbitrary commutative ring, assuming a certain Condition (D) on the grid which holds vacuously when the ring is a domain. In the first half of this paper we give a further Generalized Alon-Furedi Theorem which provides a sharp upper bound when the degrees of the polynomial in each variable are also taken into account. This yields in particular a new proof of Alon-Furedi. We then discuss the relationship between Alon-Furedi and results of DeMillo-Lipton, Schwartz and Zippel. A direct coding theoretic interpretation of Alon-Furedi Theorem and its generalization in terms of Reed--Muller type affine variety codes is shown which gives us the minimum Hamming distance of these codes. Then we apply the Alon-Furedi Theorem to quickly recover (and sometimes strengthen) old and new results in finite geometry, including the Jamison/Brouwer-Schrijver bound on affine blocking sets. We end with a discussion of multiplicity enhancements.
In this paper we characterize large regular graphs using certain entries in the projection matrices onto the eigenspaces of the graph. As a corollary of this result, we show that large association schemes become $P$-polynomial association schemes. Ou
r results are summarized as follows. Let $G=(V,E)$ be a connected $k$-regular graph with $d+1$ distinct eigenvalues $k=theta_0>theta_1>cdots>theta_d$. Since the diameter of $G$ is at most $d$, we have the Moore bound [ |V| leq M(k,d)=1+k sum_{i=0}^{d-1}(k-1)^i. ] Note that if $|V|> M(k,d-1)$ holds, the diameter of $G$ is equal to $d$. Let $E_i$ be the orthogonal projection matrix onto the eigenspace corresponding to $theta_i$. Let $partial(u,v)$ be the path distance of $u,v in V$. Theorem. Assume $|V|> M(k,d-1)$ holds. Then for $x,y in V$ with $partial(x,y)=d$, the $(x,y)$-entry of $E_i$ is equal to [ -frac{1}{|V|}prod_{j=1,2,ldots,d, j e i} frac{theta_0-theta_j}{theta_i-theta_j}. ] If a symmetric association scheme $mathfrak{X}=(X,{R_i}_{i=0}^d)$ has a relation $R_i$ such that the graph $(X,R_i)$ satisfies the above condition, then $mathfrak{X}$ is $P$-polynomial. Moreover we show the dual version of this theorem for spherical sets and $Q$-polynomial association schemes.
We define a bivariate polynomial for unlabeled rooted trees and show that the polynomial of an unlabeled rooted tree $T$ is the generating function of a class of subtrees of $T$. We prove that the polynomial is a complete isomorphism invariant for un
labeled rooted trees. Then, we generalize the polynomial to unlabeled unrooted trees and we show that the generalized polynomial is a complete isomorphism invariant for unlabeled unrooted trees.
In this paper we give a new proof of the universality of the Tutte polynomial for matroids. This proof uses appropriate characters of Hopf algebra of matroids, algebra introduced by Schmitt (1994). We show that these Hopf algebra characters are solut
ions of some differential equations which are of the same type as the differential equations used to describe the renormalization group flow in quantum field theory. This approach allows us to also prove, in a different way, a matroid Tutte polynomial convolution formula published by Kook, Reiner and Stanton (1999). This FPSAC contribution is an extended abstract.
We focus on counting the number of labeled graphs on $n$ vertices and treewidth at most $k$ (or equivalently, the number of labeled partial $k$-trees), which we denote by $T_{n,k}$. So far, only the particular cases $T_{n,1}$ and $T_{n,2}$ had been s
tudied. We show that $$ left(c cdot frac{kcdot 2^k cdot n}{log k} right)^n cdot 2^{-frac{k(k+3)}{2}} cdot k^{-2k-2} leq T_{n,k} leq left(k cdot 2^k cdot nright)^n cdot 2^{-frac{k(k+1)}{2}} cdot k^{-k}, $$ for $k > 1$ and some explicit absolute constant $c > 0$. The upper bound is an immediate consequence of the well-known number of labeled $k$-trees, while the lower bound is obtained from an explicit algorithmic construction. It follows from this construction that both bounds also apply to graphs of pathwidth and proper-pathwidth at most $k$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
