Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLarge induced matchings in random graphs
114
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Given a large graph $H$, does the binomial random graph $G(n,p)$ contain a copy of $H$ as an induced subgraph with high probability? This classical question has been studied extensively for various graphs $H$, going back to the study of the independence number of $G(n,p)$ by ErdH{o}s and Bollobas, and Matula in 1976. In this paper we prove an asymptotically best possible result for induced matchings by showing that if $C/nle p le 0.99$ for some large constant $C$, then $G(n,p)$ contains an induced matching of order approximately $2log_q(np)$, where $q= frac{1}{1-p}$.
rate research
Read More
A graph $G$ whose edges are coloured (not necessarily properly) contains a full rainbow matching if there is a matching $M$ that contains exactly one edge of each colour. We refute several conjectures on matchings in hypergraphs and full rainbow matchings in graphs, made by Aharoni and Berger and others.
Posas theorem states that any graph $G$ whose degree sequence $d_1 le ldots le d_n$ satisfies $d_i ge i+1$ for all $i < n/2$ has a Hamilton cycle. This degree condition is best possible. We show that a similar result holds for suitable subgraphs $G$ of random graphs, i.e. we prove a `resilience version of Posas theorem: if $pn ge C log n$ and the $i$-th vertex degree (ordered increasingly) of $G subseteq G_{n,p}$ is at least $(i+o(n))p$ for all $i<n/2$, then $G$ has a Hamilton cycle. This is essentially best possible and strengthens a resilience version of Diracs theorem obtained by Lee and Sudakov. Chvatals theorem generalises Posas theorem and characterises all degree sequences which ensure the existence of a Hamilton cycle. We show that a natural guess for a resilience version of Chvatals theorem fails to be true. We formulate a conjecture which would repair this guess, and show that the corresponding degree conditions ensure the existence of a perfect matching in any subgraph of $G_{n,p}$ which satisfies these conditions. This provides an asymptotic characterisation of all degree sequences which resiliently guarantee the existence of a perfect matching.
A rainbow matching in an edge-colored graph is a matching in which no two edges have the same color. The color degree of a vertex v is the number of different colors on edges incident to v. Kritschgau [Electron. J. Combin. 27(2020)] studied the existence of rainbow matchings in edge-colored graph G with average color degree at least 2k, and proved some sufficient conditions for a rainbow marching of size k in G. The sufficient conditions include that |V(G)|>=12k^2+4k, or G is a properly edge-colored graph with |V(G)|>=8k. In this paper, we show that every edge-colored graph G with |V(G)|>=4k-4 and average color degree at least 2k-1 contains a rainbow matching of size k. In addition, we also prove that every strongly edge-colored graph G with average degree at least 2k-1 contains a rainbow matching of size at least k. The bound is sharp for complete graphs.
We show that for $dge d_0(epsilon)$, with high probability, the random graph $G(n,d/n)$ contains an induced path of length $(3/2-epsilon)frac{n}{d}log d$. This improves a result obtained independently by Luczak and Suen in the early 90s, and answers a question of Fernandez de la Vega. Along the way, we generalize a recent result of Cooley, Draganic, Kang and Sudakov who studied the analogous problem for induced matchings.
In this paper, we consider the average size of independent edge sets, also called matchings, in a graph. We characterize the extremal graphs for the average size of matchings in general graphs and trees. In addition, we obtain inequalities between the average size of matchings and the number of matchings as well as the matching energy, which is defined as the sum of the absolute values of the zeros of the matching polynomial.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
