BZPEERPapers, people, evidence and research paths
Menu

Discover

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

Research tools

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

Network

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

Opportunities

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

Account

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

Source author record

Omid Amini

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

ResearcherUnclaimed source record
math.COmath.AGmath.NTRoboticsArtificial IntelligenceMachine Learningmath.PRmath-phmath.CVmath.DGmath.MGmath.MPComputational Geometrymath.ACmath.GNmath.GTmath.SPNetworking and Internet Architecture

Catalog footprint

What is connected

31works
18topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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

Building this map preview

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

Published work

31 published item(s)

preprint2025arXiv

Cohomologically tropical varieties

Given the tropicalization of a complex subvariety of the torus, we define a morphism between the tropical cohomology and the rational cohomology of their respective tropical compactifications. We say that the subvariety of the torus is cohomologically tropical if this map is an isomorphism for all closed strata of the tropical compactification. We prove that a schön subvariety of the torus is cohomologically tropical if and only if it is wunderschön and its tropicalization is a tropical homology manifold. The former property means that the open strata in the boundary of a tropical compactification are all connected and the mixed Hodge structures on their cohomology are pure of maximum possible weight; the latter property requires that, locally, the tropicalization verifies tropical Poincaré duality. We study other properties of cohomologically tropical and wunderschön varieties, and show that in a semistable degeneration to an arrangement of cohomologically tropical varieties, the Hodge numbers of the smooth fibers are captured in the tropical cohomology of the tropicalization. This extends the results of Itenberg, Katzarkov, Mikhalkin, and Zharkov.

0 citations0 reviewsNo code linkedOpen access
preprint2024arXiv

Engineering Features to Improve Pass Prediction in Soccer Simulation 2D Games

Soccer Simulation 2D (SS2D) is a simulation of a real soccer game in two dimensions. In soccer, passing behavior is an essential action for keeping the ball in possession of our team and creating goal opportunities. Similarly, for SS2D, predicting the passing behaviors of both opponents and our teammates helps manage resources and score more goals. Therefore, in this research, we have tried to address the modeling of passing behavior of soccer 2D players using Deep Neural Networks (DNN) and Random Forest (RF). We propose an embedded data extraction module that can record the decision-making of agents in an online format. Afterward, we apply four data sorting techniques for training data preparation. After, we evaluate the trained models' performance playing against 6 top teams of RoboCup 2019 that have distinctive playing strategies. Finally, we examine the importance of different feature groups on the prediction of a passing strategy. All results in each step of this work prove our suggested methodology's effectiveness and improve the performance of the pass prediction in Soccer Simulation 2D games ranging from 5\% (e.g., playing against the same team) to 10\% (e.g., playing against Robocup top teams).

0 citations0 reviewsNo code linkedOpen access
preprint2024arXiv

Improving Dribbling, Passing, and Marking Actions in Soccer Simulation 2D Games Using Machine Learning

The RoboCup competition was started in 1997, and is known as the oldest RoboCup league. The RoboCup 2D Soccer Simulation League is a stochastic, partially observable soccer environment in which 24 autonomous agents play on two opposing teams. In this paper, we detail the main strategies and functionalities of CYRUS, the RoboCup 2021 2D Soccer Simulation League champions. The new functionalities presented and discussed in this work are (i) Multi Action Dribble, (ii) Pass Prediction and (iii) Marking Decision. The Multi Action Dribbling strategy enabled CYRUS to succeed more often and to be safer when dribbling actions were performed during a game. The Pass Prediction enhanced our gameplay by predicting our teammate's passing behavior, anticipating and making our agents collaborate better towards scoring goals. Finally, the Marking Decision addressed the multi-agent matching problem to improve CYRUS defensive strategy by finding an optimal solution to mark opponents' players.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

CYRUS Soccer Simulation 2D Team Description Paper 2021

In this report, we briefly present the technical procedure and simulation steps for the 2D soccer simulation of team Cyrus. We emphasize on this document on how the prediction of teammates' behavior is performed. In our proposed method, the agent receives the noisy inputs from the server, and predicts the ball holder full state behavior. Taking advantage of this approach for choosing the optimal view angle shows 11.30% improvement on the expected win rate.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

CYRUS Soccer Simulation 2D Team Description Paper 2022

Soccer Simulation 2D League is one of the major leagues of RoboCup competitions. In a Soccer Simulation 2D (SS2D) game, two teams of 11 players and one coach compete against each other. The players are only allowed to communicate with the server that is called Soccer Simulation Server. This paper introduces the previous and current research of the CYRUS soccer simulation team, the champion of RoboCup 2021. We will present our idea about improving Unmarking Decisioning and Positioning by using Pass Prediction Deep Neural Network. Based on our experimental results, this idea proven to be effective on increasing the winning rate of Cyrus against opponents.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Geometry of higher rank valuations

The aim of this paper is to introduce a certain number of tools and results suitable for the study of valuations of higher rank on function fields of algebraic varieties. This will be based on a study of higher rank quasi-monomial valuations taking values in the lexicographically ordered group R^k. We prove a duality theorem that gives a geometric realization of higher rank quasi-monomial valuations as tangent cones of dual cone complexes. Using this duality, we provide an analytic description of quasi-monomial valuations as multi-directional derivative operators on tropical functions. We consider moreover a refined notion of tropicalization in which we remember the initial terms of power series on each cone of a dual complex, and prove a tropical analogue of the weak approximation theorem in number theory by showing that any compatible collection of initial terms on cones of a dual cone complex is the refined tropicalization of a rational function in the function field of the variety. Endowing the value group R^k with its Euclidean topology, we study then a natural topology on spaces of higher rank valuations that we call the tropical topology. By using the approximation theorem we provide an explicit description of the tropical topology on tangent cones of dual cone complexes. Finally, we show that tangent cones of dual complexes provide a notion of skeleton in higher rank non-archimedean geometry. That is, generalizing the picture in rank one to higher rank, we construct retraction maps to tangent cones of dual cone complexes, and use them to obtain limit formulae in which we reconstruct higher rank non-archimedian spaces with their tropical topology as the projective limit of their higher rank skeleta. We conjecture that these higher rank skeleta provide appropriate bases for the study of variations of Newton-Okounkov bodies.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Moduli of hybrid curves II: Tropical and hybrid Laplacians

The present paper is a sequel to our work on hybrid geometry of curves and their moduli spaces. We introduce a notion of hybrid Laplacian, formulate a hybrid Poisson equation, and give a mathematical meaning to the convergence both of the Laplace operator and the solutions to the Poisson equation on Riemann surfaces. As the main theorem of this paper, we then obtain a layered description of the asymptotics of Arakelov Green functions on Riemann surfaces close to the boundary of their moduli spaces. This is done in terms of a suitable notion of hybrid Green functions. As a byproduct of our approach, we obtain other results of independent interest. In particular, we introduce higher rank canonical compactifications of fans and polyhedral spaces and use them to define the moduli space of higher rank tropical curves. Moreover, we develop the first steps of a function theory in higher rank non-Archimedean, hybrid, and tame analysis. Furthermore, we establish the convergence of the Laplace operator on metric graphs toward the tropical Laplace operator on limit tropical curves in the corresponding moduli spaces, leading to new perspectives in operator theory on metric graphs. Our result on the Arakelov Green function is inspired by the works of several authors, in particular those of Faltings, de Jong, Wentworth and Wolpert, and solves a long-standing open problem arising from the Arakelov geometry of Riemann surfaces. The hybrid layered behavior close to the boundary of moduli spaces is expected to be a broad phenomenon and will be explored in our forthcoming work.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Voronoi tilings, toric arrangements and degenerations of line bundles III

We describe limits of line bundles on nodal curves in terms of toric arrangements associated to Voronoi tilings of Euclidean spaces. These tilings encode information on the relationship between the possibly infinitely many limits, and ultimately give rise to a new definition of limit linear series. This article and the first two that preceded it are the first in a series aimed to explore this new approach. In Part I, we set up the combinatorial framework and showed how graphs weighted with integer lengths associated to the edges provide tilings of Euclidean spaces by certain polytopes associated to the graph itself and to its subgraphs. In Part II, we described the arrangements of toric varieties associated to the tilings of Part I in several ways: using normal fans, as unions of orbits, by equations and as degenerations of tori. In the present Part III, we show how these combinatorial and toric frameworks allow us to describe all stable limits of a family of line bundles along a degenerating family of curves. Our main result asserts that the collection of all these limits is parametrized by a connected 0-dimensional closed substack of the Artin stack of all torsion-free rank-one sheaves on the limit curve. Moreover, we thoroughly describe this closed substack and all the closed substacks that arise in this way as certain torus quotients of the arrangements of toric varieties of Part II determined by the Voronoi tilings of Euclidean spaces studied in Part I.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Hodge theory for tropical varieties

In this paper we prove that the cohomology of smooth projective tropical varieties verify the tropical analogs of three fundamental theorems which govern the cohomology of complex projective varieties: Hard Lefschetz theorem, Hodge-Riemann relations and monodromy-weight conjecture. On the way to establish these results, we introduce and prove other results of independent interest. This includes a generalization of the results of Adiprasito-Huh-Katz, Hodge theory for combinatorial geometries, to any unimodular quasi-projective fan having the same support as the Bergman fan of a matroid, a tropical analog for Bergman fans of the pioneering work of Feichtner-Yuzvinsky on cohomology of wonderful compactifications (treated in a separate paper, recalled and used here), a combinatorial study of the tropical version of the Steenbrink spectral sequence, a treatment of Kahler forms in tropical geometry and their associated Hodge-Lefschetz structures, a tropical version of the projective bundle formula, and a result in polyhedral geometry on the existence of quasi-projective unimodular triangulations of polyhedral spaces.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Lattice of integer flows and poset of strongly connected orientations

We show that the Voronoi cells of the lattice of integer flows of a finite connected graph $G$ in the quadratic vector space of real valued flows have the following very precise combinatorics: the face poset of a Voronoi cell is isomorphic to the poset of strongly connected orientations of subgraphs of $G$. This confirms a conjecture of Caporaso and Viviani {Torelli Theorem For Graphs and Tropical Curves, Duke Math. J. 153(1) (2010), 129-171}.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Voronoi tilings, toric arrangements and degenerations of line bundles I

We describe limits of line bundles on nodal curves in terms of toric arrangements associated to Voronoi tilings of Euclidean spaces. These tilings encode information on the relationship between the possibly infinitely many limits, and ultimately give rise to a new definition of limit linear series. This paper and its second and third companion parts are the first in a series aimed to explore this new approach. In the present article, we set up the combinatorial framework and show how graphs with integer lengths associated to the edges provide tilings of Euclidean spaces by certain polytopes associated to the graph itself and to certain of its subgraphs. We further provide a description of the combinatorial structure of these polytopes and the way they are glued together in the tiling. In the second part of the series, we describe the arrangements of toric varieties associated to these tilings. These results will be of use in the third part to achieve our goal of describing all stable limits of a family of line bundles along a degenerating family of curves.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Voronoi tilings, toric arrangements and degenerations of line bundles II

We describe limits of line bundles on nodal curves in terms of toric arrangements associated to Voronoi tilings of Euclidean spaces. These tilings encode information on the relationship between the possibly infinitely many limits, and ultimately give rise to a new definition of limit linear series. This article and its first and third part companion parts are the first in a series aimed to explore this new approach. In the first part, we set up the combinatorial framework and showed how graphs weighted with integer lengths associated to the edges provide tilings of Euclidean spaces by polytopes associated to the graph itself and to its subgraphs. In this part, we describe the arrangements of toric varieties associated to these tilings. Roughly speaking, the normal fan to each polytope in the tiling corresponds to a toric variety, and these toric varieties are glued together in an arrangement according to how the polytopes meet. We provide a thorough description of these toric arrangements from different perspectives: by using normal fans, as unions of torus orbits, by describing the (infinitely many) polynomial equations defining them in products of doubly infinite chains of projective lines, and as degenerations of algebraic tori. These results will be of use in the third part to achieve our goal of describing all stable limits of a family of line bundles along a degenerating family of curves.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A transfer principle and applications to eigenvalue estimates for graphs

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 $λ_k^{nr}$ of the normalized Laplacian of a graph $G$ of (geometric) genus $g$ on $n$ vertices satisfies $$λ_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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Feynman Amplitudes and Limits of Heights

We investigate from a mathematical perspective how Feynman amplitudes appear in the low-energy limit of string amplitudes. In this paper, we prove the convergence of the integrands. We derive this from results describing the asymptotic behavior of the height pairing between degree-zero divisors, as a family of Riemann surfaces degenerates. These are obtained by means of the nilpotent orbit theorem in Hodge theory.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Logarithmic Tree Factorials

To any rooted tree, we associate a sequence of numbers that we call the logarithmic factorials of the tree. This provides a generalization of Bhargava's factorials to a natural combinatorial setting suitable for studying questions around generalized factorials. We discuss several basic aspects of the framework in this paper. In particular, we relate the growth of the sequence of logarithmic factorials associated to a tree to the transience of the random walk and the existence of a harmonic measure on the tree, obtain an equidistribution theorem for factorial-determining-sequences of subsets of local fields, and provide a factorial-based characterization of the branching number of infinite trees. Our treatment is based on a local weighting process in the tree which gives an effective way of constructing the factorial sequence.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The combinatorial Chow ring of products of graphs

We prove results describing the structure of a Chow ring associated to a product of graphs, which arises from the Gross-Schoen desingularization of a product of regular proper semi-stable curves over discrete valuation rings. By the works of Johannes Kolb and Shou-Wu Zhang, this ring controls the behavior of the non-Archimedean height pairing on products of smooth proper curves over non-Archimedean fields. We provide a complete description of the degree map, and prove vanishing results affirming a conjecture of Kolb, which, combined with his work, leads to an analytic formula for the arithmetic intersection number of adelic metrized line bundles on products of curves over complete discretely valued fields.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The exchange graph and variations of the ratio of the two Symanzik polynomials

Correlation functions in quantum field theory are calculated using Feynman amplitudes, which are finite dimensional integrals associated to graphs. The integrand is the exponential of the ratio of the first and second Symanzik polynomials associated to the Feynman graph, which are described in terms of the spanning trees and spanning 2-forests of the graph, respectively. In a previous paper with Bloch, Burgos and Fresán, we related this ratio to the asymptotic of the Archimedean height pairing between degree zero divisors on degenerating families of Riemann surfaces. Motivated by this, we consider in this paper the variation of the ratio of the two Symanzik polynomials under bounded perturbations of the geometry of the graph. This is a natural problem in connection with the theory of nilpotent and SL2 orbits in Hodge theory. Our main result is the boundedness of variation of the ratio. For this we define the exchange graph of a given graph which encodes the exchange properties between spanning trees and spanning 2-forests in the graph. We provide a description of the connected components of this graph, and use this to prove our result on boundedness of the variations.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Geometric Tomography With Topological Guarantees

We consider the problem of reconstructing a compact 3-manifold (with boundary) embedded in $\mathbb{R}^3$ from its cross-sections $\mathcal S$ with a given set of cutting planes $\mathcal P$ having arbitrary orientations. Using the obvious fact that a point $x \in \mathcal P$ belongs to the original object if and only if it belongs to $\mathcal S$, we follow a very natural reconstruction strategy: we say that a point $x \in \mathbb{R}^3$ belongs to the reconstructed object if (at least one of) its nearest point(s) in $\mathcal P$ belongs to $\mathcal S$. This coincides with the algorithm presented by Liu et al. in \cite{LB+08}. In the present paper, we prove that under appropriate sampling conditions, the output of this algorithm preserves the homotopy type of the original object. Using the homotopy equivalence, we also show that the reconstructed object is homeomorphic (and isotopic) to the original object. This is the first time that 3-dimensional shape reconstruction from cross-sections comes with theoretical guarantees.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A spectral lower bound for the divisorial gonality of metric graphs

Let $Γ$ be a compact metric graph, and denote by $Δ$ the Laplace operator on $Γ$ with the first non-trivial eigenvalue $λ_1$. We prove the following Yang-Li-Yau type inequality on divisorial gonality $γ_{div}$ of $Γ$. There is a universal constant $C$ such that \[γ_{div}(Γ) \geq C \frac{μ(Γ) . \ell_{\min}^{\mathrm{geo}}(Γ). λ_1(Γ)}{d_{\max}},\] where the volume $μ(Γ)$ is the total length of the edges in $Γ$, $\ell_{\min}^{\mathrm{geo}}$ is the minimum length of all the geodesic paths between points of $Γ$ of valence different from two, and $d_{\max}$ is the largest valence of points of $Γ$. Along the way, we also establish discrete versions of the above inequality concerning finite simple graph models of $Γ$ and their spectral gaps.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Equidistribution of Weierstrass points on curves over non-Archimedean fields

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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Explosion and linear transit times in infinite trees

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 following cases: we say $T$ is explosive if \[ \lim_{n\to \infty}m_n(T) < \infty, \] and say that $T$ exhibits linear growth if \[ \liminf_{n\to \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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Lifting harmonic morphisms I: metrized complexes and Berkovich skeleta

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 is 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" versions of some foundational results ofLiu-Lorenzini, Coleman, and Liu on simultaneous semistable reduction of curves. We then consider the inverse problem of lifting finite harmonic morphisms of metrized complexes to morphisms of curves over K. We prove that every tamely ramified finite harmonic morphism of Λ-metrized complexes of k-curves lifts to a finite morphism of K-curves. If in addition the ramification points are marked, we obtain a complete classification of all such lifts along with their automorphisms. This generalizes and provides new analytic proofs of earlier results of Saïdi and Wewers. As an application, we discuss the relationship between harmonic morphisms of metric graphs and induced maps between component groups of Néron models, providing a negative answer to a question of Ribet motivated by number theory. This article is the first in a series of two. The second article contains several applications of our lifting results to questions about lifting morphisms of tropical curves.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Lifting harmonic morphisms II: tropical curves and metrized complexes

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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Linear series on metrized complexes of algebraic curves

A metrized complex of algebraic curves is a finite metric graph together with a collection of marked complete nonsingular algebraic curves, one for each vertex, the marked points being in bijection with incident edges. We establish a Riemann-Roch theorem for metrized complexes of curves which generalizes both the classical Riemann-Roch theorem and its graph-theoretic and tropical analogues due to Baker-Norine, Gathmann-Kerber, and Mikhalkin-Zharkov. We also establish generalizations of the second author's specialization lemma and its weighted graph analogue due to Caporaso and the first author, showing that the rank of a divisor cannot go down under specialization from curves to metrized complexes. As an application of these considerations, we formulate a generalization of the Eisenbud-Harris theory of limit linear series to semistable curves which are not necessarily of compact type.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On explosions in heavy-tailed branching random walks

Consider a branching random walk on $\mathbb{R}$, with offspring distribution Z and nonnegative displacement distribution W. We say that explosion occurs if an infinite number of particles may be found within a finite distance of the origin. In this paper, we investigate this phenomenon when the offspring distribution Z is heavy-tailed. Under an appropriate condition, we are able to characterize the pairs (Z, W) for which explosion occurs, by demonstrating the equivalence of explosion with a seemingly much weaker event: that the sum over generations of the minimum displacement in each generation is finite. Furthermore, we demonstrate that our condition on the tail is best possible for this equivalence to occur. We also investigate, under additional smoothness assumptions, the behavior of $M_n$, the position of the particle in generation n closest to the origin, when explosion does not occur (and hence $\lim_{n\rightarrow\infty}M_n=\infty$).

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A Unified Approach to Distance-Two Colouring of Graphs on Surfaces

In this paper we introduce the notion of $Σ$-colouring of a graph $G$: For given subsets $Σ(v)$ of neighbours of $v$, for every $v\in V(G)$, this is a proper colouring of the vertices of $G$ such that, in addition, vertices that appear together in some $Σ(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 asymptotic versions of Wegner's and Borodin's Conjecture on the planar version of these two colourings. Using a recent approach of Havet et al., we reduce the problem to edge-colouring of multigraphs, and then use Kahn's result that the list chromatic index is close to the fractional chromatic index. Our results are based on a strong structural lemma for graphs embeddable in a fixed surface, which also implies that the size of a clique in the square of a graph of maximum degree $Δ$ embeddable in some fixed surface is at most $\frac32\,Δ$ plus a constant.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Reduced Divisors and Embeddings of Tropical Curves

Given a divisor $D$ on a tropical curve $Γ$, we show that reduced divisors define an integral affine map from the tropical curve to the complete linear system $|D|$. This is done by providing an explicit description of the behavior of reduced divisors under infinitesimal modifications of the base point. We consider the cases where the reduced-divisor map defines an embedding of the curve into the linear system, and in this way, classify all the tropical curves with a very ample canonical divisor. As an application of the reduced-divisor map, we show the existence of Weierstrass points on tropical curves of genus at least two and present a simpler proof of a theorem of Luo on rank-determining sets of points. We also discuss the classical analogue of the (tropical) reduced-divisor map: For a smooth projective curve $C$ and a divisor $D$ of non-negative rank on $C$, reduced divisors equivalent to $D$ define a morphism from $C$ to the complete linear system $|D|$, which is described in terms of Wronskians.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Riemann-Roch for Sub-Lattices of the Root Lattice $A_n$

Recently, Baker and Norine {Advances in Mathematics, 215(2): 766-788, 2007} found new analogies between graphs and Riemann surfaces by developing a Riemann-Roch machinery on a finite graph $G$. In this paper, we develop a general Riemann-Roch Theory for sub-lattices of the root lattice $A_n$ by following the work of Baker and Norine, and establish connections between the Riemann-Roch theory and the Voronoi diagrams of lattices under certain simplicial distance functions. In this way, we rediscover the work of Baker and Norine from a geometric point of view and generalise their results to other sub-lattices of $A_n$. In particular, we provide a geometric approach for the study of the Laplacian of graphs. We also discuss some problems on classification of lattices with a Riemann-Roch formula as well as some related algorithmic issues.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Subgraphs of weakly quasi-random oriented graphs

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 area 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,B\ssq 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.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

WDM and Directed Star Arboricity

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 arcs of $D$ such that at each vertex $v$, and for each colour $α$, $in(v,α)+out(v,α)\leq n$ with $in(v,α)$ the number of arcs coloured $α$ entering $v$ and $out(v,α)$ the number of labels $l$ such that there is at least one arc of label $l$ leaving $v$ and coloured with $α$. The problem is to find the minimum number of colours $λ_n(D)$ such that the $m$-labelled digraph $D$ has an $n$-fibre colouring. In the particular case when $D$ is $1$-labelled, $λ_1(D)$ is called the directed star arboricity of $D$, and is denoted by $dst(D)$. We first show that $dst(D)\leq 2Δ^-(D)+1$, and conjecture that if $Δ^-(D)\geq 2$, then $dst(D)\leq 2Δ^-(D)$. We also prove that for a subcubic digraph $D$, then $dst(D)\leq 3$, and that if $Δ^+(D), Δ^-(D)\leq 2$, then $dst(D)\leq 4$. Finally, we study $λ_n(m,k)=\max\{λ_n(D) \tq D \mbox{is $m$-labelled} \et Δ^-(D)\leq k\}$. We show that if $m\geq n$, then $\ds \left\lceil\frac{m}{n}\left\lceil \frac{k}{n}\right\rceil + \frac{k}{n} \right\rceil\leq λ_n(m,k) \leq\left\lceil\frac{m}{n}\left\lceil \frac{k}{n}\right\rceil + \frac{k}{n} \right\rceil + C \frac{m^2\log k}{n}$ for some constant $C$. We conjecture that the lower bound should be the right value of $λ_n(m,k)$.

0 citations0 reviewsNo code linkedOpen access