The Turan density $pi(cal F)$ of a family $cal F$ of $r$-graphs is the limit as $ntoinfty$ of the maximum edge density of an $cal F$-free $r$-graph on $n$ vertices. Erdos [Israel J. Math 2 (1964) 183--190] proved that no Turan density can lie in the
open interval $(0,r!/r^r)$. Here we show that any other open subinterval of $[0,1]$ avoiding Turan densities has strictly smaller length. In particular, this implies a conjecture of Grosu [E-print arXiv:1403.4653v1, 2014].
Laczkovich proved that if bounded subsets $A$ and $B$ of $R^k$ have the same non-zero Lebesgue measure and the box dimension of the boundary of each set is less than $k$, then there is a partition of $A$ into finitely many parts that can be translate
d to form a partition of $B$. Here we show that it can be additionally required that each part is both Baire and Lebesgue measurable. As special cases, this gives measurable and translation-on
We give a sketch of proof that any two (Lebesgue) measurable subsets of the unit sphere in $R^n$, for $nge 3$, with non-empty interiors and of the same measure are equidecomposable using pieces that are measurable.
The classical theorem of Vizing states that every graph of maximum degree $d$ admits an edge-coloring with at most $d+1$ colors. Furthermore, as it was earlier shown by KH{o}nig, $d$ colors suffice if the graph is bipartite. We investigate the exis
tence of measurable edge-colorings for graphings. A graphing is an analytic generalization of a bounded-degree graph that appears in various areas, such as sparse graph limits, orbit equivalence theory and measurable group theory. We show that every graphing of maximum degree $d$ admits a measurable edge-coloring with $d + O(sqrt{d})$ colors; furthermore, if the graphing has no odd cycles, then $d+1$ colors suffice. In fact, if a certain conjecture about finite graphs that strengthens Vizings theorem is true, then our method will show that $d+1$ colors are always enough.
Let $G$ be a graph whose edges are coloured with $k$ colours, and $mathcal H=(H_1,dots , H_k)$ be a $k$-tuple of graphs. A monochromatic $mathcal H$-decomposition of $G$ is a partition of the edge set of $G$ such that each part is either a single edg
e or forms a monochromatic copy of $H_i$ in colour $i$, for some $1le ile k$. Let $phi_{k}(n,mathcal H)$ be the smallest number $phi$, such that, for every order-$n$ graph and every $k$-edge-colouring, there is a monochromatic $mathcal H$-decomposition with at most $phi$ elements. Extending the previous results of Liu and Sousa [Monochromatic $K_r$-decompositions of graphs, Journal of Graph Theory}, 76:89--100, 2014], we solve this problem when each graph in $mathcal H$ is a clique and $nge n_0(mathcal H)$ is sufficiently large.
In Martin Gardners October, 1976 Mathematical Games column in Scientific American, he posed the following problem: What is the smallest number of [queens] you can put on a board of side n such that no [queen] can be added without creating three in a
row, a column, or a diagonal? We use the Combinatorial Nullstellensatz to prove that this number is at least n, except in the case when n is congruent to 3 modulo 4, in which case one less may suffice. A second, more elementary proof is also offered in the case that n is even.
Given a planar graph $G$, we consider drawings of $G$ in the plane where edges are represented by straight line segments (which possibly intersect). Such a drawing is specified by an injective embedding $pi$ of the vertex set of $G$ into the plane. W
e prove that a wheel graph $W_n$ admits a drawing $pi$ such that, if one wants to eliminate edge crossings by shifting vertices to new positions in the plane, then at most $(2+o(1))sqrt n$ of all $n$ vertices can stay fixed. Moreover, such a drawing $pi$ exists even if it is presupposed that the vertices occupy any prescribed set of points in the plane. Similar questions are discussed for other families of planar graphs.
The stability method is very useful for obtaining exact solutions of many extremal graph problems. Its key step is to establish the stability property which, roughly speaking, states that any two almost optimal graphs of the same order $n$ can be mad
e isomorphic by changing o(n^2) edges. Here we show how the recently developed theory of graph limits can be used to give an analytic approach to stability. As an application, we present a new proof of the Erdos-Simonovits Stability Theorem. Also, we investigate various properties of the edit distance. In particular, we show that the combinatorial and fraction
Let P_G(q) denote the number of proper q-colorings of a graph G. This function, called the chromatic polynomial of G, was introduced by Birkhoff in 1912, who sought to attack the famous four-color problem by minimizing P_G(4) over all planar graphs G
. Since then, motivated by a variety of applications, much research was done on minimizing or maximizing P_G(q) over various families of graphs. In this paper, we study an old problem of Linial and Wilf, to find the graphs with n vertices and m edges which maximize the number of q-colorings. We provide the first approach which enables one to solve this problem for many nontrivial ranges of parameters. Using our machinery, we show that for each q >= 4 and sufficiently large m < kappa_q n^2 where kappa_q is approximately 1/(q log q), the extremal graphs are complete bipartite graphs minus the edges of a star, plus isolated vertices. Moreover, for q = 3, we establish the structure of optimal graphs for all large m <= n^2/4, confirming (in a stronger form) a conjecture of Lazebnik from 1989.
