We prove equidistribution of Weierstrass points on Berkovich curves. Let $X$ be a smooth proper curve of positive genus over a complete algebraically closed non-Archimedean field $K$ of equal characteristic zero with a non-trivial valuation. Let
$L$ be a line bundle of positive degree on $X$. The Weierstrass points of powers of $L$ are equidistributed according to the Zhang-Arakelov measure on the analytification $X^{an}$. This provides a non-Archimedean analogue of a theorem of Mumford and Neeman. Along the way we provide a description of the reduction of Weierstrass points, answering a question of Eisenbud and Harris.
Let $T$ be an infinite rooted tree with weights $w_e$ assigned to its edges. Denote by $m_n(T)$ the minimum weight of a path from the root to a node of the $n$th generation. We consider the possible behaviour of $m_n(T)$ with focus on the two followi
ng cases: we say $T$ is explosive if [ lim_{nto infty}m_n(T) < infty, ] and say that $T$ exhibits linear growth if [ liminf_{nto infty} frac{m_n(T)}{n} > 0. ] We consider a class of infinite randomly weighted trees related to the Poisson-weighted infinite tree, and determine precisely which trees in this class have linear growth almost surely. We then apply this characterization to obtain new results concerning the event of explosion in infinite randomly weighted spherically-symmetric trees, answering a question of Pemantle and Peres. As a further application, we consider the random real tree generated by attaching sticks of deterministic decreasing lengths, and determine for which sequences of lengths the tree has finite height almost surely.
In this paper, we prove a variant of the Burger-Brooks transfer principle which, combined with recent eigenvalue bounds for surfaces, allows to obtain upper bounds on the eigenvalues of graphs as a function of their genus. More precisely, we show the
existence of a universal constants $C$ such that the $k$-th eigenvalue $lambda_k^{nr}$ of the normalized Laplacian of a graph $G$ of (geometric) genus $g$ on $n$ vertices satisfies $$lambda_k^{nr}(G) leq C frac{d_{max}(g+k)}{n},$$ where $d_{max}$ denotes the maximum valence of vertices of the graph. This result is tight up to a change in the value of the constant $C$, and improves recent results of Kelner, Lee, Price and Teng on bounded genus graphs. To show that the transfer theorem might be of independent interest, we relate eigenvalues of the Laplacian on a metric graph to the eigenvalues of its simple graph models, and discuss an application to the mesh partitioning problem, extending pioneering results of Miller-Teng-Thurston-Vavasis and Spielman-Tang to arbitrary meshes.
Let $Gamma$ be a compact metric graph, and denote by $Delta$ the Laplace operator on $Gamma$ with the first non-trivial eigenvalue $lambda_1$. We prove the following Yang-Li-Yau type inequality on divisorial gonality $gamma_{div}$ of $Gamma$. There i
s a universal constant $C$ such that [gamma_{div}(Gamma) geq C frac{mu(Gamma) . ell_{min}^{mathrm{geo}}(Gamma). lambda_1(Gamma)}{d_{max}},] where the volume $mu(Gamma)$ is the total length of the edges in $Gamma$, $ell_{min}^{mathrm{geo}}$ is the minimum length of all the geodesic paths between points of $Gamma$ of valence different from two, and $d_{max}$ is the largest valence of points of $Gamma$. Along the way, we also establish discre
In this paper we prove several lifting theorems for morphisms of tropical curves. We interpret the obstruction to lifting a finite harmonic morphism of augmented metric graphs to a morphism of algebraic curves as the non-vanishing of certain Hurwitz
numbers, and we give various conditions under which this obstruction does vanish. In particular we show that any finite harmonic morphism of (non-augmented) metric graphs lifts. We also give various applications of these results. For example, we show that linear equivalence of divisors on a tropical curve C coincides with the equivalence relation generated by declaring that the fibers of every finite harmonic morphism from C to the tropical projective line are equivalent. We study liftability of metrized complexes equipped with a finite group action, and use this to classify all augmented metric graphs arising as the tropicalization of a hyperelliptic curve. We prove that there exists a d-gonal tropical curve that does not lift to a d-gonal algebraic curve. This article is the second in a series of two.
Let K be an algebraically closed, complete non-Archimedean field. The purpose of this paper is to carefully study the extent to which finite morphisms of algebraic K-curves are controlled by certain combinatorial objects, called skeleta. A skeleton i
s a metric graph embedded in the Berkovich analytification of X. A skeleton has the natural structure of a metrized complex of curves. We prove that a finite morphism of K-curves gives rise to a finite harmonic morphism of a suitable choice of skeleta. We use this to give analytic proofs of stronger skeletonized
In this paper we introduce the notion of $Sigma$-colouring of a graph $G$: For given subsets $Sigma(v)$ of neighbours of $v$, for every $vin V(G)$, this is a proper colouring of the vertices of $G$ such that, in addition, vertices that appear togethe
r in some $Sigma(v)$ receive different colours. This concept generalises the notion of colouring the square of graphs and of cyclic colouring of graphs embedded in a surface. We prove a general result for graphs embeddable in a fixed surface, which implies asymptot
A digraph is $m$-labelled if every arc is labelled by an integer in ${1, dots,m}$. Motivated by wavelength assignment for multicasts in optical networks, we introduce and study $n$-fibre colourings of labelled digraphs. These are colourings of the ar
cs of $D$ such that at each vertex $v$, and for each colour $alpha$, $in(v,alpha)+out(v,alpha)leq n$ with $in(v,alpha)$ the number of arcs coloured $alpha$ entering $v$ and $out(v,alpha)$ the number of labels $l$ such that there is at least one arc of label $l$ leaving $v$ and coloured with $alpha$. The problem is to find the minimum number of colours $lambda_n(D)$ such that the $m$-labelled digraph $D$ has an $n$-fibre colouring. In the particular case when $D$ is $1$-labelled, $lambda_1(D)$ is called the directed star arboricity of $D$, and is denoted by $dst(D)$. We first show that $dst(D)leq 2Delta^-(D)+1$, and conjecture that if $Delta^-(D)geq 2$, then $dst(D)leq 2Delta^-(D)$. We also prove that for a subcubic digraph $D$, then $dst(D)leq 3$, and that if $Delta^+(D), Delta^-(D)leq 2$, then $dst(D)leq 4$. Finally, we study $lambda_n(m,k)=max{lambda_n(D) tq D mbox{is $m$-labelled} et Delta^-(D)leq k}$. We show that if $mgeq n$, then $ds leftlceilfrac{m}{n}leftlceil frac{k}{n}rightrceil + frac{k}{n} rightrceilleq lambda_n(m,k) leqleftlceilfrac{m}{n}leftlceil frac{k}{n}rightrceil + frac{k}{n} rightrceil + C frac{m^2log k}{n}$ for some constant $C$. We conjecture that the lower bound should be the right value of $lambda_n(m,k)$.
It is an intriguing question to see what kind of information on the structure of an oriented graph $D$ one can obtain if $D$ does not contain a fixed oriented graph $H$ as a subgraph. The related question in the unoriented case has been an active are
a of research, and is relatively well-understood in the theory of quasi-random graphs and extremal combinatorics. In this paper, we consider the simplest cases of such a general question for oriented graphs, and provide some results on the global behavior of the orientation of $D$. For the case that $H$ is an oriented four-cycle we prove: in every $H$-free oriented graph $D$, there is a pair $A,Bssq V(D)$ such that $e(A,B)ge e(D)^{2}/32|D|^{2}$ and $e(B,A)le e(A,B)/2$. We give a random construction which shows that this bound on $e(A,B)$ is best possible (up to the constant). In addition, we prove a similar result for the case $H$ is an oriented six-cycle, and a more precise result in the case $D$ is dense and $H$ is arbitrary. We also consider the related extremal question in which no condition is put on the oriented graph $D$, and provide an answer that is best possible up to a multiplicative constant. Finally, we raise a number of related questions and conjectures.
Covering problems are fundamental classical problems in optimization, computer science and complexity theory. Typically an input to these problems is a family of sets over a finite universe and the goal is to cover the elements of the universe with a
s few sets of the family as possible. The variations of covering problems include well known problems like Set Cover, Vertex Cover, Dominating Set and Facility Location to name a few. Recently there has been a lot of study on partial covering problems, a natural generalization of covering problems. Here, the goal is not to cover all the elements but to cover the specified number of elements with the minimum number of sets. In this paper we study partial covering problems in graphs in the realm of parameterized complexity. Classical (non-partial) version of all these problems have been intensively studied in planar graphs and in graphs excluding a fixed graph $H$ as a minor. However, the techniques developed for parameterized version of non-partial covering problems cannot be applied directly to their partial counterparts. The approach we use, to show that various partial covering problems are fixed parameter tractable on planar graphs, graphs of bounded local treewidth and graph excluding some graph as a minor, is quite different from previously known techniques. The main idea behind our approach is the concept of implicit branching. We find implicit branching technique to be interesting on its own and believe that it can be used for some other problems.
