# Algorithmic Lattice Path Counting Using the Kernel Method [F050-04]

### Project Lead

### Project Duration

01/03/2013 - 31/12/2015### Project URL

Go to Website## Publications

### 2016

### Workshop on Symbolic Combinatorics and Algorithmic Differential Algebra

#### Manuel Kauers, Peter Paule, Greg Reid

ACM Communications in Computer Algebra 50(Issue 1), pp. 27-34. March 2016. 1932-2240. [pdf]@

author = {Manuel Kauers and Peter Paule and Greg Reid},

title = {{Workshop on Symbolic Combinatorics and Algorithmic Differential Algebra}},

language = {english},

journal = {ACM Communications in Computer Algebra},

volume = {50},

number = {Issue 1},

pages = {27--34},

isbn_issn = {1932-2240},

year = {2016},

month = {March},

refereed = {no},

length = {8}

}

**article**{RISC5284,author = {Manuel Kauers and Peter Paule and Greg Reid},

title = {{Workshop on Symbolic Combinatorics and Algorithmic Differential Algebra}},

language = {english},

journal = {ACM Communications in Computer Algebra},

volume = {50},

number = {Issue 1},

pages = {27--34},

isbn_issn = {1932-2240},

year = {2016},

month = {March},

refereed = {no},

length = {8}

}

### A New Witness Identity for $11|p(11n+6)$

#### Peter Paule, Cristian-Silviu Radu

In: Analytic Number Theory, Modular Forms and q-Hypergeometric Series, George E. Andrews, Frank Garvan (ed.), pp. 625-640. 2016. Springer, 2194-1009. [pdf]@

author = {Peter Paule and Cristian-Silviu Radu},

title = {{A New Witness Identity for $11|p(11n+6)$}},

booktitle = {{Analytic Number Theory, Modular Forms and q-Hypergeometric Series}},

language = {english},

pages = {625--640},

publisher = {Springer},

isbn_issn = { 2194-1009},

year = {2016},

editor = { George E. Andrews and Frank Garvan},

refereed = {yes},

length = {16}

}

**inproceedings**{RISC5329,author = {Peter Paule and Cristian-Silviu Radu},

title = {{A New Witness Identity for $11|p(11n+6)$}},

booktitle = {{Analytic Number Theory, Modular Forms and q-Hypergeometric Series}},

language = {english},

pages = {625--640},

publisher = {Springer},

isbn_issn = { 2194-1009},

year = {2016},

editor = { George E. Andrews and Frank Garvan},

refereed = {yes},

length = {16}

}

### 2015

### Phase Transition of Random Non-Uniform Hypergraphs

#### Élie de Panafieu

Journal of Discrete Algorithms, pp. ?-?. 2015. ????. [pdf]@

author = {Élie de Panafieu},

title = {{Phase Transition of Random Non-Uniform Hypergraphs}},

language = {english},

abstract = {Non-uniform hypergraphs appear in various domains of computer science as in the satisfiability problems and in data analysis.We analyse a general model where the probability for an edge of size~$t$ to belong to the hypergraph depends of a parameter~$\omega_t$ of the model. It is a natural generalization of the models of graphs used by Flajolet, Knuth and Pittel [1989] and Janson, Knuth, \L{}uczak and Pittel [1993]. The present paper follows the same general approach based on analytic combinatorics. We show that many analytic tools developed for the analysis of graphs can be extended surprisingly well to non-uniform hypergraphs. More specifically, we analyze their typical structure before and near the birth of the \emph{complex} components, that are the connected components with more than one cycle. We derive the asymptotic number of sparse connected hypergraphs as their complexity, defined as the \emph{excess}, increases. Although less natural than the number of edges, this parameter allows a precise description of the structure of hypergraphs. Finally, we compute some statistics of the model to link number of edges and excess. },

journal = {Journal of Discrete Algorithms},

pages = {?--?},

isbn_issn = {????},

year = {2015},

refereed = {yes},

length = {19}

}

**article**{RISC5099,author = {Élie de Panafieu},

title = {{Phase Transition of Random Non-Uniform Hypergraphs}},

language = {english},

abstract = {Non-uniform hypergraphs appear in various domains of computer science as in the satisfiability problems and in data analysis.We analyse a general model where the probability for an edge of size~$t$ to belong to the hypergraph depends of a parameter~$\omega_t$ of the model. It is a natural generalization of the models of graphs used by Flajolet, Knuth and Pittel [1989] and Janson, Knuth, \L{}uczak and Pittel [1993]. The present paper follows the same general approach based on analytic combinatorics. We show that many analytic tools developed for the analysis of graphs can be extended surprisingly well to non-uniform hypergraphs. More specifically, we analyze their typical structure before and near the birth of the \emph{complex} components, that are the connected components with more than one cycle. We derive the asymptotic number of sparse connected hypergraphs as their complexity, defined as the \emph{excess}, increases. Although less natural than the number of edges, this parameter allows a precise description of the structure of hypergraphs. Finally, we compute some statistics of the model to link number of edges and excess. },

journal = {Journal of Discrete Algorithms},

pages = {?--?},

isbn_issn = {????},

year = {2015},

refereed = {yes},

length = {19}

}

### 2014

### Analytic Description of the Phase Transition of Inhomogeneous Multigraphs

#### Élie de Panafieu, Vlady Ravelomanana

European Journal of Combinatorics, pp. -. 2014. Elsevier, ????. [pdf]@

author = {Élie de Panafieu and Vlady Ravelomanana},

title = {{Analytic Description of the Phase Transition of Inhomogeneous Multigraphs}},

language = {english},

abstract = {We introduce a new model of random multigraphs with colored vertices and weighted edges. It is similar to the "inhomogeneous random graph" model of Söderberg (2002), extended by Bollobás, Janson and Riordan (2007). By means of analytic combinatorics, we then analyze the birth of "complex components", which are components with at least two cycles.We apply those results to give a complete picture of the finite size scaling and the critical exponents associated to a rather broad family of decision problems. As applications, we derive new proofs of known results on the 2-colorability problem, already investigated by Pittel and Yeum (2010), and on the enumeration of properly q-colored multigraphs, analyzed by Wright (1972). We also obtain new results on the phase transition of the satisfiability of quantified 2-Xor-formulas, a problem introduced by Creignou, Daudé and Egly (2007).},

journal = {European Journal of Combinatorics},

pages = {--},

publisher = {Elsevier},

isbn_issn = {????},

year = {2014},

refereed = {yes},

keywords = {generating functions, analytic combinatorics, inhomogeneous graphs, phase transition},

sponsor = {ANR Boole, ANR Magnum, Austrian Science Fund (FWF) grant F5004},

length = {15}

}

**article**{RISC5061,author = {Élie de Panafieu and Vlady Ravelomanana},

title = {{Analytic Description of the Phase Transition of Inhomogeneous Multigraphs}},

language = {english},

abstract = {We introduce a new model of random multigraphs with colored vertices and weighted edges. It is similar to the "inhomogeneous random graph" model of Söderberg (2002), extended by Bollobás, Janson and Riordan (2007). By means of analytic combinatorics, we then analyze the birth of "complex components", which are components with at least two cycles.We apply those results to give a complete picture of the finite size scaling and the critical exponents associated to a rather broad family of decision problems. As applications, we derive new proofs of known results on the 2-colorability problem, already investigated by Pittel and Yeum (2010), and on the enumeration of properly q-colored multigraphs, analyzed by Wright (1972). We also obtain new results on the phase transition of the satisfiability of quantified 2-Xor-formulas, a problem introduced by Creignou, Daudé and Egly (2007).},

journal = {European Journal of Combinatorics},

pages = {--},

publisher = {Elsevier},

isbn_issn = {????},

year = {2014},

refereed = {yes},

keywords = {generating functions, analytic combinatorics, inhomogeneous graphs, phase transition},

sponsor = {ANR Boole, ANR Magnum, Austrian Science Fund (FWF) grant F5004},

length = {15}

}

### Ore Polynomials in Sage

#### Manuel Kauers, Maximilian Jaroschek, Fredrik Johansson

In: Computer Algebra and Polynomials, Jaime Gutierrez, Josef Schicho, Martin Weimann (ed.), Lecture Notes in Computer Science , pp. ?-?. 2014. tba. [pdf] [ps]@

author = {Manuel Kauers and Maximilian Jaroschek and Fredrik Johansson},

title = {{Ore Polynomials in Sage}},

booktitle = {{Computer Algebra and Polynomials}},

language = {english},

abstract = {We present a Sage implementation of Ore algebras. The main features for the mostcommon instances include basic arithmetic and actions; GCRD and LCLM; D-finiteclosure properties; natural transformations between related algebras; guessing;desingularization; solvers for polynomials, rational functions and (generalized)power series. This paper is a tutorial on how to use the package.},

series = {Lecture Notes in Computer Science},

pages = {?--?},

isbn_issn = {tba},

year = {2014},

editor = {Jaime Gutierrez and Josef Schicho and Martin Weimann},

refereed = {yes},

length = {17}

}

**inproceedings**{RISC4944,author = {Manuel Kauers and Maximilian Jaroschek and Fredrik Johansson},

title = {{Ore Polynomials in Sage}},

booktitle = {{Computer Algebra and Polynomials}},

language = {english},

abstract = {We present a Sage implementation of Ore algebras. The main features for the mostcommon instances include basic arithmetic and actions; GCRD and LCLM; D-finiteclosure properties; natural transformations between related algebras; guessing;desingularization; solvers for polynomials, rational functions and (generalized)power series. This paper is a tutorial on how to use the package.},

series = {Lecture Notes in Computer Science},

pages = {?--?},

isbn_issn = {tba},

year = {2014},

editor = {Jaime Gutierrez and Josef Schicho and Martin Weimann},

refereed = {yes},

length = {17}

}

### Hypercontractive inequalities via SOS, and the Frankl-R\"odl graph

#### Manuel Kauers, Ryan ODonnell, Li-Yang Tan, Yuan Zhou

In: Proceedings of SODA'14, tba (ed.), pp. ?-?. 2014. tba. [pdf]@

author = {Manuel Kauers and Ryan ODonnell and Li-Yang Tan and Yuan Zhou},

title = {{Hypercontractive inequalities via SOS, and the Frankl-R\"odl graph}},

booktitle = {{Proceedings of SODA'14}},

language = {english},

pages = {?--?},

isbn_issn = {tba},

year = {2014},

editor = {tba},

refereed = {yes},

length = {15}

}

**inproceedings**{RISC4829,author = {Manuel Kauers and Ryan ODonnell and Li-Yang Tan and Yuan Zhou},

title = {{Hypercontractive inequalities via SOS, and the Frankl-R\"odl graph}},

booktitle = {{Proceedings of SODA'14}},

language = {english},

pages = {?--?},

isbn_issn = {tba},

year = {2014},

editor = {tba},

refereed = {yes},

length = {15}

}

### On the length of integers in telescopers for proper hypergeometric terms

#### Manuel Kauers, Lily Yen

Journal of Symbolic Computation, pp. ?-?. 2014. ISSN 0747-7171. to appear. [pdf] [ps]@

author = {Manuel Kauers and Lily Yen},

title = {{On the length of integers in telescopers for proper hypergeometric terms}},

language = {english},

journal = {Journal of Symbolic Computation},

pages = {?--?},

isbn_issn = {ISSN 0747-7171},

year = {2014},

note = {to appear},

refereed = {yes},

length = {15}

}

**article**{RISC4955,author = {Manuel Kauers and Lily Yen},

title = {{On the length of integers in telescopers for proper hypergeometric terms}},

language = {english},

journal = {Journal of Symbolic Computation},

pages = {?--?},

isbn_issn = {ISSN 0747-7171},

year = {2014},

note = {to appear},

refereed = {yes},

length = {15}

}

### Computer Algebra

#### Manuel Kauers

In: Handbook of Combinatorics, Miklos Bona (ed.), pp. ?-?. 2014. Taylor and Francis, tba.@

author = {Manuel Kauers},

title = {{Computer Algebra}},

booktitle = {{Handbook of Combinatorics}},

language = {english},

pages = {?--?},

publisher = {Taylor and Francis},

isbn_issn = {tba},

year = {2014},

editor = {Miklos Bona},

refereed = {yes},

length = {59}

}

**incollection**{RISC4956,author = {Manuel Kauers},

title = {{Computer Algebra}},

booktitle = {{Handbook of Combinatorics}},

language = {english},

pages = {?--?},

publisher = {Taylor and Francis},

isbn_issn = {tba},

year = {2014},

editor = {Miklos Bona},

refereed = {yes},

length = {59}

}

### Bounds for D-Finite Closure Properties

#### Manuel Kauers

In: Proceedings of ISSAC 2014, Katsusuke Nabeshima (ed.), pp. 288-295. 2014. isbn 978-1-4503-2501-1/14/07. [pdf]@

author = {Manuel Kauers},

title = {{Bounds for D-Finite Closure Properties}},

booktitle = {{Proceedings of ISSAC 2014}},

language = {english},

pages = {288--295},

isbn_issn = {isbn 978-1-4503-2501-1/14/07},

year = {2014},

editor = {Katsusuke Nabeshima},

refereed = {yes},

length = {8}

}

**inproceedings**{RISC4989,author = {Manuel Kauers},

title = {{Bounds for D-Finite Closure Properties}},

booktitle = {{Proceedings of ISSAC 2014}},

language = {english},

pages = {288--295},

isbn_issn = {isbn 978-1-4503-2501-1/14/07},

year = {2014},

editor = {Katsusuke Nabeshima},

refereed = {yes},

length = {8}

}

### On 3-dimensional lattice walks confined to the positive octant

#### Alin Bostan, Mireille Bousquet-Melou, Manuel Kauers, Stephen Melczer

Annals of Combinatorics, pp. ??-??. 2014. ISSN 0218-0006. to appear. [pdf]@

author = {Alin Bostan and Mireille Bousquet-Melou and Manuel Kauers and Stephen Melczer},

title = {{ On 3-dimensional lattice walks confined to the positive octant}},

language = {english},

journal = {Annals of Combinatorics},

pages = {??--??},

isbn_issn = {ISSN 0218-0006},

year = {2014},

note = {to appear},

refereed = {yes},

length = {36}

}

**article**{RISC5082,author = {Alin Bostan and Mireille Bousquet-Melou and Manuel Kauers and Stephen Melczer},

title = {{ On 3-dimensional lattice walks confined to the positive octant}},

language = {english},

journal = {Annals of Combinatorics},

pages = {??--??},

isbn_issn = {ISSN 0218-0006},

year = {2014},

note = {to appear},

refereed = {yes},

length = {36}

}

### A Generalized Apagodu-Zeilberger Algorithm

#### Shaoshi Chen, Manuel Kauers, Christoph Koutschan

In: Proceedings of ISSAC 2014, Katsusuke Nabeshima (ed.), pp. 107-114. 2014. ISBN 978-1-4503-2501-1. [pdf]@

author = {Shaoshi Chen and Manuel Kauers and Christoph Koutschan},

title = {{A Generalized Apagodu-Zeilberger Algorithm}},

booktitle = {{Proceedings of ISSAC 2014}},

language = {english},

pages = {107--114},

isbn_issn = {ISBN 978-1-4503-2501-1},

year = {2014},

editor = {Katsusuke Nabeshima},

refereed = {yes},

length = {8}

}

**inproceedings**{RISC5034,author = {Shaoshi Chen and Manuel Kauers and Christoph Koutschan},

title = {{A Generalized Apagodu-Zeilberger Algorithm}},

booktitle = {{Proceedings of ISSAC 2014}},

language = {english},

pages = {107--114},

isbn_issn = {ISBN 978-1-4503-2501-1},

year = {2014},

editor = {Katsusuke Nabeshima},

refereed = {yes},

length = {8}

}