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)$.

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

In this paper we study some cube packing problems. In particular we are interested in compact subsets of $\mathbb{R}^n,n\geq 2$, which contain boundaries of cubes with all side lengths in $(0,1)$. We show here that such sets must have lower box dimension at least $n-0.5$ and we will also provide sharp examples. We also show here that such sets must be large in general in a precise sense which is also introduced in this paper., 9 pages. arXiv admin note: text overlap with arXiv:1711.06533

The theory of mixed multiplicities of filtrations by $m$-primary ideals in a ring is introduced in a recent paper by Cutkosky, Sarkar and Srinivasan. In this paper, we consider the positivity of mixed multiplicities of filtrations. We show that the mixed multiplicities of filtrations must be nonnegative real numbers and give examples to show that they could be zero or even irrational. When $R$ is analytically irreducible, and $\mathcal I(1),\ldots,\mathcal I(r)$ are filtrations of $R$ by $m_R$-primary ideals, we show that all of the mixed multiplicities $e_R(\mathcal I(1)^{[d_1]},\ldots,\mathcal I(r)^{[d_r]};R)$ are positive if and only if the ordinary multiplicities $e_R(\mathcal I(i);R)$ for $1\le i\le r$ are positive. We extend this to modules and prove a simple characterization of when the mixed multiplicities are positive or zero on a finitely generated module., 15 pages

This paper develops an abstract theory for subdifferential operators to give existence and uniqueness of solutions to the initial-boundary problem (P) for the nonlinear diffusion equation in an unbounded domain $\Omega\subset\mathbb{R}^N$ ($N\in{\mathbb N}$), written as \[ \frac{\partial u}{\partial t} + (-\Delta+1)\beta(u) = g \quad \mbox{in}\ \Omega\times(0, T), \] which represents the porous media, the fast diffusion equations, etc., where $\beta$ is a single-valued maximal monotone function on $\mathbb{R}$, and $T>0$. Existence and uniqueness for (P) were directly proved under a growth condition for $\beta$ even though the Stefan problem was excluded from examples of (P). This paper completely removes the growth condition for $\beta$ by confirming Cauchy's criterion for solutions of the following approximate problem (P)$_{\varepsilon}$ with approximate parameter $\varepsilon>0$: \[ \frac{\partial u_{\varepsilon}}{\partial t} + (-\Delta+1)(\varepsilon(-\Delta+1)u_{\varepsilon} + \beta(u_{\varepsilon}) + \pi_{\varepsilon}(u_{\varepsilon})) = g \quad \mbox{in}\ \Omega\times(0, T), \] which is called the Cahn--Hilliard system, even if $\Omega \subset \mathbb{R}^N$ ($N \in \mathbb{N}$) is an unbounded domain. Moreover, it can be seen that the Stefan problem is covered in the framework of this paper.

The theme of this paper is the analysis of bootstrap percolation processes on random graphs generated by preferential attachment. This is a class of infection processes where vertices have two states: they are either infected or susceptible. At each round every susceptible vertex which has at least $r\geq 2$ infected neighbours becomes infected and remains so forever. Assume that initially $a(t)$ vertices are randomly infected, where $t$ is the total number of vertices of the graph. Suppose also that $r < m$, where $2m$ is the average degree. We determine a critical function $a_c(t)$ such that when $a(t) \gg a_c(t)$, complete infection occurs with high probability as $t \rightarrow \infty$, but when $a(t) \ll a_c (t)$, then with high probability the process evolves only for a bounded number of rounds and the final set of infected vertices is asymptotically equal to $a(t)$., This paper is significantly different to the previous version

This paper studies a higher dimensional generalization of Frieze's $\zeta(3)$-limit theorem in the Erd\"os-R\'enyi graph process. Frieze's theorem states that the expected weight of the minimum spanning tree converges to $\zeta(3)$ as the number of vertices goes to infinity. In this paper, we study the $d$-Linial-Meshulam process as a model for random simplicial complexes, where $d=1$ corresponds to the Erd\"os-R\'enyi graph process. First, we define spanning acycles as a higher dimensional analogue of spanning trees, and connect its minimum weight to persistent homology. Then, our main result shows that the expected weight of the minimum spanning acycle behaves in $O(n^{d-1})$., Comment: 24 pages

The k-core, defined as the maximal subgraph of minimum degree at least k, of the random graph G(n,p) has been studied extensively. In a landmark paper Pittel, Wormald and Spencer [J Combin Theory Ser B 67 (1996), 111–151] determined the threshold dk for the appearance of an extensive k-core. The aim of the present paper is to describe how the k-core is “embedded” into the random graph in the following sense. Let k≥3 and fix d=np>dk. Colour each vertex that belongs to the k-core of G(n,p) in black and all remaining vertices in white. Here we derive a multi-type branching process that describes the local structure of this coloured random object as n tends to infinity. This generalises prior results on, e.g., the internal structure of the k-core. In the physics literature it was suggested to characterize the core by means of a message passing algorithm called Warning Propagation. Ibrahimi, Kanoria, Kraning and Montanari [Ann Appl Probab 25 (2015), 2743–2808] used this characterization to describe the 2-core of random hypergraphs. To derive our main result we use a similar approach. A key observation is that a bounded number of iterations of this algorithm is enough to give a good approximation of the k-core. Based on this the study of the k-core reduces to the analysis of Warning Propagation on a suitable Galton-Watson tree. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 00, 000–000, 2017

We consider consecutive random subdivision of polygons described as follows. Given an initial convex polygon with $d\ge 3$ edges, we choose a point at random on each edge, such that the proportions in which these points divide edges are i.i.d. copies of some random variable $\xi$. These new points form a new (smaller) polygon. By repeatedly implementing this procedure we obtain a sequence of random polygons. The aim of this paper is to show that under very mild non-degenerateness conditions on $\xi$, the shapes of these polygons eventually become "flat" The convergence rate to flatness is also investigated; in particular, in the case of triangles ($d=3$), we show how to calculate the exact value of the rate of convergence, connected to Lyapunov exponents. Using the theory of products of random matrices our paper greatly generalizes the results of Volkov (2013) which are achieved mostly by using ad hoc methods., Comment: 35 pages, 2 figures

Staircase tableaux are combinatorial objects that were first introduced due to a connection with the asymmetric simple exclusion process (ASEP) and Askey-Wilson polynomials. Since their introduction, staircase tableaux have been the object of study in many recent papers. Relevant to this paper, Hitczenko and Janson proved that distribution of parameters on the first diagonal is asymptotically normal. In addition, they conjectured that other diagonals would be asymptotically Poisson. Since then, only the second and the third diagonal were proven to follow the conjecture. This paper builds upon those results to prove the conjecture for the kth diagonal where k is fixed. In particular, we prove that the distribution of the number of α's (β's) on the kth diagonal, k > 1, is asymptotically Poisson with parameter 1/2. In addition, we prove that symbols on the kth diagonal are asymptotically independent and thus, collectively follow the Poisson distribution with parameter 1. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 795–818, 2016

In a recent paper of Ellenberg, Oberlin, and Tao, the authors asked whether there are Besicovitch phenomena in F_q[[t]]^n. In this paper, we answer their question in the affirmative by explicitly constructing a Kakeya set in F_q[[t]]^n of measure 0. Furthermore, we prove that any Kakeya set in F_q[[t]]^2 or Z_p^2 is of Minkowski dimension 2., Comment: 10 pages

We consider connectivity properties of certain i.i.d. random environments on i¾?d, where at each location some steps may not be available. Site percolation and oriented percolation are examples of such environments. In these models, one of the quantities most often studied is the random set of vertices that can be reached from the origin by following a connected path. More generally, for the models we consider, multiple different types of connectivity are of interest, including: the set of vertices that can be reached from the origin; the set of vertices from which the origin can be reached; the intersection of the two. As with percolation models, many of the models we consider admit, or are expected to admit phase transitions. Among the main results of the paper is a proof of the existence of phase transitions for some two-dimensional models that are non-monotone in their underlying parameter, and an improved bound on the critical value for oriented site percolation on the triangular lattice. The connectivity of the random directed graphs provides a foundation for understanding the asymptotic properties of random walks in these random environments, which we study in a second paper. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 111-137, 2014

Let $G$ be a finite group, and let $\kappa(G)$ be the probability that elements $g$, $h\in G$ are conjugate, when $g$ and $h$ are chosen independently and uniformly at random. The paper classifies those groups $G$ such that $\kappa(G) \geq 1/4$, and shows that $G$ is abelian whenever $\kappa(G)|G| < 7/4$. It is also shown that $\kappa(G)|G|$ depends only on the isoclinism class of $G$. Specialising to the symmetric group $S_n$, the paper shows that $\kappa(S_n) \leq C/n^2$ for an explicitly determined constant $C$. This bound leads to an elementary proof of a result of Flajolet \emph{et al}, that $\kappa(S_n) \sim A/n^2$ as $n\rightarrow \infty$ for some constant $A$. The same techniques provide analogous results for $\rho(S_n)$, the probability that two elements of the symmetric group have conjugates that commute., Comment: 34 pages, corrected version, to appear in Journal of the London Mathematical Society

We determine the order of magnitude of H^{(k+1)}(x,\vec{y},2\vec{y}), the number of integers up to x that are divisible by a product d_1...d_k with y_i, Comment: 34 pages. Added reference [10] to a paper of Nair and Tenenbaum which contains a result similar to Lemma 2.2 and which appeared prior to the publication of this paper. Simplified the proof of Lemma 2.2 using ideas from [10]. Removed part (a) of Lemma 2.2, as it is now redundant. Version 5 remains the published version

In a paper of 2003, B. K��lshammer, J. B. Olsson and G. R. Robinson defined $\ell$-blocks for the symmetric groups, where $\ell >1$ is an arbitrary integer. In this paper, we give a definition for the defect group of the principal $\ell$-block. We then check that, in the Abelian case, we have an analogue of one of M. Brou��'s conjectures., 18 pages

In this paper the absolute value or distance from the origin analogue of the classical Khintchine-Groshev theorem [5] is established for a single linear form with a “slowly decreasing” error function. To explain this in more detail, some notation is introduced. Throughout this paper, m, n are positive integers; i.e., m, n ∈ ℕ; x = (x1,…, xn) will denote a point or vector in ℝn, q = (q1,…, qn) will denote a non-zero vector in ℤn and|x| := max{|x1|,…,|xn|} = ‖X‖∞will denote the height of the vector x. Let Ψ : ℕ → (0, ∞) be a (non-zero) function which converges to 0 at ∞. The notion of a slowly decreasing functionΨ is defined in [3] as a function for which, given c ∈ (0, 1), there exists a K = K(c) > 1 such that Ψ(ck) ≤ KΨ(k). Of course, since Ψ is decreasing, Ψ(k) ≤ Ψ(ck). For any set X, |X| will denote the Lebesgue measure of X (there should be no confusion with the height of a vector).

Let G be a group and let O_G denote the set of left orderings on G. Then O_G can be topologized in a natural way, and we shall study this topology to show that O_G can never be countably infinite. This paper retrieves correct parts of the withdrawn paper arXiv:math/0607470., 4 pages

This version of the paper corrects an inaccuracy in the proof of Theorem 2.9 in the published version. The main results remain unchanged., Corrected arXiv version of the published paper

Given a graph sequence $\{G_n\}_{n \geq 1}$ denote by $T_3(G_n)$ the number of monochromatic triangles in a uniformly random coloring of the vertices of $G_n$ with $c \geq 2$ colors. This arises as a generalization of the birthday paradox, where $G_n$ corresponds to a friendship network and $T_3(G_n)$ counts the number of triples of friends with matching birthdays. In this paper we prove a central limit theorem (CLT) for $T_3(G_n)$ with explicit error rates. The proof involves constructing a martingale difference sequence by carefully ordering the vertices of $G_n$, based on a certain combinatorial score function, and using a quantitive version of the martingale CLT. We then relate this error term to the well-known fourth moment phenomenon, which, interestingly, holds only when the number of colors $c \geq 5$. We also show that the convergence of the fourth moment is necessary to obtain a Gaussian limit for any $c \geq 2$, which, together with the above result, implies that the fourth-moment condition characterizes the limiting normal distribution of $T_3(G_n)$, whenever $c \geq 5$. Finally, to illustrate the promise of our approach, we include an alternative proof of the CLT for the number of monochromatic edges, which provides quantitative rates for the results obtained in Bhattacharya et al. (2017)., Comment: 30 pages, 2 figures

A partial linear space is a pair $(\mathcal{P},\mathcal{L})$ where $\mathcal{P}$ is a non-empty set of points and $\mathcal{L}$ is a collection of subsets of $\mathcal{P}$ called lines such that any two distinct points are contained in at most one line, and every line contains at least two points. A partial linear space is proper when it is not a linear space or a graph. A group of automorphisms $G$ of a proper partial linear space acts transitively on ordered pairs of distinct collinear points and ordered pairs of distinct non-collinear points precisely when $G$ is transitive of rank 3 on points. In this paper, we classify the finite proper partial linear spaces that admit rank 3 affine primitive automorphism groups, except for certain families of small groups, including subgroups of $A\Gamma L_1(q)$. Up to these exceptions, this completes the classification of the finite proper partial linear spaces admitting rank 3 primitive automorphism groups. We also provide a more detailed version of the classification of the rank 3 affine primitive permutation groups, which may be of independent interest., Comment: In this version, we have removed the assumption $V\leq H$ from 18.1 (old 13.2) and we have a new elementary proof of 10.10 (old 13.1). We have also reorganised some of the sections and made minor revisions throughout. 69 pages, 1 figure

Let f: C --> P^3 be a general curve of genus g, mapped to P^3 via a general linear series of degree d; and let Q be a general (and thus smooth) quadric. In this paper, we show that the points of intersection f(C) \cap Q give a general collection of 2d points on Q, except for exactly six exceptional cases. We also prove similar theorems for every other pair (r, n) for which, except for only finitely many pairs (d, g), the intersection of a general curve of genus g mapped to P^r via a general linear series of degree d, with a general hypersurface S of degree n, is a general collection of dn points on S. As explained in arXiv:1809.05980, these results play a key role in the author's proof of the Maximal Rank Conjecture

In a celebrated paper, Borwein, Erd\'elyi, Ferguson and Lockhart constructed cosine polynomials of the form \[ f_A(x) = \sum_{a \in A} \cos(ax), \] with $A\subseteq \mathbb{N}$, $|A|= n$ and as few as $n^{5/6+o(1)}$ zeros in $[0,2\pi]$, thereby disproving an old conjecture of J.E. Littlewood. Here we give a sharp analysis of their constructions and, as a result, prove that there exist examples with as few as $C(n\log n)^{2/3}$ roots., Comment: 17 pages. A few typos fixed

In this paper, we consider a randomized greedy algorithm for independent sets in $r$-uniform $d$-regular hypergraphs $G$ on $n$ vertices with girth $g$. By analyzing the expected size of the independent sets generated by this algorithm, we show that $\alpha(G)\geq (f(d,r)-\epsilon(g,d,r))n$, where $\epsilon(g,d,r)$ converges to $0$ as $g\rightarrow\infty$ for fixed $d$ and $r$, and $f(d,r)$ is determined by a differential equation. This extends earlier results of Gamarnik and Goldberg for graphs. We also prove that when applying this algorithm to uniform linear hypergraphs with bounded degree, the size of the independent sets generated by this algorithm concentrate around the mean asymptotically almost surely.

In this paper, we compute the cohomology class of certain "special maximal-rank loci" originally defined by Aprodu and Farkas. By showing that such classes are nonzero, we are able to verify the non-emptiness portion of the Strong Maximal Rank Conjecture in a wide range of cases. As an application, we obtain new evidence for the existence portion of a well-known conjecture due to Bertram, Feinberg and independently Mukai in higher-rank Brill--Noether theory., 38 pages, significantly reorganized final version to appear in J. London Math. Soc

In this paper, we consider the 3D Navier-Stokes equations in the whole space. We investigate some new inequalities and \textit{a priori} estimates to provide the critical regularity criteria in terms of one directional derivative of the velocity field, namely $\partial_3 \mathbf{u} \in L^p((0,T); L^q(\mathbb{R}^3)), ~\frac{2}{p} + \frac{3}{q} = 2, ~\frac{3}{2}

Given graphs $F,H$ and $G$, we say that $G$ is $(F,H)_v$-Ramsey if every red/blue vertex colouring of $G$ contains a red copy of $F$ or a blue copy of $H$. Results of {\L}uczak, Ruci\'nski and Voigt and, subsequently, Kreuter determine the threshold for the property that the random graph $G(n,p)$ is $(F,H)_v$-Ramsey. In this paper we consider the sister problem in the setting of randomly perturbed graphs. In particular, we determine how many random edges one needs to add to a dense graph to ensure that with high probability the resulting graph is $(F,H)_v$-Ramsey for all pairs $(F,H)$ that involve at least one clique., Comment: 21 pages

Reflexive polytopes have been studied from viewpoints of combinatorics, commutative algebra and algebraic geometry. A nef-partition of a reflexive polytope $\mathcal{P}$ is a decomposition $\mathcal{P}=\mathcal{P}_1+\cdots+\mathcal{P}_r$ such that each $\mathcal{P}_i$ is a lattice polytope containing the origin. Batyrev and van Straten gave a combinatorial method for explicit constructions of mirror pairs of Calabi-Yau complete intersections obtained from nef-partitions. In the present paper, by means of Gr\"{o}bner basis techniques, we give a large family of nef-partitions arising from unimodular configurations., Comment: 12 pages, typos are corrected, the writing is improved

In this paper, we investigate the weak-type regularity of the Bergman projection. The two domains we focus on are the polydisc and the Hartogs triangle. For the polydisc we provide a proof that the weak-type behavior is of "$L\log L$" type. This result is likely known to the experts, but does not appear to be in the literature. For the Hartogs triangle we show that the operator is of weak-type $(4,4)$; settling the question of the behavior of the projection at this endpoint. At the other endpoint of interest, we show that the Bergman projection is not of weak-type $(\frac{4}{3}, \frac{4}{3})$ and provide evidence as to what the correct behavior at this endpoint might be., Comment: 15 pages

Let G be a group, and let M=(m_n) be a sequence of finitely supported probability measures on G. Consider the probability that two elements chosen independently according to m_n commute. Antolin, Martino and Ventura define the 'degree of commutativity' dc_M(G) of G with respect to this sequence to be the lim sup of this probability. The main results of the present paper give quantitative algebraic consequences of the degree of commutativity being above certain thresholds. For example, if m_n is the distribution of the nth step of a symmetric random walk on G, or if G is amenable and (m_n) is a sequence of almost-invariant measures on G, we show that if dc_M(G) is at least a>0 then G contains a normal subgroup G' of index f(a) and a normal subgroup H of cardinality at most g(a) such that G'/H is abelian. This generalises a result for finite groups due to P. M. Neumann, and generalises and quantifies a result for certain residually finite groups of subexponential growth due to Antolin, Martino and Ventura. We also describe some general conditions on M under which such theorems hold. We close with an application to 'conjugacy ratios' as introduced by Cox., 18 pages. Some theorem, section and reference numbering is significantly changed from previous versions

A recent result of Condon, Kim, K\"{u}hn and Osthus implies that for any $r\geq (\frac{1}{2}+o(1))n$, an $n$-vertex almost $r$-regular graph $G$ has an approximate decomposition into any collections of $n$-vertex bounded degree trees. In this paper, we prove that a similar result holds for an almost $\alpha n$-regular graph $G$ with any $\alpha>0$ and a collection of bounded degree trees on at most $(1-o(1))n$ vertices if $G$ does not contain large bipartite holes. This result is sharp in the sense that it is necessary to exclude large bipartite holes and we cannot hope for an approximate decomposition into $n$-vertex trees. Moreover, this implies that for any $\alpha>0$ and an $n$-vertex almost $\alpha n$-regular graph $G$, with high probability, the randomly perturbed graph $G\cup \mathbf{G}(n,O(\frac{1}{n}))$ has an approximate decomposition into all collections of bounded degree trees of size at most $(1-o(1))n$ simultaneously. This is the first result considering an approximate decomposition problem in the context of Ramsey-Tur\'an theory and the randomly perturbed graph model., Comment: 15 pages

"This is the peer reviewed version of the following article: Abad C, Bravo A, Villamayor U. OV. Finite morphisms and simultaneous reduction of the multiplicity. Mathematische Nachrichten. 2020;293:8–38, which has been published in final form at https://doi.org/10.1002/mana.201800470. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Use of Self-Archived Versions. This article may not be enhanced, enriched or otherwise transformed into a derivative work, without express permission from Wiley or by statutory rights under applicable legislation. Copyright notices must not be removed, obscured or modified. The article must be linked to Wiley’s version of record on Wiley Online Library and any embedding, framing or otherwise making available the article or pages thereof by third parties from platforms, services and websites other than Wiley Online Library must be prohibited", Let X be a singular algebraic variety defined over a perfect field k, with quotient field K ( X ) . Let s ≥ 2 be the highest multiplicity of X and let F s ( X ) be the set of points of multiplicity s. If Y ⊂ F s ( X ) is a regular center and X ← X 1 is the blow up at Y, then the highest multiplicity of X1 is less than or equal to s. A sequence of blow ups at regular centers Y i ⊂ F s ( X i ) , say X ← X 1 ← ⋯ ← X n , is said to be a simplification of the multiplicity if the maximum multiplicity of X n is strictly lower than that of X, that is, if F s ( X n ) is empty. In characteristic zero there is an algorithm which assigns to each X a unique simplification of the multiplicity. However, the problem remains open when the characteristic is positive. In this paper we will study finite dominant morphisms between singular varieties β : X ′ → X of generic rank r ≥ 1 (i.e., [ K ( X ′ ) : K ( X ) ] = r ). We will see that, when imposing suitable conditions on β, there is a strong link between the strata of maximum multiplicity of X and X ′ , say F s ( X ) and F r s ( X ′ ) respectively. In such case, we will say that the morphism is strongly transversal. When β : X ′ → X is strongly transversal one can obtain information about the simplification of the multiplicity of X from that of X ′ and vice versa. Finally, we will see that given a singular variety X and a finite field extension L of K ( X ) of rank r ≥ 1 , one can construct (at least locally, in étale topology) a strongly transversal morphism β : X ′ → X , where X ′ has quotient field L., The authors were partially supported by the Spanish Ministry of Economy and Competitiveness, through the “Severo Ochoa” Programme for Centres of Excellence in R&D (SEV2015-0554), and through MTM2015-68524-P (MINECO/FEDER)

The seminal Lee-Yang theorem states that for any graph the zeros of the partition function of the ferromagnetic Ising model lie on the unit circle in $\mathbb C$. In fact the union of the zeros of all graphs is dense on the unit circle. In this paper we study the location of the zeros for the class of graphs of bounded maximum degree $d\geq 3$, both in the ferromagnetic and the anti-ferromagnetic case. We determine the location exactly as a function of the inverse temperature and the degree $d$. An important step in our approach is to translate to the setting of complex dynamics and analyze a dynamical system that is naturally associated to the partition function., 24 pages, 3 figures. Made a number of small clarifications, corrections and changes in notation. Results remain unchanged. To appear in the Journal of the London Mathematical Society

Let Γ be a simple graph and IΓ (x) its multivariate independence polynomial. The main result of this paper is the characterization of chordal graphs as the only Γ for which the power series expansion of I-1Γ (x) is Horn hypergeometric., Bulletin of the London Mathematical Society, 53 (6), ISSN:0024-6093, ISSN:1469-2120

Peter Aczel has given a categorical construction for fixed points of normal functors, i.e. dilators which preserve initial segments. For a general dilator $X\mapsto T_X$ we cannot expect to obtain a well-founded fixed point, as the order type of $T_X$ may always exceed the order type of $X$. In the present paper we show how to construct a Bachmann-Howard fixed point of $T$, i.e. an order $\operatorname{BH}(T)$ with an "almost" order preserving collapse $\vartheta:T_{\operatorname{BH}(T)}\rightarrow\operatorname{BH}(T)$. Building on previous work, we show that $\Pi^1_1$-comprehension is equivalent to the assertion that $\operatorname{BH}(T)$ is well-founded for any dilator $T$., Comment: This version has been accepted for publication in the Bulletin of the London Mathematical Society

In this paper we propose algorithms for allocating $n$ sequential balls into $n$ bins that are interconnected as a $d$-regular $n$-vertex graph $G$, where $d\ge3$ can be any integer.Let $l$ be a given positive integer. In each round $t$, $1\le t\le n$, ball $t$ picks a node of $G$ uniformly at random and performs a non-backtracking random walk of length $l$ from the chosen node.Then it allocates itself on one of the visited nodes with minimum load (ties are broken uniformly at random). Suppose that $G$ has a sufficiently large girth and $d=\omega(\log n)$. Then we establish an upper bound for the maximum number of balls at any bin after allocating $n$ balls by the algorithm, called {\it maximum load}, in terms of $l$ with high probability. We also show that the upper bound is at most an $O(\log\log n)$ factor above the lower bound that is proved for the algorithm. In particular, we show that if we set $l=\lfloor(\log n)^{\frac{1+\epsilon}{2}}\rfloor$, for every constant $\epsilon\in (0, 1)$, and $G$ has girth at least $\omega(l)$, then the maximum load attained by the algorithm is bounded by $O(1/\epsilon)$ with high probability.Finally, we slightly modify the algorithm to have similar results for balanced allocation on $d$-regular graph with $d\in[3, O(\log n)]$ and sufficiently large girth.

In this paper we study the number of rational points on curves in an ensemble of abelian covers of the projective line: Let $\ell$ be a prime, $q$ a prime power and consider the ensemble $\mathcal{H}_{g,\ell}$ of $\ell$-cyclic covers of $\mathbb{P}^1_{\mathbb{F}_q}$ of genus $g$. We assume that $q\not\equiv 0,1\mod \ell$. If $2g+2\ell-2\not\equiv0\mod (\ell-1){\rm ord}_\ell(q)$, then $\mathcal{H}_{g,\ell}$ is empty. Otherwise, the number of rational points on a random curve in $\mathcal{H}_{g,\ell}$ distributes as $\sum_{i=1}^{q+1} X_i$ as $g\to \infty$, where $X_1,\ldots, X_{q+1}$ are i.i.d.\ random variables taking the values $0$ and $\ell$ with probabilities $\frac{\ell-1}{\ell}$ and $\frac{1}{\ell}$, respectively. The novelty of our result is that it works in the absence of a primitive $\ell$-th-root of unity, the presence of which was crucial in previous studies., We have corrected a mistake in the main theorem pointed out by Will Sawin

Let $\{G_i\}$ be the random graph process: starting with an empty graph $G_0$ with $n$ vertices, in every step $i \geq 1$ the graph $G_i$ is formed by taking an edge chosen uniformly at random among the non-existing ones and adding it to the graph $G_{i - 1}$. The classical `hitting-time' result of Ajtai, Koml\'{o}s, and Szemer\'{e}di, and independently Bollob\'{a}s, states that asymptotically almost surely the graph becomes Hamiltonian as soon as the minimum degree reaches $2$, that is if $\delta(G_i) \ge 2$ then $G_i$ is Hamiltonian. We establish a resilience version of this result. In particular, we show that the random graph process almost surely creates a sequence of graphs such that for $m \geq (\tfrac{1}{6} + o(1))n\log n$ edges, the $2$-core of the graph $G_m$ remains Hamiltonian even after an adversary removes $(\tfrac{1}{2} - o(1))$-fraction of the edges incident to every vertex. A similar result is obtained for perfect matchings., Comment: 23 pages; small updates to the paper after anonymous reviewers' reports

Let $K$ be a number field, and let $d\geq 2$. A conjecture of Odoni (stated more generally for characteristic zero Hilbertian fields $K$) posits that there is a monic polynomial $f\in K[x]$ of degree $d$, and a point $x_0\in K$, such that for every $n\geq 0$, the so-called arboreal Galois group $Gal(K(f^{-n}(x_0))/K)$ is an $n$-fold wreath product of the symmetric group $S_d$. In this paper, we prove Odoni's conjecture when $d$ is even and $K$ is an arbitrary number field, and also when both $d$ and $[K:Q]$ are odd., 15 pages, 1 figure

A clique colouring of a graph is a colouring of the vertices so that no maximal clique is monochromatic (ignoring isolated vertices). The smallest number of colours in such a colouring is the clique chromatic number. In this paper, we study the asymptotic behaviour of the clique chromatic number of the random graph G(n,p) for a wide range of edge-probabilities p=p(n). We see that the typical clique chromatic number, as a function of the average degree, forms an intriguing step function., 25 pages

In this paper we define the chromatic number of a lattice: It is the least number of colors one needs to color the interiors of the cells of the Voronoi tessellation of a lattice so that no two cells sharing a facet are of the same color. We compute the chromatic number of the root lattices, their duals, and of the Leech lattice, we consider the chromatic number of lattices of Voronoi's first kind, and we investigate the asymptotic behaviour of the chromatic number of lattices when the dimension tends to infinity. We introduce a spectral lower bound for the chromatic number of lattices in spirit of Hoffman's bound for finite graphs. We compute this bound for the root lattices and relate it to the character theory of the corresponding Lie groups., (v2) 40 pages, 4 figures, 3 tables, suggestions of referee incorporated, to appear in Journal of the London Mathematical Society

In this paper, we study the existence of perfect matchings and Hamiltonian cycles in the preferential attachment model. In this model, vertices are added to the graph one by one, and each time a new vertex is created it establishes a connection with $m$ random vertices selected with probabilities proportional to their current degrees. (Constant $m$ is the only parameter of the model.) We prove that if $m \ge 1{,}260$, then asymptotically almost surely there exists a perfect matching. Moreover, we show that there exists a Hamiltonian cycle asymptotically almost surely, provided that $m \ge 29{,}500$. One difficulty in the analysis comes from the fact that vertices establish connections only with vertices that are "older" (i.e. are created earlier in the process). However, the main obstacle arises from the fact that edges in the preferential attachment model are not generated independently. In view of that, we also consider a simpler setting---sometimes called uniform attachment---in which vertices are added one by one and each vertex connects to $m$ older vertices selected uniformly at random and independently of all other choices. We first investigate the existence of perfect matchings and Hamiltonian cycles in the uniform attachment model, and then extend the argument to the preferential attachment version., Comment: 29 pages

An oriented tree $T$ on $n$ vertices is unavoidable if every tournament on $n$ vertices contains a copy of $T$. In this paper we give a sufficient condition for $T$ to be unavoidable, and use this to prove that almost all labelled oriented trees are unavoidable, verifying a conjecture of Bender and Wormald. We additionally prove that every tournament on $n + o(n)$ vertices contains a copy of every oriented tree $T$ on $n$ vertices with polylogarithmic maximum degree, improving a result of K\"uhn, Mycroft and Osthus.

Let $G=G(n)$ be a graph on $n$ vertices with maximum degree $\Delta=\Delta(n)$. Assign to each vertex $v$ of $G$ a list $L(v)$ of colors by choosing each list independently and uniformly at random from all $k$-subsets of a color set $\mathcal{C}$ of size $\sigma= \sigma(n)$. Such a list assignment is called a \emph{random $(k,\mathcal{C})$-list assignment}. In this paper, we are interested in determining the asymptotic probability (as $n \to \infty$) of the existence of a proper coloring $\varphi$ of $G$, such that $\varphi(v) \in L(v)$ for every vertex $v$ of $G$, a so-called $L$-coloring. We give various lower bounds on $\sigma$, in terms of $n$, $k$ and $\Delta$, which ensures that with probability tending to 1 as $n \to \infty$ there is an $L$-coloring of $G$. In particular, we show, for all fixed $k$ and growing $n$, that if $\sigma(n) = \omega(n^{1/k^2} \Delta^{1/k})$ and $\Delta=O\left(n^{\frac{k-1}{k(k^3+ 2k^2 - k +1)}}\right)$, then the probability that $G$ has an $L$-coloring tends to 1 as $n \rightarrow \infty$. If $k\geq 2$ and $\Delta= \Omega(n^{1/2})$, then the same conclusion holds provided that $\sigma=\omega(\Delta)$. We also give related results for other bounds on $\Delta$, when $k$ is constant or a strictly increasing function of $n$.

Let $H$ be a fixed graph and $\mathcal{G}$ a subcritical graph class. In this paper we show that the number of occurrences of $H$ (as a subgraph) in a uniformly at random graph of size $n$ in $\mathcal{G}$ follows a normal limiting distribution with linear expectation and variance. The main ingredient in our proof is the analytic framework developed by Drmota, Gittenberger and Morgenbesser to deal with infinite systems of functional equations. As a case study, we get explicit expressions for the number of triangles and cycles of length four for the family of series-parallel graphs., Comment: 32 pages, 6 figures

Given a finite group G and a field F, a G-set X gives rise to an F[G]-permutation module F[X]. This defines a map from the Burnside ring of G to its representation ring over F. It is an old problem in representation theory, with wide-ranging applications in algebra, number theory, and geometry, to give explicit generators of the kernel K_F(G) of this map, i.e. to classify pairs of G-sets X, Y such that F[X] is isomorphic to F[Y]. When F has characteristic 0, a complete description of K_F(G) is now known. In this paper, we give a similar description of K_F(G) when F is a field of characteristic p>0 in all but the most complicated case, which is when G has a subquotient that is a non-p-hypo-elementary (p,p)-Dress group., 18 pages; minor corrections and improvements. Final version to appear in Bull. London Math. Soc

Let D(n,p) be the random directed graph on n vertices where each of the n(n-1) possible arcs is present independently with probability p. A celebrated result of Frieze shows that if $p\ge(\log n+\omega(1))/n$ then D(n,p) typically has a directed Hamilton cycle, and this is best possible. In this paper, we obtain a strengthening of this result, showing that under the same condition, the number of directed Hamilton cycles in D(n,p) is typically $n!(p(1+o(1)))^{n}$. We also prove a hitting-time version of this statement, showing that in the random directed graph process, as soon as every vertex has in-/out-degrees at least 1, there are typically $n!(\log n/n(1+o(1)))^{n}$ directed Hamilton cycles.

Graph bootstrap percolation, introduced by Bollob\'as in 1968, is a cellular automaton defined as follows. Given a "small" graph $H$ and a "large" graph $G = G_0 \subseteq K_n$, in consecutive steps we obtain $G_{t+1}$ from $G_t$ by adding to it all new edges $e$ such that $G_t \cup e$ contains a new copy of $H$. We say that $G$ percolates if for some $t \geq 0$, we have $G_t = K_n$. For $H = K_r$, the question about the size of the smallest percolating graphs was independently answered by Alon, Frankl and Kalai in the 1980's. Recently, Balogh, Bollob\'as and Morris considered graph bootstrap percolation for $G = G(n,p)$ and studied the critical probability $p_c(n,K_r)$, for the event that the graph percolates with high probability. In this paper, using the same setup, we determine, up to a logarithmic factor, the critical probability for percolation by time $t$ for all $1 \leq t \leq C \log\log n$., Comment: 18 pages, 3 figures

There is always a natural embedding of $S_s\wr S_k$ into the linear programming (LP) relaxation permutation symmetry group of an orthogonal array integer linear programming (ILP) formulation with equality constraints. The point of this paper is to prove that in the $2$ level, strength $1$ case the LP relaxation permutation symmetry group of this formulation is isomorphic to $S_2\wr S_k$ for all $k$, and in the $2$ level, strength $2$ case it is isomorphic to $S_2^k\rtimes S_{k+1}$ for $k\geq 4$. The strength $2$ result reveals previously unknown permutation symmetries that can not be captured by the natural embedding of $S_2\wr S_k$. We also conjecture a complete characterization of the LP relaxation permutation symmetry group of the ILP formulation., Comment: 17 pages

A classical theorem of Ghouila-Houri from 1960 asserts that every directed graph on $n$ vertices with minimum out-degree and in-degree at least $n/2$ contains a directed Hamilton cycle. In this paper we extend this theorem to a random directed graph ${\mathcal D}(n,p)$, that is, a directed graph in which every ordered pair $(u,v)$ becomes an arc with probability $p$ independently of all other pairs. Motivated by the study of resilience of properties of random graphs, we prove that if $p \gg \log n/\sqrt{n}$, then a.a.s. every subdigraph of ${\mathcal D}(n,p)$ with minimum out-degree and in-degree at least $(1/2 + o(1)) n p$ contains a directed Hamilton cycle. The constant $1/2$ is asymptotically best possible. Our result also strengthens classical results about the existence of directed Hamilton cycles in random directed graphs., Comment: 35 pages, 1 figure

In this paper, we give the first examples of connected Polish groups that have ample generics, answering a question of Kechris and Rosendal. We show that any Polish group with ample generics embeds into a connected Polish group with ample generics and that full groups of type III hyperfinite ergodic equivalence relations have ample generics. We also sketch a proof of the following result: the full group of any type III ergodic equivalence relation has topological rank 2., Comment: New version mentioning the results Malicki obtained independently and simultaneously http://arxiv.org/abs/1503.03919, which also answer Kechris and Rosendal's question in a different way. Comments welcome!