Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userExtremal aspects of graph and hypergraph decomposition problems
102
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We survey recent advances in the theory of graph and hypergraph decompositions, with a focus on extremal results involving minimum degree conditions. We also collect a number of intriguing open problems, and formulate new ones.
rate research
Read More
In a generalized Turan problem, two graphs $H$ and $F$ are given and the question is the maximum number of copies of $H$ in an $F$-free graph of order $n$. In this paper, we study the number of double stars $S_{k,l}$ in triangle-free graphs. We also study an opposite version of this question: what is the maximum number edges/triangles in graphs with double star type restrictions, which leads us to study two questions related to the extremal number of triangles or edges in graphs with degree-sum constraints over adjacent or non-adjacent vertices.
A convex geometric hypergraph or cgh consists of a family of subsets of a strictly convex set of points in the plane. There are eight pairwise nonisomorphic cghs consisting of two disjoint triples. These were studied at length by Bra{ss} (2004) and by Aronov, Dujmovic, Morin, Ooms, and da Silveira (2019). We determine the extremal functions exactly for seven of the eight configurations. The above results are about cyclically ordered hypergraphs. We extend some of them for triangle systems with vertices from a non-convex set. We also solve problems posed by P. Frankl, Holmsen and Kupavskii (2020), in particular, we determine the exact maximum size of an intersecting family of triangles whose vertices come from a set of $n$ points in the plane.
We study the following rainbow version of subgraph containment problems in a family of (hyper)graphs, which generalizes the classical subgraph containment problems in a single host graph. For a collection $textbf{G}={G_1, G_2,ldots, G_{m}}$ of not necessarily distinct graphs on the same vertex set $[n]$, a (sub)graph $H$ on $[n]$ is rainbow if $E(H)subseteq bigcup_{iin [m]}E(G_i)$ and $|E(H)cap E(G_i)|le 1$ for $iin[m]$. Note that if $|E(H)|=m$, then a rainbow $H$ consists of exactly one edge from each $G_i$. Our main results are on rainbow clique-factors in (hyper)graph systems with minimum $d$-degree conditions. In particular, (1) we obtain a rainbow analogue of an asymptotical version of the Hajnal--Szemer{e}di theorem, namely, if $tmid n$ and $delta(G_i)geq(1-frac{1}{t}+varepsilon)n$ for each $iin[frac{n}{t}binom{t}{2}]$, then $textbf{G}$ contains a rainbow $K_t$-factor; (2) we prove that for $1le dle k-1$, essentially a minimum $d$-degree condition forcing a perfect matching in a $k$-graph also forces rainbow perfect matchings in $k$-graph systems. The degree assumptions in both results are asymptotically best possible (although the minimum $d$-degree condition forcing a perfect matching in a $k$-graph is in general unknown). For (1) we also discuss two direct
A Gallai-coloring (Gallai-$k$-coloring) is an edge-coloring (with colors from ${1, 2, ldots, k}$) of a complete graph without rainbow triangles. Given a graph $H$ and a positive integer $k$, the $k$-colored Gallai-Ramsey number $GR_k(H)$ is the minimum integer $n$ such that every Gallai-$k$-coloring of the complete graph $K_n$ contains a monochromatic copy of $H$. In this paper, we consider two extremal problems related to Gallai-$k$-colorings. First, we determine upper and lower bounds for the maximum number of edges that are not contained in any rainbow triangle or monochromatic triangle in a $k$-edge-coloring of $K_n$. Second, for $ngeq GR_k(K_3)$, we determine upper and lower bounds for the minimum number of monochromatic triangles in a Gallai-$k$-coloring of $K_{n}$, yielding the exact value for $k=3$. Furthermore, we determine the Gallai-Ramsey number $GR_k(K_4+e)$ for the graph on five vertices consisting of a $K_4$ with a pendant edge.
This paper provides a survey of methods, results, and open problems on graph and hypergraph colourings, with a particular emphasis on semi-random `nibble methods. We also give a detailed sketch of some aspects of the recent proof of the ErdH{o}s-Faber-Lov{a}sz conjecture.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
