BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Fedor Petrov

Fedor Petrov appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.COmath.NTmath.ACmath.MGComputer Science and Game TheoryDiscrete Mathematicsmath-phmath.CAmath.FAmath.GRmath.MPmath.PRmath.RAmath.SG

Catalog footprint

What is connected

21works
14topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

21 published item(s)

preprint2022arXiv

A combinatorial proof of the Burdzy-Pitman conjecture

We prove a sharp upper bound for the number of high degree differences in bipartite graphs: let $ (U, V, E)$ be a bipartite graph with $U=\{u_1, u_2, \dots, u_n\}$ and $V=\{v_1, v_2, \dots, v_n\}$; for $n\ge k>\frac{n}{2}$ we show that $\sum_{1\le i,j \le n} 1 {\Big\{|\text{deg}(u_i)-\text{deg}(v_j)|\ge k}\Big\} \le 2k(n-k).$ As a direct application we show a slightly stronger, probabilistic version of this theorem and thus confirm the Burdzy-Pitman conjecture about the maximal spread of coherent and independent distributions.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

A greedoid and a matroid inspired by Bhargava's $p$-orderings

Consider a finite set $E$. Assume that each $e \in E$ has a "weight" $w \left(e\right) \in \mathbb{R}$ assigned to it, and any two distinct $e, f \in E$ have a "distance" $d \left(e, f\right) = d \left(f, e\right) \in \mathbb{R}$ assigned to them, such that the distances satisfy the ultrametric triangle inequality $d(a,b)\leqslant \max \left\{d(a,c),d(b,c)\right\}$. We look for a subset of $E$ of given size with maximum perimeter (where the perimeter is defined by summing the weights of all elements and their pairwise distances). We show that any such subset can be found by a greedy algorithm (which starts with the empty set, and then adds new elements one by one, maximizing the perimeter at each step). We use this to define numerical invariants, and also to show that the maximum-perimeter subsets of all sizes form a strong greedoid, and the maximum-perimeter subsets of any given size are the bases of a matroid. This essentially generalizes the "$P$-orderings" constructed by Bhargava in order to define his generalized factorials, and is also similar to the strong greedoid of maximum diversity subsets in phylogenetic trees studied by Moulton, Semple and Steel. We further discuss some numerical invariants of $E, w, d$ stemming from this construction, as well as an analogue where maximum-perimeter subsets are replaced by maximum-perimeter tuples (i.e., elements can appear multiple times).

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Alon -- Tarsi numbers of direct products

We provide a general framework on the coefficients of the graph polynomials of graphs which are Cartesian products. As a corollary, we prove that if $G=(V,E)$ is a graph with degrees of vertices $2d(v), v\in V$, and the graph polynomial $\prod_{(i,j)\in E} (x_j-x_i)$ contains an "almost central" monomial (that means a monomial $\prod_v x_v^{c_v}$, where $|c_v-d(v)|\leqslant 1$ for all $v\in V$), then the Cartesian product $G\square C_{2n}$ is $(d(\cdot)+2)$-choosable.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Combinatorial results implied by many zero divisors in a group ring

It has been recently proved (by Croot, Lev and Pach and the subsequent work by Ellenberg and Gijswijt) that for a group $G=G_0^n$, where $G_0\ne \{1,-1\}^m$ is a fixed finite Abelian group and $n$ is large, any subset $A$ without 3-progressions (triples $x,y,z$ of different elements with $xy=z^2$) contains at most $|G|^{1-c}$ elements, where $c>0$ is a constant depending only on $G_0$. This is known to be false when $G$ is, say, large cyclic group. The aim of this note is to show that algebraic property which corresponds to this difference is the following: in the first case a group algebra $\mathbb{F}[G]$ over suitable field $\mathbb{F}$ contains a subspace $X$ with codimension at most $|X|^{1-c}$ such that $X^3=0$. We discuss which bounds are obtained for finite Abelian $p$-groups and for some matrix $p$-groups: Heisenberg group over $\mathbb{F}_p$ and the unitriangular group over $\mathbb{F}_p$. Also we show how the method works for further generalizations by Kleinberg--Sawin--Speyer and Ellenberg.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On some determinants involving Jacobi symbols

In this paper we study some conjectures on determinants with Jacobi symbol entries posed by Z.-W. Sun. For any positive integer $n\equiv3\pmod4$, we show that $$(6,1)_n=[6,1]_n=(3,2)_n=[3,2]_n=0$$ and $$(4,2)_n=(8,8)_n=(3,3)_n=(21,112)_n=0$$ as conjectured by Sun, where $$(c,d)_n=\bigg|\left(\frac{i^2+cij+dj^2}n\right)\bigg|_{1\le i,j\le n-1}$$ and $$[c,d]_n=\bigg|\left(\frac{i^2+cij+dj^2}n\right)\bigg|_{0\le i,j\le n-1}$$ with $(\frac{\cdot}n)$ the Jacobi symbol. We also prove that $(10,9)_p=0$ for any prime $p\equiv5\pmod{12}$, and $[5,5]_p=0$ for any prime $p\equiv 13,17\pmod{20}$, which were also conjectured by Sun. Our proofs involve character sums over finite fields.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Proof of some conjectures involving quadratic residues

We confirm several conjectures of Sun involving quadratic residues modulo odd primes. For any prime $p\equiv 1\pmod 4$ and integer $a\not\equiv0\pmod p$, we prove that \begin{align*}&(-1)^{|\{1\le k<\frac p4:\ (\frac kp)=-1\}|}\prod_{1\le j<k\le(p-1)/2}(e^{2πiaj^2/p}+e^{2πiak^2/p}) \\=&\begin{cases}1&\text{if}\ p\equiv1\pmod 8,\\\left(\frac ap\right)\varepsilon_p^{-(\frac ap)h(p)}&\text{if}\ p\equiv5\pmod8,\end{cases} \end{align*} and that \begin{align*}&\left|\left\{(j,k):\ 1\le j<k\le\frac{p-1}2\ \&\ \{aj^2\}_p>\{ak^2\}_p\right\}\right| \\&+\left|\left\{(j,k):\ 1\le j<k\le\frac{p-1}2\ \&\ \{ak^2-aj^2\}_p>\frac p2\right\}\right| \\\equiv&\left|\left\{1\le k<\frac p4:\ \left(\frac kp\right)=\left(\frac ap\right)\right\}\right|\pmod2. \end{align*} where $(\frac{a}p)$ is the Legendre symbol, $\varepsilon_p$ and $h(p)$ are the fundamental unit and the class number of the real quadratic field $\mathbb Q(\sqrt p)$ respectively, and $\{x\}_p$ is the least nonnegative residue of an integer $x$ modulo $p$. Also, for any prime $p\equiv3\pmod4$ and $δ=1,2$, we determine $$(-1)^{\left|\left\{(j,k): \ 1\le j<k\le(p-1)/2\ \text{and}\ \{δT_j\}_p>\{δT_k\}_p\right\}\right|},$$ where $T_m$ denotes the triangular number $m(m+1)/2$.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Bang's problem and symplectic invariants

We consider the Tarski--Bang problem about covering of convex bodies by planks. The results of this kind give a lower bound on the sum of widths of planks (regions between a pair of parallel hyperplanes) covering a given convex body. Previously we have applied some notions of symplectic geometry to study convex bodies, and here we show that the symplectic techniques may be useful in this problem as well. We are able to handle some particular cases with the symplectic techniques, and show that the general cases would follow from a certain ``subadditivity conjecture'' in symplectic geometry, motivated by the results of K.~Ball. We also prove several related results by more elementary methods.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A new approach to constant term identities and Selberg-type integrals

Selberg-type integrals that can be turned into constant term identities for Laurent polynomials arise naturally in conjunction with random matrix models in statistical mechanics. Built on a recent idea of Karasev and Petrov we develop a general interpolation based method that is powerful enough to establish many such identities in a simple manner. The main consequence is the proof of a conjecture of Forrester related to the Calogero--Sutherland model. In fact we prove a more general theorem, which includes Aomoto's constant term identity at the same time. We also demonstrate the relevance of the method in additive combinatorics.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Virtual continuity of the measurable functions of several variables, and Sobolev embedding theorems

Classical Luzin's theorem states that the measurable function of one variable is "almost" continuous. This is not so anymore for functions of several variables. The search of right analogue of the Luzin theorem leads to a notion of virtually continuous functions of several variables. This probably new notion appears implicitly in the statements like embeddings theorems and traces theorems for Sobolev spaces. In fact, it reveals their nature as theorems about virtual continuity. This notion is especially useful for the study and classification of measurable functions, aswell as in some questions on dynamical systems, polymorphisms and bistochastic measures. In this work we recall necessary definitions and properties of admissible metrics, define virtual continuity, describe some of applications. Detailed analysis is to be presented in another paper.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On the interpolation of integer-valued polynomials

It is well known, that if polynomial with rational coefficients of degree $n$ takes integer values in points $0,1,...,n$ then it takes integer values in all integer points. Are there sets of $n+1$ points with the same property in other integral domains? We show that answer is negative for the ring of Gaussian integers $\mathbb{Z}[i]$ when $n$ is large enough. Also we discuss the question about minimal possible size of set, such that if polynomial takes integer values in all points of this set then it is integer-valued.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Frugal Mechanism Design via Spectral Techniques

We study the design of truthful mechanisms for set systems, i.e., scenarios where a customer needs to hire a team of agents to perform a complex task. In this setting, frugality [Archer&Tardos'02] provides a measure to evaluate the "cost of truthfulness", that is, the overpayment of a truthful mechanism relative to the "fair" payment. We propose a uniform scheme for designing frugal truthful mechanisms for general set systems. Our scheme is based on scaling the agents' bids using the eigenvector of a matrix that encodes the interdependencies between the agents. We demonstrate that the r-out-of-k-system mechanism and the \sqrt-mechanism for buying a path in a graph [Karlin et. al'05] can be viewed as instantiations of our scheme. We then apply our scheme to two other classes of set systems, namely, vertex cover systems and k-path systems, in which a customer needs to purchase k edge-disjoint source-sink paths. For both settings, we bound the frugality of our mechanism in terms of the largest eigenvalue of the respective interdependency matrix. We show that our mechanism is optimal for a large subclass of vertex cover systems satisfying a simple local sparsity condition. For k-path systems, while our mechanism is within a factor of k + 1 from optimal, we show that it is, in fact, optimal, when one uses a modified definition of frugality proposed in [Elkind et al.'07]. Our lower bound argument combines spectral techniques and Young's inequality, and is applicable to all set systems. As both r-out-of-k systems and single path systems can be viewed as special cases of k-path systems, our result improves the lower bounds of [Karlin et al.'05] and answers several open questions proposed in that paper.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On possible growth of Toeplitz languages

We consider a new family of factorial languages whose subword complexity grows as $Θ(n^α)$, where $α$ is the root of some transcendent equation. Analytical methods and in particular, a corollary of the Wiener-Pitt theorem, are used to find the asymptotic growth of the complexity. Factorial languages considered are languages of arithmetical factors of some Toeplitz words. So, we describe a new family of words with an unusual growth of arithmetical complexity.

0 citations0 reviewsNo code linkedOpen access