I was not here for a while, my bad.

Today is a birthday of my brilliant younger colleague and coauthor Ivan Bochkov.

Yesterday I learnt the following nice theorem from him: if G is a finite connected graph whose group of automorphisms is vertex-transitive, it has a perfect (or almost perfect, if the number of vertices is odd) matching.

I like Vanya's proof a lot, but let me wait a bit with it, possibly the readers suggest something equally or more nice.

Comments are in a new format. Reactions allowed.

Here is the proof.

Let a maximal matching in G cover all vertices but t. We should prove that t is 0 or 1, so assume that on the contrary t>1. By Tutte's perfect matching theorem in Berge's "defect formula" form, there exists a set U of vertices such that G-U contains |U|+t odd components. Since G is connected and t>1, we get that U is non-empty. The crucial observation is that any maximal matching in G covers U. Thus, by transitivity, any maximal matching in G covers every vertex, which is absurd. A contradiction.

Let m>1 be an integer. Call a positive integer x written in the base m system dangerous, if x divides the number y, which is obtained from x by reversing its digits, and x<y. Then, if for given m there exists a 3-digit dangerous number, there also exists a 2-digit dangerous number.

A puzzle: who is the author of this result? He is not unlikely the most widely known alive mathematician.

Let n>k>0 be integers. For a sequence of n real numbers, we are allowed to take any k terms and replace them all to their arithmetic mean. The goal is to minimize the number of distinct values in the sequence. Denote the minimal number of distinct values which may be always achieved by f(n,k). For example, if n is a power of k, then f(n, k)=1.

Find f(n, k).

Motivated by a recent puzzle given for our children (they had to prove that f(80,3) is at most 2, actually f(n, k)<k for k>2 always.)

Have anybody here read this Ramsey paper?

The same question about Per Enflo's invariant subspace new text.

For what it worth, on Friday 19:00 by SPb time I discuss the problems of IMO 2023 (in Russian), you may register for a Zoom meeting at https://forms.gle/ZLdA32J689A8q5vZ6 or look at translation in VK group https://vk.com/spbumathcs

a very nice problem from IMC (which is in process now) by Ivan

Everybody loves the Raney lemma a.k.a. лемма о бензоколонках: if n reals x_1,...,x_n sum up to 0, then there exists a cyclic shift x_i,x_{i+1},...,x_n,x_1,...,x_{i-1} with non-negative sums of the initial segments: x_i+x_{i+1}+...+x_k⩾0 (for all k=i,i+1,i+2,...,i-1). (Если вдоль кольцевой автомобильной дороги стоят несколько бензоколонок, в которых бензина суммарно хватает чтобы её объехать, то её можно объехать, стартовав с пустым баком с одной из бензоколонок, двигаясь по часовой стрелке и заправляясь по ходу.)

Today I finally learnt (from Taya Korotchenko) the satisfactory proof.

Take n vectors: (1,-1,0,0,..,0) and all its cyclic shifts. They are the vertices of the simplex in the (n-1)-dimensional space, and 0 is inside this simplex (as its barycentre). The ray from 0 to x=(x_1,...,x_n) crosses some facet of this simplex, for example (and without loss of generality) that formed by all vectors but the last one (-1,0,0,...,0,1). In this facet for every point (y_1,...,y_n) all partial sums y_1+...+y_i of the coordinates are non-negative, since this is so for all its vertices.

after a conversation with Victor Kleptsyn, updated a proof of Huang's sensitivity theorem which I blogposted before.
Here is a link https://fedyapetrov.wordpress.com/2023/10/20/huangs-sensitivity-an-update/ and for those who are lazy to follow the link here is a screenshot of the post

Update: Arseny Akopyan reminded me that this explanation of Huang's argument was observed before by Roman Karasev:

https://arxiv.org/pdf/1907.11175.pdf

А не анонимный опрос никак не устроить?

короче, предлагается считать, что русский лучше, на худой конец есть вполне годные роботы-переводчики

Чат, вступайте https://t.me/+HpH445wOx580ZDIy

Несложно видеть, что

Извините за спам, пытаюсь разобраться. Не очень удобно пока что:(

@ivanovmp разъяснил, как пользоваться этим ботом: там можно задать преамбулу для общения с ним, что, в частности, помогает понимать русский язык. Но есть ограничения по числу символов, типа 255.