Search

We introduce a graph Ramsey game called Ramsey, Paper, Scissors. This game has two players, Proposer and Decider. Starting from an empty graph on $n$ vertices, on each turn Proposer proposes a potential edge and Decider simultaneously decides (without knowing Proposer's choice) whether to add it to the graph. Proposer cannot propose an edge which would create a triangle in the graph. The game ends when Proposer has no legal moves remaining, and Proposer wins if the final graph has independence number at least $s$. We prove a threshold phenomenon exists for this game by exhibiting randomized strategies for both players that are optimal up to constants. Namely, there exist constants $0B\sqrt{n}\log{n}$. This is a factor of $\Theta(\sqrt{\log{n}})$ larger than the lower bound coming from the off-diagonal Ramsey number $r(3,s)$.

O. Einstein (2008) proved Bollob\'as-type theorems on intersecting families of ordered sets of finite sets and subspaces. Unfortunately, we report that the proof of a theorem on ordered sets of subspaces had a mistake. We prove two weaker variants., Comment: 6 pages. Improved bound for Theorem 4

Leonetti proved that whenever $${\mathcal {I}}$$ is an ideal on $${\mathbb {N}}$$ such that there exists an uncountable family of sets that are not in $${\mathcal {I}}$$ with the property that the intersection of any two distinct members of that family is in $${\mathcal {I}}$$ , then the space $$c_{0,{\mathcal {I}}}$$ of sequences in $$\ell _\infty $$ that converge to 0 along $${\mathcal {I}}$$ is not complemented. We provide a shorter proof of a more general fact that the quotient space $$\ell _\infty / c_{0,{\mathcal {I}}}$$ does not even embed into $$\ell _\infty $$ .

The aim of this paper is to discuss the main result in the paper by D.Y. Gao and X. Lu [On the extrema of a nonconvex functional with double-well potential in 1D, Z. Angew. Math. Phys. (2016) 67:62]. More precisely we provide a detailed study of the problem considered in that paper, pointing out the importance of the norm on the space $C^{1}[a,b]$; because no norm (topology) is mentioned on $C^{1}[a,b]$ we look at it as being a subspace of $W^{1,p}(a,b)$ for $p\in [1,\infty]$ endowed with its usual norm. We show that the objective function has not local extrema with the mentioned constraints for $p\in [1,4)$, and has (up to an additive constant) only a local maximizer for $p=\infty$, unlike the conclusion of the main result of the discussed paper where it is mentioned that there are (up to additive constants) two local minimizers and a local maximizer. We also show that the same conclusions are valid for the similar problem treated in the preprint by X. Lu and D.Y. Gao [On the extrema of a nonconvex functional with double-well potential in higher dimensions, arXiv:1607.03995]., 12 pages; in this version we added the forgotten condition $F(x) \ne 0$ for $x\in (a,b)$ on page 3

Let $\alpha:[0,1]\to [0,1]$ be a measurable function. It was proved by P. Marchal \cite{Mar15} that the function $$ \phi^{(\alpha)}(\lambda):=\exp\left[ \int_0^1\frac{\lambda-1}{1+(\lambda-1)x}\,\alpha(x)\,d x \right],\quad \lambda>0 $$ is a special Bernstein function. Marchal used this to construct, on a single probability space, a family of regenerative sets $\mathcal R^{(\alpha)}$ such that $\mathcal{R}^{(\alpha)} \stackrel{\text{law}}{=} \overline{\{S^{(\alpha)}_t:t\geq 0\}}$ ($S^{(\alpha)}$ is the subordinator with Laplace exponent $\phi^{(\alpha)}$) and $\mathcal R^{(\alpha)}\subset \mathcal R^{(\beta)}$ whenever $\alpha\leq\beta$. We give two simple proofs showing that $\phi^{(\alpha)}$ is a complete Bernstein function and extend Marchal's construction to all complete Bernstein functions., Comment: to appear in Electron. Comm. Probab

In this short paper, we derive an alternative proof for some known (van den Berg & Gilkey 2015) short-time asymptotics of the heat content in a compact full-dimensional submanifolds S with smooth boundary. This includes formulae like $$\begin{aligned} \int _{S} \exp (t\Delta ) (f \mathbb {1}_{S}) \,\mathrm {d}V= \int _S f \,\mathrm {d}V- \sqrt{\frac{t}{\pi }} \int _{\partial S} f \,\mathrm {d}A+ o(\sqrt{t}),\quad t \rightarrow 0^+, \end{aligned}$$ ∫ S exp ( t Δ ) ( f 1 S ) d V = ∫ S f d V - t π ∫ ∂ S f d A + o ( t ) , t → 0 + , and explicit expressions for similar expansions involving other powers of $$\sqrt{t}$$ t . By the same method, we also obtain short-time asymptotics of $$\int _S \exp (t^m\Delta ^m)(f \mathbb {1}_S)\,\mathrm {d}V$$ ∫ S exp ( t m Δ m ) ( f 1 S ) d V , $$m \in \mathbb N$$ m ∈ N , and more generally for one-parameter families of operators $$t \mapsto k(\sqrt{-t\Delta })$$ t ↦ k ( - t Δ ) defined by an even Schwartz function k.

In the gas station problem we want to find the cheapest path between two vertices of an n-vertex graph. Our car has a specific fuel capacity and at each vertex we can fill our car with gas, with the fuel cost depending on the vertex. Furthermore, we are allowed at most Δ stops for refuelling. In this short paper we provide an algorithm solving the problem in O ( Δ n 2 + n 2 log ⁡ n ) steps improving an earlier result by Khuller, Malekian and Mestre.

The traveling salesman problem (TSP) is one of the most prominent combinatorial optimization problems. Given a complete graph \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G = (V, E)$$\end{document}G=(V,E) and non-negative distances d for every edge, the TSP asks for a shortest tour through all vertices with respect to the distances d. The method of choice for solving the TSP to optimality is a branch and cut approach. Usually the integrality constraints are relaxed first and all separation processes to identify violated inequalities are done on fractional solutions. In our approach we try to exploit the impressive performance of current ILP-solvers and work only with integer solutions without ever interfering with fractional solutions. We stick to a very simple ILP-model and relax the subtour elimination constraints only. The resulting problem is solved to integer optimality, violated constraints (which are trivial to find) are added and the process is repeated until a feasible solution is found. In order to speed up the algorithm we pursue several attempts to find as many relevant subtours as possible. These attempts are based on the clustering of vertices with additional insights gained from empirical observations and random graph theory. Computational results are performed on test instances taken from the TSPLIB95 and on random Euclidean graphs.

The purpose of this short paper is to show the invalidity of a Fourier series expansion of fractional order as derived by G. Jumarie in a series of papers. In his work the exponential functions einωx are replaced by the Mittag-Leffler functions Eα (i(nωx)α) , over the interval [0,Mα/ω] where 0 < ω < ∞ and Mα > 0 is the period of the function Eα (ixα) , i.e., Eα (ixα) = Eα (i(x +Mα)α) . He showed that any smooth periodic function f with period Mα/ω can be expanded in a Fourier-type series. We will show that the only possible period of the function Eα (ixα) is Mα = 0; hence the invalidity of any Fourier-type series expansion of f.

In this short paper, we consider the Once-reinforced random walk with reinforcement parameter $a$ on trees with bounded degree which are transient for the simple random walk. On each of these trees, we prove that there exists an explicit critical parameter $a_{0}$ such that the Once-reinforced random walk is almost surely recurrent if $a>a_{0}$ and almost surely transient if $a

Let $G=(V,E)$ be a connected finite graph. In this short paper, we reinvestigate the Kazdan-Warner equation $$\Delta u=c-he^u$$ with $cc>c_-(h)$ and it is not solvable for $c-\infty$, then there exists at least one solution to the Kazdan-Warner equation with $c=c_-(h)$., Comment: 7 pages

In this short paper, we extend the classical Hoffman-Meeks Halfspace Theorem [Hoffman and Meeks, 'The strong halfspace theorem for minimal surfaces', Invent. Math. 101 (1990) 373-377] to self-shrinkers, that is: Let $P$ be a hyperplane passing through the origin. The only properly immersed self-shrinker $\Sigma $ contained in one of the closed half-space determined by $P$ is $\Sigma = P$. Our proof is geometric and uses a catenoid type hypersurface discovered by Kleene-Moller [Kleene and Moller, 'Self-shrinkers with a rotational symmetry', Trans. Amer. Math. Soc. 366 (2014) 3943-3963]. Also, using a similar geometric idea, we obtain that the only self-shrinker properly immersed in an closed cylinder $ \overline {B^{k+1} (R)} \times {\mathbb R}^{n-k}\subset {\mathbb R}^{n+1}$, for some $k\in \{1, \ldots, n\}$ and radius $R$, $R \leqslant \sqrt {2k}$, is the cylinder ${\mathbb S}^k (\sqrt {2k}) \times {\mathbb R}^{n-k}$. We also extend the above results for $\lambda $-hypersurfaces.

An asymmetric coloring of a graph is a coloring of its vertices that is not preserved by any non-identity automorphism of the graph. The motion of a graph is the minimal degree of its automorphism group, i.e., the minimum number of elements displaced by any non-identity automorphism. In this paper we confirm Tom Tucker's "Infinite Motion Conjecture" that connected locally finite graphs with infinite motion admit an asymmetric 2-coloring. We infer this from the more general result that the inverse limit of a sequence of finite permutation groups with disjoint domains, viewed as a permutation group on the union of those domains, admits an asymmetric 2-coloring. The proof is based on the study of the interaction between epimorphisms of finite permutation groups and the structure of the setwise stabilizers of subsets of their domains., Comment: V.2 updates: Choi 1972 ref. added, Sec. 8.3 (Mathieu groups) updated, question about $M_{24}$ deleted from "Open questions." New material: New Sec. 14 added, incl. two conjectures. Minor changes made for improved clarity throughout the paper. None of the updates affects the main results or their proofs

An {\em orientation} of an undirected graph $G$ is an assignment of exactly one direction to each edge of $G$. Converting two-way traffic networks to one-way traffic networks and bidirectional communication networks to unidirectional communication networks are practical instances of graph orientations. In these contexts minimising the diameter of the resulting oriented graph is of prime interest. The $n$-star network topology was proposed as an alternative to the hypercube network topology for multiprocessor systems by Akers and Krishnamurthy [IEEE Trans. on Computers (1989)]. The $n$-star graph $S_n$ consists of $n!$ vertices, each labelled with a distinct permutation of $[n]$. Two vertices are adjacent if their labels differ exactly in the first and one other position. $S_n$ is an $(n-1)$-regular, vertex-transitive graph with diameter $\lfloor 3(n-1)/2 \rfloor$. Orientations of $S_n$, called unidirectional star graphs and distributed routing protocols over them were studied by Day and Tripathi [Information Processing Letters (1993)] and Fujita [The First International Symposium on Computing and Networking (CANDAR 2013)]. Fujita showed that the (directed) diameter of this unidirectional star graph $\overrightarrow{S_n}$ is at most $\lceil{5n/2}\rceil + 2$. In this paper, we propose a new distributed routing algorithm for the same $\overrightarrow{S_n}$ analysed by Fujita, which routes a packet from any node $s$ to any node $t$ at an undirected distance $d$ from $s$ using at most $\min\{4d+4, 2n+4\}$ hops. This shows that the (directed) diameter of $\overrightarrow{S_n}$ is at most $2n+4$. We also show that the diameter of $\overrightarrow{S_n}$ is at least $2n$ when $n \geq 7$, thereby showing that our upper bound is tight up to an additive factor., Full version of the paper to be presented in CALDAM 2020

A $(k,g)$-cage is a $k$-regular simple graph of girth $g$ with minimum possible number of vertices. In this paper, $(k,g)$-cages which are Moore graphs are referred as minimal $(k,g)$-cages. A simple connected graph is called distance regular(DR) if all its vertices have the same intersection array. A bipartite graph is called distance biregular(DBR) if all the vertices of the same partite set admit the same intersection array. It is known that minimal $(k,g)$-cages are DR graphs and their subdivisions are DBR graphs. In this paper, for minimal $(k,g)$-cages we give a formula for distance spectral radius in terms of $k$ and $g$, and also determine polynomials of degree $[\frac{g}{2}]$, which is the diameter of the graph. This polynomial gives all distance eigenvalues when the variable is substituted by adjacency eigenvalues. We show that a minimal $(k,g)$-cage of diameter $d$ has $d+1$ distinct distance eigenvalues, and this partially answers a problem posed in [5]. We prove that every DBR graph is a $2$-partitioned transmission regular graph and then give a formula for its distance spectral radius. By this formula we obtain the distance spectral radius of subdivision of minimal $(k,g)$-cages. Finally we determine the full distance spectrum of subdivision of some minimal $(k,g)$-cages., 22 pages

The maximum k-colorable subgraph (MkCS) problem is to find an induced k-colorable subgraph with maximum cardinality in a given graph. This paper is an in-depth analysis of the MkCS problem that considers various semidefinite programming relaxations, including their theoretical and numerical comparisons. To simplify these relaxations, we exploit the symmetry arising from permuting the colors, as well as the symmetry of the given graphs when applicable. We also show how to exploit invariance under permutations of the subsets for other partition problems and how to use the MkCS problem to derive bounds on the chromatic number of a graph. Our numerical results verify that the proposed relaxations provide strong bounds for the MkCS problem and that those outperform existing bounds for most of the test instances. Summary of Contribution: The maximum k-colorable subgraph (MkCS) problem is to find an induced k-colorable subgraph with maximum cardinality in a given graph. The MkCS problem has a number of applications, such as channel assignment in spectrum sharing networks (e.g., Wi-Fi or cellular), very-large-scale integration design, human genetic research, and so on. The MkCS problem is also related to several other optimization problems, including the graph partition problem and the max-k-cut problem. The two mentioned problems have applications in parallel computing, network partitioning, floor planning, and so on. This paper is an in-depth analysis of the MkCS problem that considers various semidefinite programming relaxations, including their theoretical and numerical comparisons. Further, our analysis relates the MkCS results with the stable set and the chromatic number problems. We provide extended numerical results that verify that the proposed bounding approaches provide strong bounds for the MkCS problem and that those outperform existing bounds for most of the test instances. Moreover, our lower bounds on the chromatic number of a graph are competitive with existing bounds in the literature.

A hypergraph is Sperner if no hyperedge contains another one. A Sperner hypergraph is equilizable (resp., threshold) if the characteristic vectors of its hyperedges are the (minimal) binary solutions to a linear equation (resp., inequality) with positive coefficients. These combinatorial notions have many applications and are motivated by the theory of Boolean functions and integer programming. We introduce in this paper the class of $1$-Sperner hypergraphs, defined by the property that for every two hyperedges the smallest of their two set differences is of size one. We characterize this class of Sperner hypergraphs by a decomposition theorem and derive several consequences from it. In particular, we obtain bounds on the size of $1$-Sperner hypergraphs and their transversal hypergraphs, show that the characteristic vectors of the hyperedges are linearly independent over the reals, and prove that $1$-Sperner hypergraphs are both threshold and equilizable. The study of $1$-Sperner hypergraphs is motivated also by their applications in graph theory, which we present in a companion paper.

It was shown by Mukai that the maximum order of a finite group acting faithfully and symplectically on a K3 surface is $960$ and that the group is isomorphic to the group $M\_{20}$. Then Kondo showed that the maximum order of a finite group acting faithfully on a K3 surface is $3\,840$ and this group contains the Mathieu group $M\_{20}$ with index four. Kondo also showed that there is a unique K3 surface on which this group acts faithfully, which is the Kummer surface $\Km(E\_i\times E\_i)$. In this paper we describe two more K3 surfaces admitting a big finite automorphism group of order $1\,920$, both groups contains $M\_{20}$ as a subgroup of index 2. We show moreover that these two groups and the two K3 surfaces are unique. This result was shown independently by S. Brandhorst and K. Hashimoto in a forthcoming paper, with the aim of classifying all the finite groups acting faithfully on K3 surfaces with maximal symplectic part., 15 pages

A combinatorial polytope $P$ is said to be projectively unique if it has a single realization up to projective transformations. Projective uniqueness is a geometrically compelling property but is difficult to verify. In this paper, we merge two approaches to projective uniqueness in the literature. One is primarily geometric and is due to McMullen, who showed that certain natural operations on polytopes preserve projective uniqueness. The other is more algebraic and is due to Gouveia, Macchia, Thomas, and Wiebe. They use certain ideals associated to a polytope to verify a property called graphicality that implies projective uniqueness. In this paper, we show that that McMullen's operations preserve not only projective uniquness but also graphicality. As an application, we show that large families of order polytopes are graphic and thus projectively unique.

The stochastic block model (SBM) is a random graph model in which the edges are generated according to the underlying cluster structure on the vertices. The (ferromagnetic) Ising model, on the other hand, assigns $\pm 1$ labels to vertices according to an underlying graph structure in a way that if two vertices are connected in the graph then they are more likely to be assigned the same label. In SBM, one aims to recover the underlying clusters from the graph structure while in Ising model, an extensively-studied problem is to recover the underlying graph structure based on i.i.d. samples (labelings of the vertices). In this paper, we propose a natural composition of SBM and the Ising model, which we call the Stochastic Ising Block Model (SIBM). In SIBM, we take SBM in its simplest form, where $n$ vertices are divided into two equal-sized clusters and the edges are connected independently with probability $p$ within clusters and $q$ across clusters. Then we use the graph $G$ generated by the SBM as the underlying graph of the Ising model and draw $m$ i.i.d. samples from it. The objective is to exactly recover the two clusters in SBM from the samples generated by the Ising model, without observing the graph $G$. As the main result of this paper, we establish a sharp threshold $m^\ast$ on the sample complexity of this exact recovery problem in a properly chosen regime, where $m^\ast$ can be calculated from the parameters of SIBM. We show that when $m\ge m^\ast$, one can recover the clusters from $m$ samples in $O(n)$ time as the number of vertices $n$ goes to infinity. When $m, Comment: Fixed a gap in the original proof of Theorem 5. The new proof of Theorem 5 relies on Lemma 5, which is the main new element in this version

The paper is devoted to coverings by translative homothets and illuminations of convex bodies. For a given positive number $\alpha$ and a convex body $B$, $g_{\alpha}(B)$ is the infimum of $\alpha$-powers of finitely many homothety coefficients less than 1 such that there is a covering of $B$ by translative homothets with these coefficients. $h_{\alpha}(B)$ is the minimal number of directions such that the boundary of $B$ can be illuminated by this number of directions except for a subset whose Hausdorff dimension is less than $\alpha$. In this paper, we prove that $g_{\alpha}(B)\leq h_{\alpha}(B)$, find upper and lower bounds for both numbers, and discuss several general conjectures. In particular, we show that $h_{\alpha} (B) > 2^{d-\alpha}$ for almost all $\alpha$ and $d$ when $B$ is the $d$-dimensional cube, thus disproving the conjecture from Research Problems in Discrete Geometry by Brass, Moser, and Pach.

The signed permutation modules are a simultaneous generalization of the ordinary permutation modules and the twisted permutation modules of the symmetric group. In a recent paper Dave Benson and Peter Symonds defined a new invariant $\gamma_G(M)$ for a finite dimensional module $M$ of a finite group $G$ which attempts to quantify how close a module is to being projective. In this paper, we determine this invariant for all the signed permutation modules of the symmetric group using tools from representation theory and combinatorics., Comment: 14 pages. arXiv admin note: substantial text overlap with arXiv:2012.00341

In this paper we determine two asymptotic results for Jack measures on partitions, a model defined by two specializations of Jack polynomials proposed by Borodin-Olshanski in [European J. Combin. 26.6 (2005): 795-834]. Assuming these two specializations are the same, we derive limit shapes and Gaussian fluctuations for the anisotropic profiles of these random partitions in three asymptotic regimes associated to diverging, fixed, and vanishing values of the Jack parameter. To do so, we introduce a generalization of Motzkin paths we call "ribbon paths", show for general Jack measures that certain joint cumulants are weighted sums of connected ribbon paths on $n$ sites with $n-1+g$ pairings, and derive our two results from the contributions of $(n,g)=(1,0)$ and $(2,0)$, respectively. Our analysis makes use of Nazarov-Sklyanin's spectral theory for Jack polynomials. As a consequence, we give new proofs of several results for Schur measures, Plancherel measures, and Jack-Plancherel measures. In addition, we relate our weighted sums of ribbon paths to the weighted sums of ribbon graphs of maps on non-oriented real surfaces recently introduced by Chapuy-Dol\k{e}ga., Comment: Several results in this paper first appeared in the author's unpublished monograph arXiv:1508.03063. Version 2: revised and accepted for publication in International Mathematics Research Notices (IMRN)

Consider an oriented curve $\Gamma$ in a domain $D$ in the plane $\boldsymbol R^2$. Thinking of $D$ as a piece of paper, one can make a curved folding in the Euclidean space $\boldsymbol R^3$. This can be expressed as the image of an "origami map" $\Phi:D\to \boldsymbol R^3$ such that $\Gamma$ is the singular set of $\Phi$, the word "origami" coming from the Japanese term for paper folding. We call the singular set image $C:=\Phi(\Gamma)$ the crease of $\Phi$ and the singular set $\Gamma$ the crease pattern of $\Phi$. We are interested in the number of origami maps whose creases and crease patterns are $C$ and $\Gamma$, respectively. Two such possibilities have been known. In the authors' previous work, two other new possibilities and an explicit example with four such non-congruent distinct curved foldings were established. In this paper, we determine the possibility of the number $N$ of congruence classes of curved foldings with the same crease and crease pattern. As a consequence, if $C$ is a non-closed simple arc, then $N=4$ if and only if both $\Gamma$ and $C$ do not admit any symmetries. On the other hand, when $C$ is a closed curve, there are infinitely many distinct possibilities for curved foldings with the same crease and crease pattern, in general., Comment: 29 pages, 7 figures

We prove that the spaces $\operatorname{tot}\big(\Gamma(\Lambda^\bullet A^\vee \otimes_R\mathcal{T}_{\operatorname{poly}}^{\bullet}\big)$ and $\operatorname{tot}\big(\Gamma(\Lambda^\bullet A^\vee)\otimes_R\mathcal{D}_{\operatorname{poly}}^{\bullet}\big)$ associated with a Lie pair $(L,A)$ each carry an $L_\infty$ algebra structure canonical up to an $L_\infty$ isomorphism with the identity map as linear part. These two spaces serve, respectively, as replacements for the spaces of formal polyvector fields and formal polydifferential operators on the Lie pair $(L,A)$. Consequently, both $\mathbb{H}^\bullet_{\operatorname{CE}}(A,\mathcal{T}_{\operatorname{poly}}^{\bullet})$ and $\mathbb{H}^\bullet_{\operatorname{CE}}(A,\mathcal{D}_{\operatorname{poly}}^{\bullet})$ admit unique Gerstenhaber algebra structures. Our approach is based on homotopy transfer and the construction of a Fedosov dg Lie algebroid (i.e. a dg foliation on a Fedosov dg manifold)., Comment: [v2] 50 pages, paper was expanded; [v1] Paper arXiv:1605.09656v1 was expended and split into two papers. The first part is arXiv:1605.09656v2. The second part is the present paper. A new result addressing uniqueness of the constructed structures has been added

In this paper we are interested in the asymptotic enumeration of Cayley graphs. It has previously been shown that almost every Cayley digraph has the smallest possible automorphism group: that is, it is a digraphical regular representation (DRR). In this paper, we approach the corresponding question for undirected Cayley graphs. The situation is complicated by the fact that there are two infinite families of groups that do not admit any graphical regular representation (GRR). The strategy for digraphs involved analysing separately the cases where the regular group $R$ has a nontrivial proper normal subgroup $N$ with the property that the automorphism group of the digraph fixes each $N$-coset setwise, and the cases where it does not. In this paper, we deal with undirected graphs in the case where the regular group has such a nontrivial proper normal subgroup., Comment: 27 pages

When the reduced twisted $C^*$-algebra $C^*_r(\mathcal{G}, c)$ of a non-principal groupoid $\mathcal{G}$ admits a Cartan subalgebra, Renault's work on Cartan subalgebras implies the existence of another groupoid description of $C^*_r(\mathcal{G}, c)$. In an earlier paper, joint with Reznikoff and Wright, we identified situations where such a Cartan subalgebra arises from a subgroupoid $\mathcal{S}$ of $\mathcal{G}$. In this paper, we study the relationship between the original groupoids $\mathcal{S}, \mathcal{G}$ and the Weyl groupoid and twist associated to the Cartan pair. We first identify the spectrum $\mathfrak{B}$ of the Cartan subalgebra $C^*_r(\mathcal{S}, c)$. We then show that the quotient groupoid $\mathcal{G}/\mathcal{S}$ acts on $\mathfrak{B}$, and that the corresponding action groupoid is exactly the Weyl groupoid of the Cartan pair. Lastly we show that, if the quotient map $\mathcal{G}\to\mathcal{G}/\mathcal{S}$ admits a continuous section, then the Weyl twist is also given by an explicit continuous $2$-cocycle on $\mathcal{G}/\mathcal{S} \ltimes \mathfrak{B}$., 32 pages

We compare crystal combinatorics of the level 2 Fock space with the classification of unitary irreducible representations of type B rational Cherednik algebras to study how unitarity behaves under parabolic restriction. First, we show that any finite-dimensional unitary irreducible representation of such an algebra is labeled by a bipartition consisting of a rectangular partition in one component and the empty partition in the other component. This is a new proof of a result that can be deduced from theorems of Montarani and Etingof-Stoica. Second, we show that the crystal operators that remove boxes preserve the combinatorial conditions for unitarity, and that the parabolic restriction functors categorifying the crystals send irreducible unitary representations to unitary representations. Third, we find the supports of the unitary representations., This paper supersedes arXiv:1907.00919 and contains that paper as a subsection. 35 pages, some color figures

In 1993, Shub and Smale posed the problem of finding a sequence of univariate polynomials of degree $N$ with condition number bounded above by $N$. In a previous paper by C. Belt\'an, U. Etayo, J. Marzo and J. Ortega-Cerd\`a, it was proved that the optimal value of the condition number is of the form $O(\sqrt{N})$, and the sequence demanded by Shub and Smale was described by a closed formula (for large enough $N\geqslant N_0$ with $N_0$ unknown) and by a search algorithm for the rest of the cases. In this paper we find concrete estimates for the constant hidden in the $O(\sqrt{N})$ term and we describe a simple formula for a sequence of polynomials whose condition number is at most $N$, valid for all $N=4M^2$, with $M$ a positive integer., Comment: 21 pages

A complex unit gain graph ($\mathbb{T}$-gain graph), $\Phi = (G, \varphi)$ is a graph where the function $\varphi$ assigns a unit complex number to each orientation of an edge of $G$, and its inverse is assigned to the opposite orientation. A $ \mathbb{T} $-gain graph $\Phi$ is balanced if the product of the edge gains of each cycle (with a fixed orientation) is $1$. Signed graphs are special cases of $\mathbb{T}$-gain graphs. The adjacency matrix of $\Phi$, denoted by $ \mathbf{A}(\Phi)$ is defined canonically. The gain Laplacian for $\Phi$ is defined as $\mathbf{L}(\Phi) = \mathbf{D}(\Phi) - \mathbf{A}(\Phi)$, where $\mathbf{D}(\Phi)$ is the diagonal matrix with diagonal entries are the degrees of the vertices of $G$. The minimum number of vertices (resp., edges) to be deleted from $\Phi$ in order to get a balanced gain graph the frustration number (resp, frustration index). We show that frustration number and frustration index are bounded below by the smallest eigenvalue of $\mathbf{L}(\Phi)$. We provide several lower and upper bounds for extremal eigenvalues of $\mathbf{L}(\Phi)$ in terms of different graph parameters such as the number of edges, vertex degrees, and average $2$-degrees. The signed graphs are particular cases of the $\mathbb{T}$-gain graphs, all the bounds established in paper hold for signed graphs. Most of the bounds established here are new for signed graphs. Finally, we perform comparative analysis for all the obtained bounds in the paper with the state-of-the-art bounds available in the literature for randomly generated Erd\H{o}s-Re\'yni graphs. Some of the major highlights of our paper are the gain-dependent bounds, limit convergence of the bounds to the extremal eigenvalues, and optimal extremal bounds obtained by posing optimization problems to achieve the best possible bounds., Comment: Preliminary version. 32 pages

It is known that every graph of sufficiently large chromatic number and bounded clique number contains, as an induced subgraph , a subdivision of any fixed forest, and a subdivision of any fixed cycle. Equivalently, every forest is pervasive, and K 3 is pervasive, in the class of all graphs, where we say a graph H is “pervasive” (in some class of graphs) if for all l ≥ 1 , every graph in the class of bounded clique number and sufficiently large chromatic number has an induced subgraph that is a subdivision of H, in which every edge of H is replaced by a path of at least l edges. Which other graphs are pervasive? It was proved by Chalopin, Esperet, Li and Ossona de Mendez that every such graph is a “forest of lanterns”: roughly, every block is a “lantern”, a graph obtained from a tree by adding one extra vertex, and there are rules about how the blocks fit together. It is not known whether every forest of lanterns is pervasive in the class of all graphs; but in another paper two of us prove that all “banana trees” are pervasive, that is, multigraphs obtained from a forest by adding parallel edges, thus generalizing the two results above. This paper contains the first half of the proof, which works for any forest of lanterns, not just for banana trees. Say a class of graphs is “ρ-controlled” if for every graph in the class, its chromatic number is at most some function (determined by the class) of the largest chromatic number of a ρ-ball in the graph. In this paper we prove that for every ρ ≥ 2 , and for every ρ-controlled class, every forest of lanterns is pervasive in this class. These results turn out particularly nicely when applied to string graphs. A “chandelier” is a special lantern, a graph obtained from a tree by adding a vertex adjacent to precisely the leaves of the tree. A “string graph” is the intersection graph of a set of curves in the plane. There are string graphs with clique number two and chromatic number arbitrarily large. We prove that the class of string graphs is 2-controlled, and consequently every forest of lanterns is pervasive in this class; but in fact something stronger is true, that every string graph of sufficiently large chromatic number and bounded clique number contains each fixed chandelier as an induced subgraph (not just as a subdivision); and the same for most forests of chandeliers (there is an extra condition on how the blocks are attached together).

The partition crank is a statistic on partitions introduced by Freeman Dyson to explain Ramanujan's congruences. In this paper, we prove that the crank is asymptotically equidistributed modulo Q, for any odd number Q. To prove this, we obtain effective bounds on the error term from Zapata Rolon's asymptotic estimate for the crank function. We then use those bounds to prove the surjectivity and strict log-subadditivity of the crank function., 14 pages 1) Some clarifications and corrections have been made. 2) This paper will appear in Ramanujan Journal

In this paper we prove that a nodal hypersurface in P^4 with defect has at least (d-1)^2 nodes, and if it has at most 2(d-2)(d-1) nodes and d>6 then it contains either a plane or a quadric surface. Furthermore, we prove that a nodal double cover of P^3 ramified along a surface of degree 2d with defect has at least d(2d-1) nodes. We construct the largest dimensional family of nodal degree d hypersurfaces in P^(2n+2) with defect for d sufficiently large., v2: A proof for the Ciliberto-Di Gennaro conjecture is added (Section 5); Some minor corrections in the other sections. v3: some minor corrections in the abstract v4: The proof for the Ciliberto-Di Gennaro conjecture has been modified; The paper is split into two parts, the complete intersection case will be discussed in a different paper

Preferential attachment networks are a type of random network where new nodes are connected to existing ones at random, and are more likely to connect to those that already have many connections. We investigate further a family of models introduced by Antunovi\'{c}, Mossel and R\'{a}cz where each vertex in a preferential attachment graph is assigned a type, based on the types of its neighbours. Instances of this type of process where the proportions of each type present do not converge over time seem to be rare. Previous work found that a "rock-paper-scissors" setup where each new node's type was determined by a rock-paper-scissors contest between its two neighbours does not converge. Here, two cases similar to that are considered, one which is like the above but with an arbitrarily small chance of picking a random type and one where there are four neighbours which perform a knockout tournament to determine the new type. These two new setups, despite seeming very similar to the rock-paper-scissors model, do in fact converge, perhaps surprisingly., Comment: 7 pages, 2 figures

Let $$\alpha = (1+\sqrt{5})/2$$ and define the lower and upper Wythoff sequences by $$a_i = \lfloor i \alpha \rfloor $$ , $$b_i = \lfloor i \alpha ^2 \rfloor $$ for $$i \ge 1$$ . In a recent interesting paper, Kawsumarng et al. proved a number of results about numbers representable as sums of the form $$a_i + a_j$$ , $$b_i + b_j$$ , $$a_i + b_j$$ , and so forth. In this paper I show how to derive all of their results, using one simple idea and existing free software called Walnut. The key idea is that for each of their sumsets, there is a relatively small automaton accepting the Fibonacci representation of the numbers represented. I also show how the automaton approach can easily prove other results.

It is known that the generating function f of a sequence of Toeplitz matrices {Tn(f)}n may not describe the asymptotic distribution of the eigenvalues of Tn(f) if f is not real. In this paper, we assume as a working hypothesis that, if the eigenvalues of Tn(f) are real for all n, then they admit an asymptotic expansion of the same type as considered in previous works, where the first function, called the eigenvalue symbol $\mathfrak {f}$ f , appearing in this expansion is real and describes the asymptotic distribution of the eigenvalues of Tn(f). This eigenvalue symbol $\mathfrak {f}$ f is in general not known in closed form. After validating this working hypothesis through a number of numerical experiments, we propose a matrix-less algorithm in order to approximate the eigenvalue distribution function $\mathfrak {f}$ f . The proposed algorithm, which opposed to previous versions, does not need any information about neither f nor $\mathfrak {f}$ f is tested on a wide range of numerical examples; in some cases, we are even able to find the analytical expression of $\mathfrak {f}$ f . Future research directions are outlined at the end of the paper.

Slice Fueter-regular functions, originally called slice Dirac-regular functions, are generalized holomorphic functions defined over the octonion algebra $\mathbb{O}$, recently introduced by M. Jin, G. Ren and I. Sabadini. A function $f:\Omega_D\subset\mathbb{O}\to\mathbb{O}$ is called (quaternionic) slice Fueter-regular if, given any quaternionic subalgebra $\mathbb{H}_\mathbb{I}$ of $\mathbb{O}$ generated by a pair $\mathbb{I}=(I,J)$ of orthogonal imaginary units $I$ and $J$ ($\mathbb{H}_\mathbb{I}$ is a `quaternionic slice' of $\mathbb{O}$), the restriction of $f$ to $\Omega_D\cap\mathbb{H}_\mathbb{I}$ belongs to the kernel of the corresponding Cauchy-Riemann-Fueter operator $\frac{\partial}{\partial x_0}+I\frac{\partial}{\partial x_1}+J\frac{\partial}{\partial x_2}+(IJ)\frac{\partial}{\partial x_3}$. The goal of this paper is to show that slice Fueter-regular functions are standard (complex) slice functions, whose stem functions satisfy a Vekua system having exactly the same form of the one characterizing axially monogenic functions of degree zero. The mentioned standard sliceness of slice Fueter-regular functions is able to reveal their `holomorphic nature': slice Fueter-regular functions have Cauchy integral formulas, Taylor and Laurent series expansions, and a version of Maximum Modulus Principle, and each of these properties is global in the sense that it is true on genuine $8$-dimesional domains of $\mathbb{O}$. Slice Fueter-regular functions are real analytic. Furthermore, we introduce the global concepts of spherical Dirac operator $\Gamma$ and of slice Fueter operator $\bar{\vartheta}_F$ over octonions, which allow to characterize slice Fueter-regular functions as the $\mathscr{C}^2$-functions in the kernel of $\bar{\vartheta}_F$ satisfying a second order differential system associated with $\Gamma$. The paper contains eight open problems., Comment: 33 pages

Let us fix a prime $p$. The Erd\H{o}s-Ginzburg-Ziv problem asks for the minimum integer $s$ such that any collection of $s$ points in the lattice $\mathbb{Z}^n$ contains $p$ points whose centroid is also a lattice point in $\mathbb{Z}^n$. For large $n$, this is essentially equivalent to asking for the maximum size of a subset of $\mathbb{F}_p^n$ without $p$ distinct elements summing to zero. In this paper, we give a new upper bound for this problem for any fixed prime $p\geq 5$ and large $n$. In particular, we prove that any subset of $\mathbb{F}_p^n$ without $p$ distinct elements summing to zero has size at most $C_p\cdot \left(2\sqrt{p}\right)^n$, where $C_p$ is a constant only depending on $p$. For $p$ and $n$ going to infinity, our bound is of the form $p^{(1/2)\cdot (1+o(1))n}$, whereas all previously known upper bounds were of the form $p^{(1-o(1))n}$ (with $p^n$ being a trivial bound). Our proof uses the so-called multi-colored sum-free theorem which is a consequence of the Croot-Lev-Pach polynomial method. This method and its consequences were already applied by Naslund as well as by Fox and the author to prove bounds for the problem studied in this paper. However, using some key new ideas, we significantly improve their bounds., Comment: 11 pages

In a paper from 2001 (Journal of the LMS), Diestel and Leader offered a proof that a connected graph has a normal spanning tree if and only if it does not contain a minor from two specific forbidden classes of graphs, all of cardinality $\aleph_1$. Unfortunately, their proof contains a gap, and their result is incorrect. In this paper, we construct a third type of obstruction: an $\aleph_1$-sized graph without a normal spanning tree that contains neither of the two types described by Diestel and Leader as a minor. Further, we show that any list of forbidden minors characterising the graphs with normal spanning trees must contain graphs of arbitrarily large cardinality., Comment: 9 pages. arXiv admin note: text overlap with arXiv:2005.02833

The classical global criteria for the existence of Hamilton cycles only apply to graphs with large edge density and small diameter. In a series of papers Asratian and Khachatryan developed local criteria for the existence of Hamilton cycles in finite connected graphs, which are analogues of the classical global criteria due to Dirac (1952), Ore (1960), Jung (1978), and Nash-Williams (1971). The idea was to show that the global concept of Hamiltonicity can, under rather general conditions, be captured by local phenomena, using the structure of balls of small radii. (The ball of radius $r$ centered at a vertex $u$ is a subgraph of $G$ induced by the set of vertices whose distances from $u$ do not exceed $r$.) Such results are called localization theorems and present a possibility to extend known classes of finite Hamiltonian graphs. In this paper we formulate a general approach for finding localization theorems and use this approach to formulate local analogues of well-known results of Bauer et al. (1989), Bondy (1980), H\"aggkvist and Nicoghossian (1981), and Moon and Moser (1963). Finally we extend two of our results to infinite locally finite graphs and show that they guarantee the existence of Hamiltonian curves, introduced by K\"undgen, Li and Thomassen (2017)., Comment: 25 pages, 3 figures

Let $S \subset \Bbb R^n$ be a smooth compact hypersurface with a strictly positive second fundamental form, $E$ be the Fourier extension operator on $S$, and $X$ be a Lebesgue measurable subset of $\Bbb R^n$. If $X$ contains a ball of each radius, then the problem of determining the range of exponents $(p,q)$ for which the estimate $\| Ef \|_{L^q(X)} \leq C \| f \|_{L^p(S)}$ holds is equivalent to the restriction conjecture. In this paper, we study the estimate under the following assumption on the set $X$: there is a number $0 < \alpha \leq n$ such that $|X \cap B_R| \leq c \, R^\alpha$ for all balls $B_R$ in $\Bbb R^n$ of radius $R \geq 1$. On the left-hand side of this estimate, we are integrating the function $|Ef(x)|^q$ against the measure $\chi_X dx$. Our approach consists of replacing the characteristic function $\chi_X$ of $X$ by an appropriate weight function $H$, and studying the resulting estimate in three different regimes: small values of $\alpha$, intermediate values of $\alpha$, and large values of $\alpha$. In the first regime, we establish the estimate by using already available methods. In the second regime, we prove a weighted H\"{o}lder-type inequality that holds for general non-negative Lebesgue measurable functions on $\Bbb R^n$, and combine it with the result from the first regime. In the third regime, we borrow a recent fractal Fourier restriction theorem of Du and Zhang and combine it with the result from the second regime. In the opposite direction, the results of this paper improve on the Du-Zhang theorem in the range $0 < \alpha < n/2$., Comment: 31 pages. Minor revision

For a separable finite diffuse measure space $${\mathcal {M}}$$ M and an orthonormal basis $$\{\varphi _n\}$$ { φ n } of $$L^2({\mathcal {M}})$$ L 2 ( M ) consisting of bounded functions $$\varphi _n\in L^\infty ({\mathcal {M}})$$ φ n ∈ L ∞ ( M ) , we find a measurable subset $$E\subset {\mathcal {M}}$$ E ⊂ M of arbitrarily small complement $$|{\mathcal {M}}{\setminus } E| | M \ E | < ϵ , such that every measurable function $$f\in L^1({\mathcal {M}})$$ f ∈ L 1 ( M ) has an approximant $$g\in L^1({\mathcal {M}})$$ g ∈ L 1 ( M ) with $$g=f$$ g = f on E and the Fourier series of g converges to g, and a few further properties. The subset E is universal in the sense that it does not depend on the function f to be approximated. Further in the paper this result is adapted to the case of $${\mathcal {M}}=G/H$$ M = G / H being a homogeneous space of an infinite compact second countable Hausdorff group. As a useful illustration the case of n-spheres with spherical harmonics is discussed. The construction of the subset E and approximant g is sketched briefly at the end of the paper.

A classical theorem of Koksma states that for Lebesgue almost every $x>1$ the sequence $(x^n)_{n=1}^{\infty}$ is uniformly distributed modulo one. In the present paper we extend Koksma's theorem to the pair correlation setting. More precisely, we show that for Lebesgue almost every $x>1$ the pair correlations of the fractional parts of $(x^n)_{n=1}^{\infty}$ are asymptotically Poissonian. The proof is based on a martingale approximation method., Version 2: some minor changes. The paper will appear in the Israel Journal of Mathematics

In Sarkozy (2001) the third author of this paper presented two conjectures on the additive decomposability of the sequence of ”smooth” (or ”friable”) numbers. Elsholtz and Harper (2015) proved (by using sieve methods) the second (less demanding) conjecture. The goal of this paper is to extend and sharpen their result in three directions by using a different approach (based on the theory of S -unit equations).

The concept of antimagic labelings of a graph is to produce distinct vertex sums by labeling edges through consecutive numbers starting from one. A long-standing conjecture is that every connected graph, except a single edge, is antimagic. Some graphs are known to be antimagic, but little has been known about sparse graphs, not even trees. This paper studies a weak version called $k$-shifted-antimagic labelings which allow the consecutive numbers starting from $k+1$, instead of starting from 1, where $k$ can be any integer. This paper establishes connections among various concepts proposed in the literature of antimagic labelings and extends previous results in three aspects: $\bullet$ Some classes of graphs, including trees and graphs whose vertices are of odd degrees, which have not been verified to be antimagic are shown to be $k$-shifted-antimagic for sufficiently large $k$. $\bullet$ Some graphs are proved $k$-shifted-antimagic for all $k$, while some are proved not for some particular $k$. $\bullet$ Disconnected graphs are also considered.

In this paper, we prove that for the oper stratification of the de Rham moduli space $M_{\mathrm{dR}}(X,r)$, the closed oper stratum is the unique minimal stratum with dimension $r^2(g-1)+g+1$, and the open dense stratum consisting of irreducible flat bundles with stable underlying vector bundles is the unique maximal stratum., Comment: This paper comes from the last section of arXiv:1905.10765v1 as an independent paper. Comments are welcome! To appear in manuscripta mathematica

In this paper we study 1/k geodesics, those closed geodesics that minimize on all subintervals of length $L/k$, where $L$ is the length of the geodesic. We develop new techniques to study the minimizing properties of these curves on doubled polygons, and demonstrate a sequence of doubled polygons whose closed geodesics exhibit unbounded minimizing properties. We also compute the length of the shortest closed geodesic on doubled odd-gons and show that this length approaches 4 times the diameter., Comment: This paper is a result of a SUMRY (REU) project at Yale

Text In this paper, we consider sums of generalized polygonal numbers with repeats, generalizing Fermat's polygonal number theorem which was proven by Cauchy. In particular, we obtain the minimal number of generalized m-gonal numbers required to represent every positive integer and we furthermore generalize this result to obtain optimal bounds when many of the generalized m-gonal numbers are repeated r times, where r ∈ N is fixed. Video For a video summary of this paper, please visit https://youtu.be/WRb91yye-IQ .

In this paper we consider a Condorcet domain (CD) formed by a rhombus tiling as a voting design and consider a problem of aggregation of voting designs using majority rule. A Condorcet super-domain is a collection of CDs obtained from rhombus tilings on a zonogone Z(n; 2) with the property that if voting designs (ballots) belong to this collection, then the simple majority rule does not yield cycles. A study of Condorcet super-domains and methods of constructing them form the main subject of this paper., 17 pages, 8 figures

Given a tournament $T$, a module of $T$ is a subset $M$ of $V(T)$ such that for $x, y\in M$ and $v\in V(T)\setminus M$, $(v,x)\in A(T)$ if and only if $(v,y)\in A(T)$. The trivial modules of $T$ are $\emptyset$, $\{u\}$ $(u\in V(T))$ and $V(T)$. The tournament $T$ is indecomposable if all its modules are trivial; otherwise it is decomposable. Let $T$ be a tournament with at least five vertices. In a previous paper, the authors proved that the smallest number $\delta(T)$ of arcs that must be reversed to make $T$ indecomposable satisfies $\delta(T) \leq \left\lceil \frac{v(T)+1}{4} \right\rceil$, and this bound is sharp, where $v(T) = |V(T)|$ is the order of $T$. In this paper, we prove that if the tournament $T$ is not transitive of even order, then $T$ can be made indecomposable by reversing the arcs of a subtournament of $T$. We denote by $\delta'(T)$ the smallest size of such a subtournament. We also prove that $\delta(T) = \left\lceil \frac{\delta'(T)}{2} \right\rceil$., Comment: 15 pages