Search

In 1977, Yu. V. Matiyasevich proposed a formula expressing the chromatic polynomial of an arbitrary graph as a linear combination of flow polynomials of subgraphs of the original graph. In this paper, we prove that this representation is a particular case of one (easily verifiable) formula, namely, the representation of the characteristic polynomial of an arbitrary matroid as a linear combination of characteristic polynomials of dual matroids. As an application, we represent the flow polynomial of a complete graph with $n$ vertices as the sum of elementary terms with respect to all partitions of positive integer $n$. Since the growth rate of the number of all partitions is less than exponential, this technique allows us to evaluate the flow polynomial for values of $n\approx 50$. We also get an explicit expression for the characteristic polynomial of the matroid dual to the matroid of the projective geometry over a finite field. We prove, in particular, that major coefficients of all these polynomials coincide with the beginning of the row in the Pascal triangle, whose number equals the quantity of elements in the corresponding matroid. At the end part of the paper, we consider one more approach, which allows us to obtain the same results of application of our main theoren by using properties of the Tutte polynomial and the classical Rota formula for coefficients of the characteristic polynomial of a matroid. In addition, we describe the connection between the matroid variant of the Matiyasevich formula and convolution formulas for Tutte polynomials., Comment: 18 pages

Given $n$ men, $n$ women, and $n$ dogs, we assume that each man has a complete preference list of women, while each woman does a complete preference list of dogs, and each dog does a complete preference list of men. We study the so-called 3D-CYC problem, i.e., a three-dimensional problem with cyclic preferences. We understand a matching as a collection of $n$ nonintersecting triples, each of which contains a man, a woman, and a dog. A matching is said to be nonstable, if one can find a man, a woman, and a dog, which belong to different triples and prefer each other to their current partners in the corresponding triples. Otherwise, the matching is said to be stable. According to the conjecture proposed by Eriksson, S\"ostrand, and Strimling (2006), the problem of finding a stable matching (the problem 3DSM-CYC) always has a solution. However, Lam and Paxton have proposed an algorithm for constructing preference lists in 3DSM-CYC of size $n=90$, which has allowed them to disprove the mentioned conjecture. The question on the existence of counterexamples of a lesser size remained open. The main value of this paper consists in reducing the size of the counterexample to $n=20$. At the end part of the paper, we discuss a new variant of 3DSM, whose solution always exists., Comment: 19 pages, 9 figures

Given $n$ men, $n$ women, and $n$ dogs, each man has an incomplete preference list of women, each woman does an incomplete preference list of dogs, and each dog does an incomplete preference list of men. We understand a family as a triple consisting of one man, one woman, and one dog such that each of them enters in the preference list of the corresponding agent. We do a matching as a collection of nonintersecting families (some agents, possibly, remain single). A matching is said to be nonstable, if one can find a man, a woman, and a dog which do not live together currently but each of them would become "happier" if they do. Otherwise the matching is said to be stable (a weakly stable matching in 3-DSMI-CYC problem). We give an example of this problem for $n=3$ where no stable matching exists. Moreover, we prove the absence of such an example for $n<3$. Such an example was known earlier only for $n=6$ (Biro, McDermid, 2010). The constructed examples also allows one to decrease (in two times) the size of the recently constructed analogous example for complete preference lists (Lam, Plaxton, 2019)., Comment: 12 pages, 4 figures

Amorphous solids lack long-range order. Therefore identifying structural defects -- akin to dislocations in crystalline solids -- that carry plastic flow in these systems remains a daunting challenge. By comparing many different structural indicators in computational models of glasses, under a variety of conditions we carefully assess which of these indicators are able to robustly identify the structural defects responsible for plastic flow in amorphous solids. We further demonstrate that the density of defects changes as a function of material preparation and strain in a manner that is highly correlated with the macroscopic material response. Our work represents an important step towards predicting how and when an amorphous solid will fail from its microscopic structure.

A theory for the microscopic structure and the vibrational properties of soft sphere glass at finite temperature is presented. With an effective potential, derived here, the phase diagram and vibrational properties are worked out around the Maxwell critical point at zero temperature $T$ and pressure $p$. Variational arguments and effective medium theory identically predict a non-trivial temperature scale $T^*\sim p^{(2-a)/(1-a)}$ with $a \approx 0.17$ such that low-energy vibrational properties are hard-sphere like for $T \gtrsim T^*$, and zero-temperature soft-sphere like otherwise. However, due to crossovers in the equation of state relating $T$, $p$, and the packing fraction $\phi$, these two regimes lead to four regions where scaling behaviors differ when expressed in terms of $T$ and $\phi$. Scaling predictions are presented for the mean-squared displacement, characteristic frequency, shear modulus, and characteristic elastic length in all regions of the phase diagram., Comment: 8 pages + 3 pages SI

Rheological properties of dense flows of hard particles are singular as one approaches the jamming threshold where flow ceases, both for aerial granular flows dominated by inertia, and for over-damped suspensions. Concomitantly, the lengthscale characterizing velocity correlations appears to diverge at jamming. Here we introduce a theoretical framework that proposes a tentative, but potentially complete scaling description of stationary flows. Our analysis, which focuses on frictionless particles, applies {\it both} to suspensions and inertial flows of hard particles. We compare our predictions with the empirical literature, as well as with novel numerical data. Overall we find a very good agreement between theory and observations, except for frictional inertial flows whose scaling properties clearly differ from frictionless systems. For over-damped flows, more observations are needed to decide if friction is a relevant perturbation or not. Our analysis makes several new predictions on microscopic dynamical quantities that should be accessible experimentally., Comment: 13 pages + 3 pages SI

We study theoretically and numerically the elastic properties of hard sphere glasses, and provide a real-space description of their mechanical stability. In contrast to repulsive particles at zero-temperature, we argue that the presence of certain pairs of particles interacting with a small force $f$ soften elastic properties. This softening affects the exponents characterizing elasticity at high pressure, leading to experimentally testable predictions. Denoting $P(f)\sim f^{\theta_e}$ the force distribution of such pairs and $\phi_c$ the packing fraction at which pressure diverges, we predict that (i) the density of states has a low-frequency peak at a scale $\omega^*$, rising up to it as $D(\omega) \sim \omega^{2+a}$, and decaying above $\omega^*$ as $D(\omega)\sim \omega^{-a}$ where $a=(1-\theta_e)/(3+\theta_e)$ and $\omega$ is the frequency, (ii) shear modulus and mean-squared displacement are inversely proportional with $\langle \delta R^2\rangle\sim1/\mu\sim (\phi_c-\phi)^{\kappa} $ where $\kappa=2-2/(3+\theta_e)$, and (iii) continuum elasticity breaks down on a scale $\ell_c \sim1/\sqrt{\delta z}\sim (\phi_c-\phi)^{-b}$ where $b=(1+\theta_e)/(6+2\theta_e)$ and $\delta z=z-2d$, where $z$ is the coordination and $d$ the spatial dimension. We numerically test (i) and provide data supporting that $\theta_e\approx 0.41$ in our bi-disperse system, independently of system preparation in two and three dimensions, leading to $\kappa\approx1.41$, $a \approx 0.17$, and $b\approx 0.21$. Our results for the mean-square displacement are consistent with a recent exact replica computation for $d=\infty$, whereas some observations differ, as rationalized by the present approach., Comment: 5 pages + 4 pages supplementary information

We model the generation of words with independent unequal probabilities of occurrence of letters. We prove that the probability $p(r)$ of occurrence of words of rank $r$ has a power asymptotics. As distinct from the paper published earlier by B. Conrad and M. Mitzenmacher, we give a brief proof by elementary methods and obtain an explicit formula for the exponent of the power law., Comment: 4 pages

In this paper we answer certain questions posed by V.I. Arnold, namely, we study periods of continued fractions for solutions of quadratic equations in the form $x^2+p x=q$ with integer $p$ and $q$, $p^2+q^2\le R^2$. Our results concern the average sum of period elements and Gauss--Kuzmin statistics as $R\to\infty$., Comment: 10 pages, 3 figures, 1 table

V.I. Arnold has experimentally established that the limit of the statistics of incomplete quotients of partial continued fractions of quadratic irrationalities coincides with the Gauss--Kuz'min statistics. Below we briefly prove this fact for roots of the equation $r x^2+p x=q$ with fixed $p$ and $r$ ($r>0$), and with random $q$, $q\le R$, $R\to \infty$. In Section 3 we estimate the sum of incomplete quotients of the period. According to the obtained bound, prior to the passage to the limit, incomplete quotients in average are logarithmically small. We also upper estimate the proportion of the "red" numbers among those representable as a sum of two squares., Comment: 11 pages, 1 Postscript figures, references replaced, minor changed content of section 1

V.I. Arnold has recently defined the complexity of a sequence of $n$ zeros and ones with the help of the operator of finite differences. In this paper we describe the results obtained for almost most complicated sequences of elements of a finite field, whose dimension $n$ is a prime number. We prove that with $n\to \infty$ this property is inherent in almost all sequences, while the values of multiplicative functions possess this property with any $n$ different from the characteristic of the field. We also describe the prime values of the parameter $n$ which make the logarithmic function almost most complicated. All these sequences reveal a stronger complexity; its algebraic sense is quite clear., Comment: 4 pages

V.I. Arnold has recently defined the complexity of finite sequences of zeroes and ones in terms of periods and preperiods of attractors of a dynamic system of the operator of finite differentiation. Arnold has set up a hypothesis that the sequence of the values of the logarithm is most complicated or almost most complicated. In this paper we obtain the necessary and sufficient conditions which make this sequence (supplemented with zero) most complicated for a more wide class of operators. We prove that a sequence of values of a multiplicative function in a finite field is most complicated or almost most complicated for any operator divisible by the differentiation operator., Comment: 9 pages,2 tables

Let $x$ be a cyclic sequence of $n$ elements of the finite field $\mathbb{F}_q$ (the first element immediately follows the $n$-th one). Let us define the operation $\Delta$ as the transition from $x$ to the sequence of differences of the neighbouring elements from $x$. The aim of this work is to give graphs of the dynamic system $\Delta$ for $q=2$, $n\le 300$ and $q=3$, $n\le 150$. These results enable us to define more precisely the Arnold hypotheses and to prove them., Comment: 16 pages, 2 large tables, program on Mathematica