Search

An edge-colored graph is said to contain a rainbow-$F$ if it contains $F$ as a subgraph and every edge of $F$ is a distinct color. The problem of maximizing edges among $n$-vertex properly edge-colored graphs not containing a rainbow-$F$, known as the rainbow Turán problem, was initiated by Keevash, Mubayi, Sudakov and Verstraëte. We investigate a variation of this problem with the additional restriction that the graph is planar, and we denote the corresponding extremal number by $\ex_{\p}^*(n,F)$. In particular, we determine $\ex_{\p}^*(n,P_5)$, where $P_5$ denotes the $5$-vertex path., 22 pages, 9 figures

How many copies of a fixed odd cycle, $C_{2m+1}$, can a planar graph contain? We answer this question asymptotically for $m\in\{2,3,4\}$ and prove a bound which is tight up to a factor of $3/2$ for all other values of $m$. This extends the prior results of Cox--Martin and Lv et al. on the analogous question for even cycles. Our bounds result from a reduction to the following maximum likelihood question: which probability mass $\mu$ on the edges of some clique maximizes the probability that $m$ edges sampled independently from $\mu$ form either a cycle or a path?

For a planar graph $H$, let $\operatorname{\mathbf{N}}_{\mathcal P}(n,H)$ denote the maximum number of copies of $H$ in an $n$-vertex planar graph. In this paper, we prove that $\operatorname{\mathbf{N}}_{\mathcal P}(n,P_7)\sim{4\over 27}n^4$, $\operatorname{\mathbf{N}}_{\mathcal P}(n,C_6)\sim(n/3)^3$, $\operatorname{\mathbf{N}}_{\mathcal P}(n,C_8)\sim(n/4)^4$ and $\operatorname{\mathbf{N}}_{\mathcal P}(n,K_4\{1\})\sim(n/6)^6$, where $K_4\{1\}$ is the $1$-subdivision of $K_4$. In addition, we obtain significantly improved upper bounds on $\operatorname{\mathbf{N}}_{\mathcal P}(n,P_{2m+1})$ and $\operatorname{\mathbf{N}}_{\mathcal P}(n,C_{2m})$ for $m\geq 4$. For a wide class of graphs $H$, the key technique developed in this paper allows us to bound $\operatorname{\mathbf{N}}_{\mathcal P}(n,H)$ in terms of an optimization problem over weighted graphs., Comment: 30 pages

For given posets $P$ and $Q$ and an integer $n$, the generalized Tur��n problem for posets, asks for the maximum number of copies of $Q$ in a $P$-free subset of the $n$-dimensional Boolean lattice, $2^{[n]}$. In this paper, among other results, we show the following: (i) For every $n\geq 5$, the maximum number of $2$-chains in a butterfly-free subfamily of $2^{[n]}$ is $\left\lceil\frac{n}{2}\right\rceil\binom{n}{\lfloor n/2\rfloor}$. (ii) For every fixed $s$, $t$ and $k$, a $K_{s,t}$-free family in $2^{[n]}$ has $O\left(n\binom{n}{\lfloor n/2\rfloor}\right)$ $k$-chains. (iii) For every $n\geq 3$, the maximum number of $2$-chains in an $\textbf{N}$-free family is $\binom{n}{\lfloor n/2\rfloor}$, where $\textbf{N}$ is a poset on 4 distinct elements $\{p_1,p_2,q_1,q_2\}$ for which $p_1 < q_1$, $p_2 < q_1$ and $p_2 < q_2$. (iv) We also prove exact results for the maximum number of $2$-chains in a family that has no $5$-path and asymptotic estimates for the number of $2$-chains in a family with no $6$-path., 13 pages, 3 figures

Let ${\rm ex}_{\mathcal{P}}(n,T,H)$ denote the maximum number of copies of $T$ in an $n$-vertex planar graph which does not contain $H$ as a subgraph. When $T=K_2$, ${\rm ex}_{\mathcal{P}}(n,T,H)$ is the well studied function, the planar Tur��n number of $H$, denoted by ${\rm ex}_{\mathcal{P}}(n,H)$. The topic of extremal planar graphs was initiated by Dowden (2016). He obtained sharp upper bound for both ${\rm ex}_{\mathcal{P}}(n,C_4)$ and ${\rm ex}_{\mathcal{P}}(n,C_5)$. Later on, Y. Lan, et al. continued this topic and proved that ${\rm ex}_{\mathcal{P}}(n,C_6)\leq \frac{18(n-2)}{7}$. In this paper, we give a sharp upper bound ${\rm ex}_{\mathcal{P}}(n,C_6) \leq \frac{5}{2}n-7$, for all $n\geq 18$, which improves Lan's result. We also pose a conjecture on ${\rm ex}_{\mathcal{P}}(n,C_k)$, for $k\geq 7$., 27 pages, 17 figures

In this note, we fix a graph $H$ and ask into how many vertices can each vertex of a clique of size $n$ can be "split" such that the resulting graph is $H$-free. Formally: A graph is an $(n,k)$-graph if its vertex sets is a pairwise disjoint union of $n$ parts of size at most $k$ each such that there is an edge between any two distinct parts. Let $$ f(n,H) = \min \{k \in \mathbb N : \mbox{there is an $(n,k)$-graph $G$ such that $H\not\subseteq G$}\} . $$ Barbanera and Ueckerdt observed that $f(n, H)=2$ for any graph $H$ that is not bipartite. If a graph $H$ is bipartite and has a well-defined Tur\'an exponent, i.e., ${\rm ex}(n, H) = \Theta(n^r)$ for some $r$, we show that $\Omega (n^{2/r -1}) = f(n, H) = O (n^{2/r-1} \log ^{1/r} n)$. We extend this result to all bipartite graphs for which an upper and a lower Tur\'an exponents do not differ by much. In addition, we prove that $f(n, K_{2,t}) =\Theta(n^{1/3})$ for any fixed $t$., Comment: 12 pages

The poset $Y_{k+1, 2}$ consists of $k+2$ distinct elements $x_1$, $x_2$, \dots, $x_{k}$, $y_1$,$y_2$, such that $x_1 \le x_2 \le \dots \le x_{k} \le y_1$,~$y_2$. The poset $Y'_{k+1, 2}$ is the dual of $Y_{k+1, 2}$ Let $\rm{La}^{\sharp}(n,\{Y_{k+1, 2}, Y'_{k+1, 2}\})$ be the size of the largest family $\mathcal{F} \subset 2^{[n]}$ that contains neither $Y_{k+1,2}$ nor $Y'_{k+1,2}$ as an induced subposet. Methuku and Tompkins proved that $\rm{La}^{\sharp}(n, \{Y_{3,2}, Y'_{3,2}\}) = \Sigma(n,2)$ for $n \ge 3$ and they conjectured the generalization that if $k \ge 2$ is an integer and $n \ge k+1$, then $\rm{La}^{\sharp}(n, \{Y_{k+1,2}, Y'_{k+1,2}\}) = \Sigma(n,k)$. In this paper, we introduce a simple discharging approach and prove this conjecture., Comment: 8 pages

Let $G$ be a tripartite graph with $N$ vertices in each vertex class. If each vertex is adjacent to at least $(2/3)N$ vertices in each of the other classes, then either $G$ contains a subgraph that consists of $N$ vertex-disjoint triangles or $G$ is a specific graph in which each vertex is adjacent to exactly $(2/3)N$ vertices in each of the other classes., 22 pages, 4 figures

This paper investigates the number of random edges required to add to an arbitrary dense graph in order to make the resulting graph hamiltonian with high probability. Adding $\Theta(n)$ random edges is both necessary and sufficient to ensure this for all such dense graphs. If, however, the original graph contains no large independent set, then many fewer random edges are required. We prove a similar result for directed graphs., Comment: 7 pages, 1 figure

In this paper we prove an asymptotic multipartite version of a well-known theorem of K��hn and Osthus by establishing, for any graph $H$ with chromatic number $r$, the asymptotic multipartite minimum degree threshold which ensures that a large $r$-partite graph $G$ admits a perfect $H$-tiling. We also give the threshold for an $H$-tiling covering all but a linear number of vertices of $G$, in a multipartite analogue of results of Koml��s and of Shokoufandeh and Zhao., 16 pages

In this paper, we provide a method for determining the asymptotic value of the maximum edit distance from a given hereditary property. This method permits the edit distance to be computed without using Szemer\'edi's Regularity Lemma directly. Using this new method, we are able to compute the edit distance from hereditary properties for which it was previously unknown. For some graphs $H$, the edit distance from ${\rm Forb}(H)$ is computed, where ${\rm forb}(H)$ is the class of graphs which contain no induced copy of graph $H$. Those graphs for which we determine the edit distance asymptotically are $H=K_a+E_b$, an $a$-clique with $b$ isolated vertices, and $H=K_{3,3}$, a complete bipartite graph. We also provide a graph, the first such construction, for which the edit distance cannot be determined just by considering partitions of the vertex set into cliques and cocliques. In the process, we develop weighted generalizations of Tur\'an's theorem, which may be of independent interest., Comment: 29 pages, 6 figures

Bootstrap percolation is a deterministic cellular automaton in which vertices of a graph~$G$ begin in one of two states, "dormant" or "active". Given a fixed integer $r$, a dormant vertex becomes active if at any stage it has at least $r$ active neighbors, and it remains active for the duration of the process. Given an initial set of active vertices $A$, we say that $G$ $r$-percolates (from $A$) if every vertex in $G$ becomes active after some number of steps. Let $m(G,r)$ denote the minimum size of a set $A$ such that $G$ $r$-percolates from $A$. Bootstrap percolation has been studied in a number of settings, and has applications to both statistical physics and discrete epidemiology. Here, we are concerned with degree-based density conditions that ensure $m(G,2)=2$. In particular, we give an Ore-type degree sum result that states that if a graph $G$ satisfies $σ_2(G)\ge n-2$, then either $m(G,2)=2$ or $G$ is in one of a small number of classes of exceptional graphs. We also give a Chvátal-type degree condition: If $G$ is a graph with degree sequence $d_1\le d_2\le\dots\le d_n$ such that $d_i \geq i+1$ or $d_{n-i} \geq n-i-1$ for all $1 \leq i < \frac{n}{2}$, then $m(G,2)=2$ or $G$ falls into one of several specific exceptional classes of graphs. Both of these results are inspired by, and extend, an Ore-type result in [D. Freund, M. Poloczek, and D. Reichman, Contagious sets in dense graphs, to appear in European J. Combin.], 15 pages, 3 figures

In the theory of partially-ordered sets, the two-dimensional Boolean lattice is known as the diamond. In this paper, we show that, if $\mathcal{F}$ is a family in the $n$-dimensional Boolean lattice that has no diamond as a subposet, then $|\mathcal{F}|\leq 2.206653{n\choose \lfloor n/2\rfloor}$, improving a bound by the authors and Michael Young., Comment: The paper has been withdrawn. There is an irreparable error in Lemma 9

The edit distance between two graphs on the same labeled vertex set is the size of the symmetric difference of the edge sets. The distance between a graph, $G$, and a hereditary property, ${\cal H}$, is the minimum of the distance between $G$ and each $G'\in{\cal H}$. The edit distance function of ${\cal H}$ is a function of $p\in[0,1]$ and is the limit of the maximum normalized distance between a graph of density $p$ and ${\cal H}$. This paper develops a method, called localization, for computing the edit distance function of various hereditary properties. For any graph $H$, ${\rm Forb}(H)$ denotes the property of not having an induced copy of $H$. This paper gives some results regarding estimation of the function for an arbitrary hereditary property. This paper also gives the edit distance function for ${\rm Forb}(H)$, where $H$ is a cycle on 9 or fewer vertices., Comment: 21 pages, 8 figures

The poset Y-k,Y-2 consists of k + 2 distinct elements x(1), x(2), ..., x(k), y(1), y(2), such that x(1) = 3 and conjectured the generalization that if k >= 2 is an integer and n >= k +1, then La-#(n, {Y-k,Y-2, Y-k,Y-2'}) = Sigma(n, k)) . On the other hand, it is known that La-#(n, Y-k,Y-2) and La-#(n, Y-k,Y-2') are both strictly greater than Sigma(n, k). In this paper, we introduce a simple approach, motivated by discharging, to prove this conjecture.