3 Search Results for "Gao, Zhicheng"

Document
DOI: 10.4230/LIPIcs.AofA.2024.1
Fringe Trees for Random Trees with Given Vertex Degrees

Authors: Gabriel Berzunza Ojeda, Cecilia Holmgren, and Svante Janson

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
We prove that the number of fringe subtrees, isomorphic to a given tree, in uniformly random trees with given vertex degrees, asymptotically follows a normal distribution. As an application, we establish the same asymptotic normality for random simply generated trees (conditioned Galton-Watson trees). Our approach relies on an extension of Gao and Wormald’s (2004) theorem to the multivariate setting.
Cite as

Gabriel Berzunza Ojeda, Cecilia Holmgren, and Svante Janson. Fringe Trees for Random Trees with Given Vertex Degrees. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 1:1-1:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{berzunzaojeda_et_al:LIPIcs.AofA.2024.1,
  author =	{Berzunza Ojeda, Gabriel and Holmgren, Cecilia and Janson, Svante},
  title =	{{Fringe Trees for Random Trees with Given Vertex Degrees}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{1:1--1:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.1},
  URN =		{urn:nbn:de:0030-drops-204369},
  doi =		{10.4230/LIPIcs.AofA.2024.1},
  annote =	{Keywords: Conditioned Galton-Watson trees, fringe trees, simply generated trees, uniformly random trees with given vertex degrees}
}
Document
DOI: 10.4230/LIPIcs.AofA.2022.9
Improved Error Bounds for the Number of Irreducible Polynomials and Self-Reciprocal Irreducible Monic Polynomials with Prescribed Coefficients over a Finite Field

Authors: Zhicheng Gao

Published in: LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)

Abstract
A polynomial is called self-reciprocal (or palindromic) if the sequence of its coefficients is palindromic. In this paper we obtain improved error bounds for the number of irreducible polynomials and self-reciprocal irreducible monic polynomials with prescribed coefficients over a finite field. The improved bounds imply that self-reciprocal irreducible monic polynomials with degree 2d and prescribed 𝓁 leading coefficients always exist provided that 𝓁 is slightly less than d/2.
Cite as

Zhicheng Gao. Improved Error Bounds for the Number of Irreducible Polynomials and Self-Reciprocal Irreducible Monic Polynomials with Prescribed Coefficients over a Finite Field. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 225, pp. 9:1-9:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gao:LIPIcs.AofA.2022.9,
  author =	{Gao, Zhicheng},
  title =	{{Improved Error Bounds for the Number of Irreducible Polynomials and Self-Reciprocal Irreducible Monic Polynomials with Prescribed Coefficients over a Finite Field}},
  booktitle =	{33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
  pages =	{9:1--9:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-230-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{225},
  editor =	{Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2022.9},
  URN =		{urn:nbn:de:0030-drops-160958},
  doi =		{10.4230/LIPIcs.AofA.2022.9},
  annote =	{Keywords: finite fields, irreducible polynomials, prescribed coefficients, generating functions, Weil bounds, self-reciprocal}
}
Document
DOI: 10.4230/LIPIcs.AofA.2020.13
Counting Cubic Maps with Large Genus

Authors: Zhicheng Gao and Mihyun Kang

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)

Abstract
We derive an asymptotic expression for the number of cubic maps on orientable surfaces when the genus is proportional to the number of vertices. Let Σ_g denote the orientable surface of genus g and θ=g/n∈ (0,1/2). Given g,n∈ ℕ with g→ ∞ and n/2-g→ ∞ as n→ ∞, the number C_{n,g} of cubic maps on Σ_g with 2n vertices satisfies C_{n,g} ∼ (g!)² α(θ) β(θ)ⁿ γ(θ)^{2g}, as g→ ∞, where α(θ),β(θ),γ(θ) are differentiable functions in (0,1/2). This also leads to the asymptotic number of triangulations (as the dual of cubic maps) with large genus. When g/n lies in a closed subinterval of (0,1/2), the asymptotic formula can be obtained using a local limit theorem. The saddle-point method is applied when g/n→ 0 or g/n→ 1/2.
Cite as

Zhicheng Gao and Mihyun Kang. Counting Cubic Maps with Large Genus. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gao_et_al:LIPIcs.AofA.2020.13,
  author =	{Gao, Zhicheng and Kang, Mihyun},
  title =	{{Counting Cubic Maps with Large Genus}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{13:1--13:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-147-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{159},
  editor =	{Drmota, Michael and Heuberger, Clemens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.13},
  URN =		{urn:nbn:de:0030-drops-120437},
  doi =		{10.4230/LIPIcs.AofA.2020.13},
  annote =	{Keywords: cubic maps, triangulations, cubic graphs on surfaces, generating functions, asymptotic enumeration, local limit theorem, saddle-point method}
}
  • Refine by Author
  • 2 Gao, Zhicheng
  • 1 Berzunza Ojeda, Gabriel
  • 1 Holmgren, Cecilia
  • 1 Janson, Svante
  • 1 Kang, Mihyun

  • Refine by Classification
  • 2 Mathematics of computing → Enumeration
  • 2 Mathematics of computing → Generating functions
  • 1 Mathematics of computing

  • Refine by Keyword
  • 2 generating functions
  • 1 Conditioned Galton-Watson trees
  • 1 Weil bounds
  • 1 asymptotic enumeration
  • 1 cubic graphs on surfaces
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2020
  • 1 2022
  • 1 2024

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact