اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدTriple systems with no three triples spanning at most five points
42
0
0.0
(
0
)
تأليف
Stefan Glock
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We show that the maximum number of triples on $n$~points, if no three triples span at most five points, is $(1pm o(1))n^2/5$. More generally, let $f^{(r)}(n;k,s)$ be the maximum number of edges of an $r$-uniform hypergraph on $n$~vertices not containing a subgraph with $k$~vertices and $s$~edges. In 1973, Brown, ErdH{o}s and Sos conjectured that the limit $lim_{nto infty}n^{-2}f^{(3)}(n;k,k-2)$ exists for all~$k$. They proved this for $k=4$, where the limit is $1/6$ and the extremal examples are Steiner triple systems. We prove the conjecture for $k=5$ and show that the limit is~$1/5$. The upper bound is established via a simple optimisation problem. For the lower bound, we use approximate $H$-decompositions of~$K_n$ for a suitably defined graph~$H$.
قيم البحث
اقرأ أيضاً
A graph is called $2K_2$-free if it does not contain two independent edges as an induced subgraph. Mou and Pasechnik conjectured that every $frac{3}{2}$-tough $2K_2$-free graph with at least three vertices has a spanning trail with maximum degree at
most $4$. In this paper, we confirm this conjecture. We also provide examples for all $t < frac{5}{4}$ of $t$-tough graphs that do not have a spanning trail with maximum degree at most $4$.
A generic immersion of a planar graph into the 2-space is said to be knotted if there does not exist a trivial embedding of the graph into the 3-space obtained by lifting the immersion with respect to the natural projection from the 3-space to the 2-
space. In this paper we show that if a generic immersion of a planar graph is knotted then the number of double points of the immersion is more than or equal to three. To prove this, we also show that an embedding of a graph obtained from a generic immersion of the graph (does not need to be planar) with at most three double points is totally free if it contains neither a Hopf link nor a trefoil knot.
Given a combinatorial design $mathcal{D}$ with block set $mathcal{B}$, the block-intersection graph (BIG) of $mathcal{D}$ is the graph that has $mathcal{B}$ as its vertex set, where two vertices $B_{1} in mathcal{B}$ and $B_{2} in mathcal{B} $ are ad
jacent if and only if $|B_{1} cap B_{2}| > 0$. The $i$-block-intersection graph ($i$-BIG) of $mathcal{D}$ is the graph that has $mathcal{B}$ as its vertex set, where two vertices $B_{1} in mathcal{B}$ and $B_{2} in mathcal{B}$ are adjacent if and only if $|B_{1} cap B_{2}| = i$. In this paper several constructions are obtained that start with twofold triple systems (TTSs) with Hamiltonian $2$-BIGs and result in larger TTSs that also have Hamiltonian $2$-BIGs. These constructions collectively enable us to determine the complete spectrum of TTSs with Hamiltonian $2$-BIGs (equivalently TTSs with cyclic $2$-intersecting Gray codes) as well as the complete spectrum for TTSs with $2$-BIGs that have Hamilton paths (i.e., for TTSs with $2$-intersecting Gray codes). In order to prove these spectrum results, we sometimes require ingredient TTSs that have large partial parallel classes; we prove lower bounds on the sizes of partial parallel clasess in arbitrary TTSs, and then construct larger TTSs with both cyclic $2$-intersecting Gray codes and parallel classes.
Let $X$ be a $v$-set, $B$ a set of 3-subsets (triples) of $X$, and $B^+cupB^-$ a partition of $B$ with $|B^-|=s$. The pair $(X,B)$ is called a simple signed Steiner triple system, denoted by ST$(v,s)$, if the number of occurrences of every 2-subset o
f $X$ in triples $BinB^+$ is one more than the number of occurrences in triples $BinB^-$. In this paper we prove that $st(v,s)$ exists if and only if $vequiv1,3pmod6$, $v e7$, and $sin{0,1,...,s_v-6,s_v-4,s_v}$, where $s_v=v(v-1)(v-3)/12$ and for $v=7$, $sin{0,2,3,5,6,8,14}$.
Let $G$ be an $n$-vertex graph with adjacency matrix $A$, and $W=[e,Ae,ldots,A^{n-1}e]$ be the walk matrix of $G$, where $e$ is the all-one vector. In Wang [J. Combin. Theory, Ser. B, 122 (2017): 438-451], the author showed that any graph $G$ is uniq
uely determined by its generalized spectrum (DGS) whenever $2^{-lfloor n/2 rfloor}det W$ is odd and square-free. In this paper, we introduce a large family of graphs $mathcal{F}_n={$ $n$-vertex graphs $Gcolon, 2^{-lfloor n/2 rfloor}det W =p^2b$ and rank$W=n-1$ over $mathbb{Z}/pmathbb{Z}},$ where $b$ is odd and square-free, $p$ is an odd prime and $p mid b$. We prove that any graph in $mathcal{F}_n$ either is DGS or has exactly one generalized cospectral mate up to isomorphism. Moreover, we show that the problem of finding the generalized cospectral mate for a graph in $mathcal{F}_n$ is equivalent to that of generating an appropriate rational orthogonal matrix from a given integral vector. This equivalence essentially depends on an amazing property of graphs in terms of generalized spectra, which states that any symmetric integral matrix generalized cospectral with the adjacency matrix of some graph must be an adjacency matrix. Based on this equivalence, we develop an efficient algorithm to decide whether a given graph in $mathcal{F}_n$ is DGS and further to find the unique generalized cospectral mate when it is not. We give some experimental results on graphs with at most 20 vertices, which suggest that $mathcal{F}_n$ may have a positive density (nearly $3%$) and possibly almost all graphs in $mathcal{F}_n$ are DGS as $nrightarrow infty$. This gives a supporting evidence for Haemers conjecture that almost all graphs are determined by their spectra.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
