ترغب بنشر مسار تعليمي؟ اضغط هنا

Crowns in linear $3$-graphs

150   0   0.0 ( 0 )
 نشر من قبل Jing Guo
 تاريخ النشر 2021
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

A textit{linear $3$-graph}, $H = (V, E)$, is a set, $V$, of vertices together with a set, $E$, of $3$-element subsets of $V$, called edges, so that any two distinct edges intersect in at most one vertex. The linear Turan number, ${rm ex}(n,F)$, is the maximum number of edges in a linear $3$-graph $H$ with $n$ vertices containing no copy of $F$. We focus here on the textit{crown}, $C$, which consists of three pairwise disjoint edges (jewels) and a fourth edge (base) which intersects all of the jewels. Our main result is that every linear $3$-graph with minimum degree at least $4$ contains a crown. This is not true if $4$ is replaced by $3$. In fact the known bounds of the Turan number are [ 6 leftlfloor{frac{n - 3}{4}}rightrfloor leq {rm ex}(n, C) leq 2n, ] and in the construction providing the lower bound all but three vertices have degree $3$. We conjecture that ${rm ex}(n, C) sim frac{3n}{2}$ but even if this were known it would not imply our main result. Our second result is a step towards a possible proof of ${rm ex}(n,C) leq frac{3n}{2}$ (i.e., determining it within a constant error). We show that a minimal counterexample to this statement must contain certain configurations with $9$ edges and we conjecture that all of them lead to contradiction.

قيم البحث

اقرأ أيضاً

An intuitive property of a random graph is that its subgraphs should also appear randomly distributed. We consider graphs whose subgraph densities exactly match their expected values. We call graphs with this property for all subgraphs with $k$ verti ces to be $k$-symmetric. We discuss some properties and examples of such graphs. We construct 3-symmetric graphs and provide some statistics.
86 - Luyining Gan , Jie Han 2020
We show that for any fixed $alpha>0$, cherry-quasirandom 3-graphs of positive density and sufficiently large order $n$ with minimum vertex degree $alpha binom n2$ have a tight Hamilton cycle. This solves a conjecture of Aigner-Horev and Levy.
122 - Jiaao Li , Yulai Ma , Yongtang Shi 2020
A bridgeless graph $G$ is called $3$-flow-critical if it does not admit a nowhere-zero $3$-flow, but $G/e$ has for any $ein E(G)$. Tuttes $3$-flow conjecture can be equivalently stated as that every $3$-flow-critical graph contains a vertex of degree three. In this paper, we study the structure and extreme edge density of $3$-flow-critical graphs. We apply structure properties to obtain lower and upper bounds on the density of $3$-flow-critical graphs, that is, for any $3$-flow-critical graph $G$ on $n$ vertices, $$frac{8n-2}{5}le |E(G)|le 4n-10,$$ where each equality holds if and only if $G$ is $K_4$. We conjecture that every $3$-flow-critical graph on $nge 7$ vertices has at most $3n-8$ edges, which would be tight if true. For planar graphs, the best possible density upper bound of $3$-flow-critical graphs on $n$ vertices is $frac{5n-8}{2}$, known from a result of Kostochka and Yancey (JCTB 2014) on vertex coloring $4$-critical graphs by duality.
Let d_i(G) be the density of the 3-vertex i-edge graph in a graph G, i.e., the probability that three random vertices induce a subgraph with i edges. Let S be the set of all quadruples (d_0,d_1,d_2,d_3) that are arbitrary close to 3-vertex graph dens ities in arbitrary large graphs. Huang, Linial, Naves, Peled and Sudakov have recently determined the projection of the set S to the (d_0,d_3) plane. We determine the projection of the set S to all the remaining planes.
379 - Cai Heng Li , Jin-Xin Zhou 2018
A finite graph $G$ is said to be {em $(G,3)$-$($connected$)$ homogeneous} if every isomorphism between any two isomorphic (connected) subgraphs of order at most $3$ extends to an automorphism $gin G$ of the graph, where $G$ is a group of automorphism s of the graph. In 1985, Cameron and Macpherson determined all finite $(G, 3)$-homogeneous graphs. In this paper, we develop a method for characterising $(G,3)$-connected homogeneous graphs. It is shown that for a finite $(G,3)$-connected homogeneous graph $G=(V, E)$, either $G_v^{G(v)}$ is $2$--transitive or $G_v^{G(v)}$ is of rank $3$ and $G$ has girth $3$, and that the class of finite $(G,3)$-connected homogeneous graphs is closed under taking normal quotients. This leads us to study graphs where $G$ is quasiprimitive on $V$. We determine the possible quasiprimitive types for $G$ in this case and give new constructions of examples for some possible types.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا