Do you want to publish a course? Click here

Measurable versions of Vizings theorem

156   0   0.0 ( 0 )
 Added by Jan Greb\\'ik
 Publication date 2019
  fields
and research's language is English




Ask ChatGPT about the research

No English abstract



rate research

Read More

Soon after his 1964 seminal paper on edge colouring, Vizing asked the following question: can an optimal edge colouring be reached from any given proper edge colouring through a series of Kempe changes? We answer this question in the affirmative for triangle-free graphs.
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 existence 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.
51 - Boris Bukh 2007
For a set of distances D={d_1,...,d_k} a set A is called D-avoiding if no pair of points of A is at distance d_i for some i. We show that the density of A is exponentially small in k provided the ratios d_1/d_2, d_2/d_3, ..., d_{k-1}/d_k are all small enough. This resolves a question of Szekely, and generalizes a theorem of Furstenberg-Katznelson-Weiss, Falconer-Marstrand, and Bourgain. Several more results on D-avoiding sets are presented.
comments
Fetching comments Fetching comments
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا