اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدInfinite strict gammoids
47
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Finite strict gammoids, introduced in the early 1970s, are matroids defined via finite digraphs equipped with some set of sinks: a set of vertices is independent if it admits a linkage to these sinks. An independent set is maximal precisely if it admits a linkage onto the sinks. In the infinite setting, this characterization of the maximal independent sets need not hold. We identify a type of substructure as the unique obstruction to the characterization. We then show that the sets linkable onto the sinks form the bases of a (possibly non-finitary) matroid precisely when the substructure does not occur.
قيم البحث
اقرأ أيضاً
Building on a bijection of Vandervelde, we enumerate certain unimodal sequences whose alternating sum equals zero. This enables us to refine the enumeration of strict partitions with respect to the number of parts and the BG-rank.
A computer search through the oriented matroid programs with dimension 5 and 10 facets shows that the maximum strictly monotone diameter is 5. Thus $Delta_{sm}(5,10)=5$. This enumeration is analogous to that of Bremner and Schewe for the non-monotone
diameter of 6-polytopes with 12 facets. Similar enumerations show that $Delta_{sm}(4,9)=5$ and $Delta_m(4,9)=Delta_m(5,10)=6.$ We shorten the known non-computer proof of the strict monotone 4-step conjecture.
Let $G$ be a graph and ${mathcal{tau}}: V(G)rightarrow Bbb{N}cup {0}$ be an assignment of thresholds to the vertices of $G$. A subset of vertices $D$ is said to be a dynamic monopoly corresponding to $(G, tau)$ if the vertices of $G$ can be partition
ed into subsets $D_0, D_1,..., D_k$ such that $D_0=D$ and for any $iin {0, ..., k-1}$, each vertex $v$ in $D_{i+1}$ has at least $tau(v)$ neighbors in $D_0cup ... cup D_i$. Dynamic monopolies are in fact modeling the irreversible spread of influence in social networks. In this paper we first obtain a lower bound for the smallest size of any dynamic monopoly in terms of the average threshold and the order of graph. Also we obtain an upper bound in terms of the minimum vertex cover of graphs. Then we derive the upper bound $|G|/2$ for the smallest size of any dynamic monopoly when the graph $G$ contains at least one odd vertex, where the threshold of any vertex $v$ is set as $lceil (deg(v)+1)/2 rceil$ (i.e. strict majority threshold). This bound improves the best known bound for strict majority threshold. We show that the latter bound can be achieved by a polynomial time algorithm. We also show that $alpha(G)+1$ is an upper bound for the size of strict majority dynamic monopoly, where $alpha(G)$ stands for the matching number of $G$. Finally, we obtain a basic upper bound for the smallest size of any dynamic monopoly, in terms of the average threshold and vertex degrees. Using this bound we derive some other upper bounds.
Tree sets are abstract structures that can be used to model various tree-shaped objects in combinatorics. Finite tree sets can be represented by finite graph-theoretical trees. We extend this representation theory to infinite tree sets. First we ch
aracterise those tree sets that can be represented by tree sets arising from infinite trees; these are precisely those tree sets without a chain of order type ${omega+1}$. Then we introduce and study a topological generalisation of infinite trees which can have limit edges, and show that every infinite tree set can be represented by the tree set admitted by a suitable such tree-like space.
For any subset $A subseteq mathbb{N}$, we define its upper density to be $limsup_{ n rightarrow infty } |A cap { 1, dotsc, n }| / n$. We prove that every $2$-edge-colouring of the complete graph on $mathbb{N}$ contains a monochromatic infinite path,
whose vertex set has upper density at least $(9 + sqrt{17})/16 approx 0.82019$. This improves on results of ErdH{o}s and Galvin, and of DeBiasio and McKenney.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
