Search

Given a hypergraph $H=(V,E)$, define for every edge $e\in E$ a linear expression with arguments corresponding with the vertices. Next, let the polynomial $p_H$ be the product of such linear expressions for all edges. Our main goal was to find a relationship between the Alon-Tarsi number of $p_H$ and the edge density of $H$. We prove that $AT(p_H)=\lceil ed(H)\rceil+1$ if all the coefficients in $p_H$ are equal to $1$. Our main result is that, no matter what those coefficients are, they can be permuted within the edges so that for the resulting polynomial $p_H^\prime$, $AT(p_H^\prime)\leq 2\lceil ed(H)\rceil+1$ holds. We conjecture that, in fact, permuting the coefficients is not necessary. If this were true, then in particular a significant generalization of the famous 1-2-3 Conjecture would follow.

The properties of the Cournot model based on the most general entanglement operator containing quadratic expressions which is symmetric with respect to the exchange of players are considered. The degree of entanglement of games dependent on one and two squeezing parameters and their payoff values in Nash equilibrium are compared. The analysis showed that the relationship between the degree of entanglement of the initial state of the game and the payoff values in Nash equilibrium is ambiguous. The phase values included in the entanglement operator have a strong influence on the final outcome of the game. In a quantum duopoly based on the initial state of a game that depends on one squeezing parameter, the maximum possible payoff in Nash equilibrium cannot be reached when the value of the phase parameter is greater than zero, in contrast to a game that depends on two parameters., Comment: 31 pages, 15 figures, one figure and some comments have been added

We consider a graph coloring algorithm that processes vertices in order taken uniformly at random and assigns colors to them using First-Fit strategy. We show that this algorithm uses, in expectation, at most $(1 + o(1))\cdot \ln n \,/\, \ln\ln n$ different colors to color any forest with $n$ vertices. We also construct a family of forests that shows that this bound is best possible.

For vanishing fidelity between initial and final states two important quantum speed limits, the Mandelstam-Tamm limit (involving energy dispersion) and Margolus-Levitin one (involving excitation energy expectation value) have been derived. While the generalization of the former limit to the case of arbitrary fidelity is straightforward, the relevant generalization of the latter, given in the seminal paper by Giovanetti et al (Phys. Rev. A67 (2003), 052109) was based on the conjectured equality of lower and upper bounds on the right hand side of generalized Margolus-Levitin inequality, verified numerically up to seven digits. Only recently there appear two proofs of the conjecture. We provide below a very elementary new proof, based on the simplest tools from differential calculus. Thus the generalized Margolus-Levitin speed limit can be derived much in the spirit of the original one valid for vanishing fidelity., Comment: 14 pages, 8 figures, substantially revised according to the suggestions of the referees, published version

It is shown that by an appropriate canonical transformation Kepler dynamics can be put in the form which allows to exhibit the structure of the symmetry transformations related to the superintegrability. They appear to fit nicely into general scheme of nonlinear realizations. In new coordiantes the Kepler dynamics results from dimensional reduction of that describing low energy mesons with spontaneously broken chiral symmetry., Comment: 16 pages, no figures; revised version to appear in Physical Review E

We prove that a class of graphs with an excluded minor and with the maximum degree sublinear in the number of edges is maximally modular, that is, modularity tends to 1 as the number of edges tends to infinity., Comment: 7 pages, 1 figure

We prove that seminormality of cut polytopes is equivalent to normality. This settles two conjectures regarding seminormality of cut polytopes.

The construction of Bell inequalities based on Platonic and Archimedean solids (Quantum 4 (2020), 293) is generalized to the case of orbits generated by the action of some finite groups. A number of examples with considerable violation of Bell inequalities is presented., Comment: 15 pages, 6 figures, modified version as suggested by the reviewers, accepted in Quantum 2021-11-18, Licence statement "arXiv.org perpetual, non-exclusive license" changed to CC-BY 4.0 as demanded by Quantum

A toric variety is constructed from a lattice polytope. It is common in algebraic combinatorics to carry this way a notion of an algebraic property from the variety to the polytope. From the combinatorial point of view, one of the most interesting constructions of toric varieties comes from the base polytope of a matroid. Matroid base polytopes and independence polytopes are Cohen--Macaulay. We study two natural stronger algebraic properties -- Gorenstein and smooth. We provide a full classifications of matroids whose independence polytope or base polytope is smooth or Gorenstein. The latter answers to a question raised by Herzog and Hibi.

Fixed edge processing has become a key feature of 5G networks, while playing a key role in reducing latency, improving energy efficiency and introducing flexible compute resource utilization on-demand with added cost savings. Autonomous vehicles are expected to possess significantly more on-board processing capabilities and with improved connectivity. Vehicles continue to be used for a fraction of the day, and as such there is a potential to increase processing capacity by utilizing these resources while vehicles are in short-term and long-term car parks, in roads and at road intersections. Such car parks and road segments can be transformed, through 6G networks, into vehicular fog clusters, or Fogbanks, that can provide processing, storage and sensing capabilities, making use of underutilized vehicular resources. We introduce the Fogbanks concept, outline current research efforts underway in vehicular clouds, and suggest promising directions for 6G in a world where autonomous driving will become commonplace. Moreover, we study the processing allocation problem in cloud-based Fogbank architecture. We solve this problem using Mixed Integer Programming (MILP) to minimize the total power consumption of the proposed architecture, taking into account two allocation strategies, single allocation of tasks and distributed allocation. Finally, we describe additional future directions needed to establish reliability, security, virtualisation, energy efficiency, business models and standardization.

We study a new optimal stopping problem: Let $G$ be a fixed graph with $n$ vertices which become active on-line in time, one by another, in a random order. The active part of $G$ is the subgraph induced by the active vertices. Find a stopping algorithm that maximizes the expected number of connected components of the active part of $G$. We prove that if $G$ is a $k$-tree, then there is no asymptotically better algorithm than `wait until $\frac{1}{k+1}$ fraction of vertices'. The maximum expected number of connected components equals to $$\left(\frac{k^k}{(k+1)^{k+1}}+o(1)\right)n.$$, Comment: minor corrections

Within Guney-Hillery approach a number of examples of classical and quantum bounds on sum of probabilities resulting from two orbits of $S_4$ is considered. It is shown that the violation of Bell's inequalities is rather rare and gentle., Comment: 21 pages; final version to appear in Quantum Information Processing

Let $f:\mathbb{K}^n\rightarrow\mathbb{K}^m$ be a generically finite polynomial map of degree $d$ between affine spaces. In arXiv:1411.5011 we proved that if $\mathbb{K}$ is the field of complex or real numbers, then the set $S_f$ of points at which $f$ is not proper, is covered by polynomial curves of degree at most $d-1$. In this paper we generalize this result to positive characteristic. We provide a geometric proof of an upper bound by $d$., Comment: arXiv admin note: text overlap with arXiv:1501.00223

The toric variety of a matroid is projectively normal, and therefore it is Cohen-Macaulay. We provide a complete graph-theoretic classification when the toric variety of a graphic matroid is Gorenstein.

The new bound on quantum speed limit (in terms of relative purity) is derived by applying the original Mandelstam-Tamm one to the evolution in the space of Hilbert-Schmidt operators acting in the initial space of states. It is shown that it provides the quantum counterpart of the classical speed limit derived in Phys. Rev. Lett. 120 (2018), 070402 and the $\hbar\rightarrow 0$ limit of the former yields the latter. The existence of classical limit is related to the degree of mixing of the quantum state., Comment: 11 pages, 1 figure; modified version as suggested by the reviewers, accepted in Quantum 2021-06-15, Licence statement "arXiv.org perpetual, non-exclusive license" changed to CC-BY 4.0 as demanded by Quantum

We analyze certain aspects of group theoretical approach to Bell inequalities proposed by G\"uney and Hillery. The general procedure for constructing the relevant group orbits is described. Using Hall theorem we determine the form of Bell inequality in the single orbit case. It is shown that in this case the Bell inequality is not violated for maximally entangled state generating trivial subrepresentation if the representation under consideration is real., Comment: 15 pages, no figures. Small misprints corrected

Using recent work by Erman-Sam-Snowden, we show that finitely generated ideals in the ring of bounded-degree formal power series in infinitely many variables have finitely generated Gr\"obner bases relative to the graded reverse lexicographic order. We then combine this result with the first author's work on topological Noetherianity of polynomial functors to give an algorithmic proof of the following statement: ideals in polynomial rings generated by a fixed number of homogeneous polynomials of fixed degrees only have a finite number of possible generic initial ideals, independently of the number of variables that they involve and independently of the characteristic of the ground field. Our algorithm outputs not only a finite list of possible generic initial ideals, but also finite descriptions of the corresponding strata in the space of coefficients., Comment: Several minor edits

The explicit construction is presented of two-player game satisfying: (i) symmetry with respect to the permutation of the players; (ii) the existence of upper bound on total payoff following from Bell inequality; (iii) the existence of unfair equilibrium with total payoff saturating the above bound. The quantum counterpart of the game is considered which possesses only fair equilibria and strategies outperforming the classical ones., Comment: 20 pages, no figures

We outline the general construction of three-players games with incomplete information which fulfil the following conditions: (i) symmetry with respect to the exchange of the players; (ii) the existence of the upper bound for total payoff resulting from Bell inequalities; (iii) the existence of both fair and unfair Nash equilibria saturating this bound. Conditions (i)$\div$(iii) imply that we are dealing with conflicting interest games. An explicit example of such a game is given. A quantum counterpart of this game is considered which is obtained by keeping the same utilities but replacing classical advisor by a quantum one. It is shown that the quantum game possesses only fair equilibria with strictly higher payoffs than in the classical case. This implies that quantum nonlocality can be used to resolve a conflict between players., Comment: New version with some references added; all conclusions remain unchanged; 16 pages, no figures

Recently (Phys. Rev. Lett. 114 (2015), 210402) the influence of the so called "Wigner translations" (more generally-Lorentz trans- formations) on circularly polarized Gaussian packets ( providing the solution to Maxwell equations in paraxial approximation) has been studied. It appears that, within this approximation, the Wigner trans- lations have an efect of shifting the wave packet trajectory parallel to itself by an amount proportional to the photon helicity. It has been suggested that this shift may result from specific properties of the algebra of Poincare generators for massless particles. In the present letter we describe the general relation between transformation proper- ties of electromagnetic field on quantum and classical levels. It allows for a straightforward derivation of the helicity-dependent transforma- tion rules. We present also an elementary derivation of the formula for sideways shift based on classical Maxwell theory. Some comments are made concerning the generalization to higher helicities and the relation to the coordinate operator defined long time ago by Pryce., Comment: 13 pages; no figures; section "Conclusions" added; missing normalization factor in eq.(20) inserted; final form to appear in Physics Letters B

We prove a new exchange property for bases of a matroid that generalizes the multiple symmetric exchange property. For every bases $B_1,\dots,B_k$ of a matroid and a subset $A_1\subset B_1$ there exist subsets $A_2\subset B_2,\dots,A_k\subset B_k$ such that all sets $(B_i\setminus A_i)\cup A_{i-1}$ achieved by a cyclic shift of $A_i$'s by one are bases.

The recently proposed (Phys. Rev. A90 (2014), 062121 and Phys. Rev. A91 (2015), 052110) group theoretical approach to the problem of breaking the Bell inequalities is applied to $S_4$ group. The Bell inequalities based on the choice of three orbits in the representation space corresponding to standard representation of $S_4$ are derived and their breaking is described. The corresponding nonlocal games are analyzed., Comment: 19 pages, no figures

In two recent papers (Phys. Rev. A90 (2014), 062121 and Phys. Rev. A91 (2015), 052110) an interesting method of analyzing the violation of Bell inequalities has been proposed which is based on the theory of finite group representations. We apply here this method to more complicated example of $S_4$ symmetry. We show how the Bell inequality can be related to the symmetries of regular tetrahedron. By choosing the orbits of threedimensional representation of $S_4$ determined by the geometry of tetrahedron we find that the Bell inequality under consideration is violated in quantum theory. The corresponding nonlocal game is analyzed., Comment: 22 pages, 1 figure, final version accepted for publication in Physical Review A

In $1980$ White conjectured that every element of the toric ideal of a matroid is generated by quadratic binomials corresponding to symmetric exchanges. We prove White's conjecture for high degrees with respect to the rank. This extends our result arXiv:1302.5236 confirming White's conjecture `up to saturation'. Furthermore, we study degrees of Gr\"{o}bner bases and Betti tables of the toric ideals of matroids of a fixed rank., Comment: final version, 16 pages

We study the symmetry of the class of nonlocal models which includes the nonlocal extension of the Pais-Uhlenbeck oscillator. As a consequence, we obtain an infinite dimensional symmetry algebra, containing the Virasoro algebra, which can be considered as a generalization of the non-relativistic conformal symmetries to the infinite order. Moreover, this nonlocal extension resembles to some extent the string model and on the quantum level it leads to the centrally extended Virasoro algebra., Comment: 21 pages. Minor changes, references modified

Landsburg method of classifying mixed Nash equilibria for maximally entangled Eisert-Lewenstein-Wilkens (ELW) game is analyzed with special emphasis on symmetries inherent to the problem. Nash equilibria for the original ELW game are determined., Comment: 25 pages, no figures

The two-players $N$ strategies games quantized according to the Eisert-Lewenstein-Wilkens scheme (Phys. Rev. Lett. 83 (1999), 3077) are considered. Group theoretical methods are applied to the problem of finding a general form of gate operators (entanglers) under the assumption that the set of classical pure strategies is contained in the set of pure quantum ones. The role of the stability group of the initial state of the game is stressed. As an example, it is shown that the maximally entangled games do not admit nontrivial pure Nash strategies. The general arguments are supported by explicit computations performed in the three strategies case., Comment: 35 pages, no figures, final version of papers: arXiv:1404.4454, arXiv:1403.7731, arXiv:1402.3932

In this note we introduce Cox rings of singularities and explicitly compute them in the case of du Val singularities $\mathbb{D}_n,\mathbb{E}_6,\mathbb{E}_7$ and $\mathbb{E}_8$., Comment: final version (published version + minor corrections), 17 pages

The main goal of this thesis is to study $\mathbb{K}$-uniruled sets that appear in affine geometry. At the beginning we discuss the property of $\mathbb{K}$-uniruledness and its equivalent conditions. Then we bound from above the degree of $\mathbb{K}$-uniruledness of the non-properness set of a polynomial map in terms of its degree and degree of $\mathbb{K}$-uniruledness of the domain variety. At the end we show that some sets associated with the set of fixed points of an algebraic group action are $\mathbb{K}$-uniruled., Comment: PhD thesis in mathematics, Institute of Mathematics of the Polish Academy of Sciences, defended 18 Jan 2013

This thesis is basically devoted to matroids -- fundamental structure of combinatorial optimization -- though some of our results concern simplicial complexes, or Euclidean spaces. We study old and new problems for these structures, with combinatorial, algebraic, and topological flavor., Comment: PhD thesis in computer science, Jagiellonian University, defended 24 Jan 2014 (updated references)

A (continuous) necklace is simply an interval of the real line colored measurably with some number of colors. A well-known application of the Borsuk-Ulam theorem asserts that every $k$-colored necklace can be fairly split by at most $k$ cuts (from the resulting pieces one can form two collections, each capturing the same measure of every color). Here we prove that for every $k\geq 1$ there is a measurable $(k+3)$-coloring of the real line such that no interval can be fairly split using at most $k$ cuts. In particular, there is a measurable $4$-coloring of the real line in which no two adjacent intervals have the same measure of every color. An analogous problem for the integers was posed by Erd\H{o}s in 1961 and solved in the affirmative in 1991 by Ker\"anen. Curiously, in the discrete case the desired coloring also uses four colors., Comment: final version, 7 pages. arXiv admin note: text overlap with arXiv:1209.1809

In this note we prove the relation between Betti numbers of an Arf semigroup $S$ and its blowup $S'$ in the case when they have the same multiplicity $n$. The relation is then $\beta_{i,s}(S')=\beta_{i,{s+(i+1)n}}(S)$., Comment: final version, 4 pages

We give a necessary and sufficient condition for a simplicial complex to be approximately Cohen-Macaulay. Namely it is approximately Cohen-Macaulay if and only if the ideal associated to its Alexander dual is componentwise linear and generated in two consecutive degrees. This completes the result of Herzog and Hibi who proved that a simplicial complex is sequentially Cohen-Macaulay if and only if the ideal associated to its Alexander dual is componentwise linear., Comment: final version, 3 pages

A coloring of a matroid is an assignment of colors to the elements of its ground set. We restrict to proper colorings - those for which elements of the same color form an independent set. Seymour proved that a $k$-colorable matroid is also colorable from any lists of size $k$. We generalize this theorem to the case when lists have still fixed sizes, but not necessarily equal. For any fixed size of lists assignment $\ell$, we prove that, if a matroid is colorable from a particular lists of size $\ell$, then it is colorable from any lists of size $\ell$. This gives an explicit necessary and sufficient condition for a matroid to be list colorable from any lists of a fixed size. As an application, we show how to use our condition to derive several base exchange properties.

Let $K$ be an algebraically closed field. Let $G$ be a non-trivial connected unipotent group, which acts effectively on an affine variety $X.$ Then every non-empty component $R$ of the set of fixed points of $G$ is a $K$-uniruled variety, i.e, there exists an affine cylinder $W\times K$ and a dominant, generically-finite polynomial mapping $\phi:W\times K\rightarrow R.$ We show also that if an arbitrary infinite algebraic group $G$ acts effectively on $K^n$ and the set of fixed points contains a hypersurface $H$, then this hypersurface is $K$-uniruled., Comment: final version, 6 pages

Let $f$ be a generically finite polynomial map $f: \mathbb{C}^n\to \mathbb{C}^m$ of algebraic degree $d$. Motivated by the study of the Jacobian Conjecture, we prove that the set $S_f$ of non-properness of $f$ is covered by parametric curves of degree at most $d-1$. This bound is best possible. Moreover, we prove that if $X\subset\mathbb{R}^n$ is a closed algebraic set covered by parametric curves, and $f: X\rightarrow\mathbb{R}^m$ is a generically finite polynomial map, then the set $S_f$ of non-properness of $f$ is also covered by parametric curves. Moreover, if $X$ is covered by parametric curves of degree at most $d_1$, and the map $f$ has degree $d_2$, then the set $S_f$ is covered by parametric curves of degree at most $2d_1d_2$. As an application of this result we show a real version of the Bia{\l}ynicki-Birula theorem: Let $G$ be a real, non-trivial, connected, unipotent group which acts effectively and polynomially on a connected smooth algebraic variety $X\subset\mathbb{R}^n$. Then the set $Fix(G)$ of fixed points has no isolated points., Comment: final version, 13 pages

Maximally entangled Eisert-Lewenstein-Wilkens games are analyzed. For a general class of gate operators defined in the previous papers of the first author the general conditions are derived which allow to determine the form of gate operators leading to maximally entangled games. The construction becomes particularly simple provided one does distinguish between games differing by relabelling of strategies. Some examples are presented., Comment: 20 pages, no figures, appendix added, references added, concluding remarks extended

We present a method of constructing non-normal very ample polytopes as a segmental fibration of unimodular graph polytopes. In many cases we explicitly compute their invariants - Hilbert function, Ehrhart polynomial, gap vector. In particular, we answer several questions posed by Beck, Cox, Delgado, Gubeladze, Haase, Hibi, Higashitani and Maclagan.