Department of Applied Mathematics

Discrete Applied Mathematics

The discrete applied mathematics research group studies theoretical, algorithmic, and computational problems in the fields of graph theory, discrete optimization, combinatorics, and algebraic geometry, with applications in biology, computer science, physics, management sciences, and engineering. Network science, with fundamental concepts from graph theory and computational techniques from discrete optimization, is widely applied to problems arising in transportation/communication, distribution, and security of resources and information. Combinatorial search incorporates graph theory, set systems, and algorithms to tackle information-theoretic questions in topics such as message transmission, data compression, and identification of defective samples in a population. Computational algebra joins tools from algebraic geometry with randomized algorithms from discrete geometry to develop methods to solve systems of polynomial equations arising in statistical inference and mathematical modeling.


Read more

    Faculty with a Primary or Secondary Interest in Discrete Applied Mathematics

    Michael Pelsmajer
    Associate Professor of Applied Mathematics
    Sonja Petrovic
    Associate Professor of Applied Mathematics
    Robert Ellis
    Associate Professor of Applied Mathematics
    Despina Stasi
    Associate Teaching Professor of Applied Mathematics
    Hemanshu Kaul
    Co-Director, M.S. in Computational Decision Science and Operations Research (CDSOR) Associate Professor of Applied Mathematics
    Maggie Cheng
    Professor of Applied Mathematics Director, Center for Interdisciplinary Scientific Computation
    Associate Teaching Professor of Applied Mathematics

    Related Seminars

    Ph.D. Students

    • Adam Rumpf
    • William Schwartz

    Recent Research Grants

    • NSF DMS-1522662 (PIs S. Petrovic and D. Stasi): Randomized Algorithms in Computational Algebra, 2015-2019.

    Recent Publications

    • H. Kaul and C. Mitillos. On Graph Fall-Coloring: Existence and Constructions. Submitted, 2016.
    • J. A. De Loera, S. Petrovic, L. Silverstein, D. Stasi, and D. Wilburne. Random Monomial Ideals. Journal of Algebra (2019), Vol. 519, No. 1, pp. 440-473.
    • S. Petrovic. What is ... a Markov Basis? Notices of the American Mathematical Society (August, 2019).
    • S. Petrovic, A. Thoma, and M. Vladoiu. Hypergraph Encodings of Arbitrary Toric Ideals, Journal of Combinatorial Theory, Series A (2019), Vol. 166, pp. 11-41.
    • S. Petrović, A. Thoma, and M. Vladoiu. Bouquet Algebra of Toric Ideals. Journal of Algebra (2018), Vol. 512, pp. 493-525.
    • A. Bonato, X. Pérez-Giménez, P. Prałat, and B. Reiniger. The Game of Overprescribed Cops and Robbers Played on Graphs. Graphs and Combinatorics (2017), Vol. 33, Issue 4, pp. 801-815.
    • J. Carraher, W. Kinnersley, B. Reiniger, and D. B. West. The Game Saturation Number of a Graph. Journal of Graph Theory (2017), Vol. 85, Issue 2, pp. 481-495.
    • A. Corso, U. Nagel, S. Petrovic, and C. Yuen. Blow-up Algebras, Determinantal Ideals, and Dedekind-Mertens-Like Formulas. Forum Mathematicum (2017), Vol. 29, Issue 4, pp. 799-830.
    • M. Dewar, J. Healy, X. Pérez-Giménez, P. Prałat, J. Proos, B. Reiniger, and K. Ternovsky. Subgraphs in Non-Uniform Random Hypergraphs. Algorithms and Models for the Web Graph, 13th International Workshop, WAW 2016, Montreal, QC, Canada, December 14-15, 2016, Proceedings (A. Bonato, F. C. Graham, and P. Prałat, eds.), Lecture Notes in Computer Science, Vol. 10088, pp. 140-151, Springer, 2017.
    • M. Ferrara, B. Kay, L. Kramer, R. R. Martin, B. Reiniger, H. C. Smith, and E. Sullivan. The Saturation Number of Induced Subposets of the Boolean Lattice. Discrete Mathematics (2017), Vol. 340, Issue 10, pp. 2479-2487.
    • R. Fulek, M. J. Pelsmajer, and M. Schaefer. Hanani-Tutte for Radial Planarity. Journal of Graph Algorithms and Applications (2017), Vol. 21, No. 1, pp. 135-154.
    • E. Gross, S. Petrovic, and D. Stasi. Goodness of Fit for Log-Linear Network Models: Dynamic Markov Bases Using Hypergraphs. Annals of the Institute of Statistical Mathematics (2017), Vol. 69, Issue 3, pp. 673-704.
    • V. Karwa, M. J. Pelsmajer, S. Petrovic, D. Stasi, and D. Wilburne. Statistical Models for Cores Decomposition of an Undirected Random Graph. Electronic Journal of Statistics (2017), Vol. 11, No. 1, pp. 1949-1982.
    • S. Petrovic. A Survey of Discrete Methods in (Algebraic) Statistics for Networks. Algebraic and Geometric Methods in Discrete Mathematics (H. A. Harrington, M. Omar, and M. Wright, eds.), Contemporary Mathematics, Vol. 685, pp. 260-281, American Mathematical Society, 2017.
    • R. H. Sloan, D. Stasi and G. Túran. Hydras: Directed Hypergraphs and Horn Formulas. Theoretical Computer Science (2017), Vol. 658, Part B, pp. 417-428.
    • N. Alon, A. V. Kostochka, B. Reiniger, D. B. West, and X. Zhu. Coloring, Sparseness, and Girth. Israel Journal of Mathematics (2016), Vol. 214, Issue 1, pp. 315-331.
    • J. A. De Loera, S. Petrovic, and D. Stasi. Random Sampling in Computational Algebra: Helly Numbers and Violator Spaces. Journal of Symbolic Computation (2016), Vol. 77, pp.1-15.
    • R. Fulek, M. J. Pelsmajer, and M. Schaefer. Hanani-Tutte for Radial Planarity II. Graph Drawing and Network Visualization, 24th International Symposium, GD 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers (Y. Hu and M. Nöllenburg, eds.), Lecture Notes in Computer Science, Vol. 9801, pp. 468-481, Springer, 2016.
    • B. Reiniger and E. Yeager. Large Subposets with Small Dimension. Order (2016), Vol. 33, Issue 1, pp. 81-84.
    • S. Antaris, D. Stasi, M. Högqvist, G. Pallis, and M. D. Dikaiakos. A Socio-Aware Decentralized Topology Construction Protocol. HOTWEB'15, Proceedings of the 2015 Third IEEE Workshop on Hot Topics in Web Systems and Technologies (Hotweb), pp. 91-96, Institute of Electrical and Electronics Engineers, 2015.
    • J. A. De Loera, S. Marguiles, M. Pernpeintner, E. Reidl, D. Rolnic, G. Spencer, D. Stasi, and J. Swenson. Graph-Coloring Ideals: Nullstellensatz Certificates, Gröbner Bases for Chordal Graphs, and Hardness of Gröbner Bases. ISSAC’15, Proceedings of the 2015 ACM, International Symposium on Symbolic and Algebraic Computation, July 6-9, 2015, Bath, UK, pp. 133-140, The Association for Computing Machinery, Inc., 2015.
    • R. Fulek, M. J. Pelsmajer, and M. Schaefer. Hanani-Tutte for Radial Planarity. Graph Drawing and Network Visualization, 23rd International Symposium, GD 2015, Los Angeles, CA, USA, September 24-26, 2015, Revised Selected Papers (E. D. Giacomo and A. Lubiw, eds.), Lecture Notes in Computer Science, Vol. 9411, pp. 99-110, Springer, 2015.
    • A. V. Kostochka and B. Reiniger. The Minimum Number of Edges in a 4-Critical Graph that is Bipartite Plus 3 Edges. European Journal of Combinatorics (2015), Vol. 46, pp. 89-94.
    • A. Kündgen, M. J. Pelsmajer, and R. Ramamurthi. Finding Minors in Graphs with a Given Path Structure. Journal of Graph Theory (2015), Vol. 79, Issue 1, pp. 30-47.