The discrete mathematics 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.
Faculty with primary interests in discrete applied mathematics
- Adam Rumpf
- William Schwartz
- Dane Wilburne
RECENT RESEARCH GRANTS
- NSF DMS-1522662 (PIs S. Petrovic and D. Stasi): Randomized Algorithms in Computational Algebra, 2015-2018.
- J. A. De Loera, S. Petrovic, L. Silverstein, D. Stasi, and D. Wilburne. Random Monomial Ideals. Submitted, 2017. arXiv:1701.07130
- A. Frieze, X. Pérez-Giménez, P. Prałat, and B. Reiniger. Perfect Matchings and Hamiltonian Cycles in the Preferential Attachment Model. Submitted, 2016. arXiv:1610:07988
- H. Kaul and C. Mitillos. On Graph Fall-Coloring: Existence and Constructions. Submitted, 2016.
- S. Petrović, A. Thoma, and M. Vladoiu. Bouquet Algebra of Toric Ideals. Submitted, 2016. arXiv:1507.02740
- C. Cox, M. Ferrara, R. R. Martin, and B. Reiniger. Chvátal-Type Results for Degree Sequence Ramsey Numbers. Submitted, 2015. arXiv:1510:04843
- S. Loeb, T. Mahoney, B. Reiniger, and J. Wise. Dynamic Coloring Parameters for Graphs with Given Genus. Submitted, 2015. arXiv:1511.03983
- J. N. Cooper and R. B. Ellis. Linearly Bounded Liars, Adaptive Covering Codes, and Deterministic Random Walks. To appear in Journal of Combinatorics, 2017.
- 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.