اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدHypergraphs with many extremal configurations
76
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
For every positive integer $t$ we construct a finite family of triple systems ${mathcal M}_t$, determine its Tur{a}n number, and show that there are $t$ extremal ${mathcal M}_t$-free configurations that are far from each other in edit-distance. We also prove a strong stability theorem: every ${mathcal M}_t$-free triple system whose size is close to the maximum size is a subgraph of one of these $t$ extremal configurations after removing a small proportion of vertices. This is the first stability theorem for a hypergraph problem with an arbitrary (finite) number of extremal configurations. Moreover, the extremal hypergraphs have very different shadow sizes (unlike the case of the famous Turan tetrahedron conjecture). Hence a corollary of our main result is that the boundary of the feasible region of ${mathcal M}_t$ has exactly $t$ global maxima.
قيم البحث
اقرأ أيضاً
Let $F$ be a graph. A hypergraph is called Berge $F$ if it can be obtained by replacing each edge in $F$ by a hyperedge containing it. Given a family of graphs $mathcal{F}$, we say that a hypergraph $H$ is Berge $mathcal{F}$-free if for every $F in m
athcal{F}$, the hypergraph $H$ does not contain a Berge $F$ as a subhypergraph. In this paper we investigate the connections between spectral radius of the adjacency tensor and structural properties of a linear hypergraph. In particular, we obtain a spectral version of Tur{a}n-type problems over linear $k$-uniform hypergraphs by using spectral methods, including a tight result on Berge $C_4$-free linear $3$-uniform hypergraphs.
For fixed positive integers $r, k$ and $ell$ with $1 leq ell < r$ and an $r$-uniform hypergraph $H$, let $kappa (H, k,ell)$ denote the number of $k$-colorings of the set of hyperedges of $H$ for which any two hyperedges in the same color class inters
ect in at least $ell$ elements. Consider the function $KC(n,r,k,ell)=max_{Hin{mathcal H}_{n}} kappa (H, k,ell) $, where the maximum runs over the family ${mathcal H}_n$ of all $r$-uniform hypergraphs on $n$ vertices. In this paper, we determine the asymptotic behavior of the function $KC(n,r,k,ell)$ for every fixed $r$, $k$ and $ell$ and describe the extremal hypergraphs. This variant of a problem of ErdH{o}s and Rothschild, who considered edge colorings of graphs without a monochromatic triangle, is related to the ErdH{o}s--Ko--Rado Theorem on intersecting systems of sets [Intersection Theorems for Systems of Finite Sets, Quarterly Journal of Mathematics, Oxford Series, Series 2, {bf 12} (1961), 313--320].
We study body-and-hinge and panel-and-hinge chains in R^d, with two marked points: one on the first body, the other on the last. For a general chain, the squared distance between the marked points gives a Morse-Bott function on a torus configuration
space. Maximal configurations, when the distance between the two marked points reaches a global maximum, have particularly simple geometrical characterizations. The three-dimensional case is relevant for applications to robotics and molecular structures.
We prove configuration results for extremal Type II codes, analogous to the configuration results of Ozeki and of the second author for extremal Type II lattices. Specifically, we show that for $n in {8, 24, 32, 48, 56, 72, 96}$ every extremal Type I
I code of length $n$ is generated by its codewords of minimal weight. Where Ozeki and Kominers used spherical harmonics and weighted theta functions, we use discrete harmonic polynomials and harmonic weight enumerators. Along we way we introduce $tfrac12$-designs as a discrete analog of Venkovs spherical designs of the same name.
The greedy tree $mathcal{G}(D)$ and the $mathcal{M}$-tree $mathcal{M}(D)$ are known to be extremal among trees with degree sequence $D$ with respect to various graph invariants. This paper provides a general theorem that covers a large family of inva
riants for which $mathcal{G}(D)$ or $mathcal{M}(D)$ is extremal. Many known results, for example on the Wiener index, the number of subtrees, the number of independent subsets and the number of matchings follow as corollaries, as do some new results on invariants such as the number of rooted spanning forests, the incidence energy and the solvability. We also extend our results on trees with fixed degree sequence $D$ to the set of trees whose degree sequence is majorised by a given sequence $D$, which also has a number of applications.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
