Search

Your search keyword '"Florian Pfender"' showing total 101 results
Start Over Author "Florian Pfender"
101 results on '"Florian Pfender"'

31. Making Kr+1-free graphs r-partite

Author

József Balogh, Bernard Lidický, Mikhail Lavrov, Florian Pfender, and Felix Christian Clemen

Subjects
Statistics and Probability, Applied Mathematics, Existential quantification, 010102 general mathematics, 0102 computer and information sciences, 01 natural sciences, Graph, Theoretical Computer Science, Combinatorics, Computational Theory and Mathematics, 010201 computation theory & mathematics, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), 0101 mathematics, Stability theorem, Mathematics
Abstract

The Erd\H{o}s-Simonovits stability theorem states that for all \epsilon >0 there exists \alpha >0 such that if G is a K_{r+1}-free graph on n vertices with e(G) > ex(n,K_{r+1}) - \alpha n^2, then one can remove \epsilon n^2 edges from G to obtain an r-partite graph. F\"uredi gave a short proof that one can choose \alpha=\epsilon. We give a bound for the relationship of \alpha and \varepsilon which is asymptotically sharp as \epsilon \to 0., Comment: 12 pages, 1 figure

Published
2020
Full Text
View/download PDF

47. Sharp bounds for decomposing graphs into edges and triangles

Author

Bernard Lidický, Jan Volec, Oleg Pikhurko, Yanitsa Pehova, Florian Pfender, and Adam Blumenthal

Subjects
Statistics and Probability, Applied Mathematics, 010102 general mathematics, 0102 computer and information sciences, Function (mathematics), 01 natural sciences, Theoretical Computer Science, Combinatorics, Computational Theory and Mathematics, 010201 computation theory & mathematics, ComputingMethodologies_DOCUMENTANDTEXTPROCESSING, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), 0101 mathematics, Constant (mathematics), QA, Mathematics
Abstract

For a real constant $\alpha$, let $\pi_3^\alpha(G)$ be the minimum of twice the number of $K_2$'s plus $\alpha$ times the number of $K_3$'s over all edge decompositions of $G$ into copies of $K_2$ and $K_3$, where $K_r$ denotes the complete graph on $r$ vertices. Let $\pi_3^\alpha(n)$ be the maximum of $\pi_3^\alpha(G)$ over all graphs $G$ with $n$ vertices. The extremal function $\pi_3^3(n)$ was first studied by Gy\H{o}ri and Tuza [Decompositions of graphs into complete subgraphs of given order, Studia Sci. Math. Hungar. 22 (1987), 315--320]. In a recent progress on this problem, Kr\'al', Lidick\'y, Martins and Pehova [Decomposing graphs into edges and triangles, Combin. Prob. Comput. 28 (2019) 465--472] proved via flag algebras that $\pi_3^3(n)\le (1/2+o(1))n^2$. We extend their result by determining the exact value of $\pi_3^\alpha(n)$ and the set of extremal graphs for all $\alpha$ and sufficiently large $n$. In particular, we show for $\alpha=3$ that $K_n$ and the complete bipartite graph $K_{\lfloor n/2\rfloor,\lceil n/2\rceil}$ are the only possible extremal examples for large $n$., Comment: 20 pages, 3 figures

Published
2021
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results