Mohamed Omar
Bio/Contact

Teaching

Outreach

Talks

Welcome to my website! I am an Assistant Professor in the Department of Mathematics at Harvey Mudd College.

I am interested in seeing algebra come alive in discrete mathematics, primarily in combinatorics, graph theory and discrete/convex geometry. I am also interested in enumerative and geometric combinatorics. My articles are below.

1. Peaks on Graphs
in preparation
w/ Alex Diaz-Lopez, Lucas Everham, Pamela E. Harris, Erik Insko, Vince Marcantonio
• We generalize the notion of peak sets in permutations to peak sets in graphs (peak sets on permutations being the case of the path graph). We obtain a recursive formula that allows us to compute the number of labelings of the vertex set of a graph with a prescribed peak set. This generalizes the work of Billey, Burdzy and Sagan.

2. Neural Ideal Preserving Homomorphisms
in preparation
w/ R. Amzi Jeffs, Nora Youngs
• Curto et. al introduced the neural ring, an algebraic structure used to infer about the geometry of place fields. In this article, we dig deeper into this algebra, determining all homomorphisms that preserve neural ideals.

3. A Proof of the Peak Polynomial Positivity Conjecture
submitted, 7 pp
w/ Alex Diaz-Lopez, Pamela E. Harris, Erik Insko
• We say that a permutation π = π_1 π_2 ··· π_n in S_n has a peak at index i if π_{i−1} < π_i > π_{i+1}. Let P(π) denote the set of indices where π has a peak. Given a set S of positive integers, we define P_S(n) = {π ∈ S_n : P(π) = S}. In 2013 Billey, Burdzy, and Sagan showed that for subsets of positive integers S and sufficiently large n, |P_S(n)| = p_S(n) 2^{n−|S|−1} where p_S(x) is a polynomial depending on S. They gave a recursive formula for p_S(x) involving an alternating sum, and they conjectured that the coefficients of p_S(x) expanded in a binomial coefficient basis centered at max(S) are all nonnegative. In this paper we introduce a new recursive formula for |P_S(n)| without alternating sums, and we use this recursion to prove that their conjecture is true.

4. Sparse Neural Codes
submitted, 12 pp
w/ R. Amzi Jeffs, Natchanon Suaysom, Aleina Wachtel, Nora Youngs
• Determining how the brain stores information is one of the most pressing problems in neuroscience. In many instances, the collection of stimuli for a given neuron can be modeled by a convex set in R^d. Combinatorial objects known as neural codes can then be used to extract features of the space covered by these convex regions. We apply results from convex geometry to determine which neural codes can be realized by arrangements of open convex sets. We restrict our attention primarily to sparse codes in low dimensions. We find that intersection-completeness characterizes realizable 2-sparse codes, and show that any realizable 2-sparse code has embedding dimension at most 3. Furthermore, we prove that in R^2 and R^3, realizations of 2-sparse codes using closed sets are equivalent to those with open sets, and this allows us to provide some preliminary results on distinguishing which 2-sparse codes have embedding dimension at most 2.

5. The q-analog of Kostant's partition function and the highest root of the classical Lie algebras
submitted, 21 pp
w/ Pamela E. Harris, Erik Insko
• Kostant’s partition function counts the number of ways to represent a particular vector (weight) as a nonnegative integral sum of positive roots of a Lie algebra. For a given weight the q-analog of Kostant’s partition function is a polynomial where the coefficient of q^k is the number of ways the weight can be written as a nonnegative integral sum of exactly k positive roots. In this paper we determine generating functions for the q-analog of Kostant’s partition function when the weight in question is the highest root of the classical Lie algebras of types B, C and D.

6. What makes a neural code convex?
submitted, 28 pp
w/ Carina Curto, Elizabeth Gross, Jack Jeffries, Katherine Morrison, Zvi Rosen, Anne Shiu, Nora Youngs
• Neural codes allow the brain to represent, process, and store information about the world. Combi- natorial codes, comprised of binary patterns of neural activity, encode information via the collective behavior of populations of neurons. A code is called convex if its codewords correspond to regions defined by an arrangement of convex open sets in Euclidean space. Convex codes have been observed experimentally in many brain areas, including sensory cortices and the hippocampus, where neurons exhibit convex receptive fields. What makes a neural code convex? That is, how can we tell from the in- trinsic structure of a code if there exists a corresponding arrangement of convex open sets? Using tools from combinatorics and commutative algebra, we uncover key signatures of convex and non-convex codes. In many cases, these signatures are sufficient to determine convexity, and reveal bounds on the minimal dimension of the underlying Euclidean space.

7. Pedagogical Practices for Fostering Mathematical Creativity and Proof-Based Courses: Three Case Studies
8. accepted, Research In Undergraduate Mathematics Education, 2016
w/ Gulden Karakok, Milos Savic, Gail Tang

• Research investigating the implementation of a mathematical creativity rubric on fostering mathematical creativity. Research findings based on three courses, one of which was the Math 106 I taught in Spring 2016.

9. Tame The GRE Math Subject Test
10. Math Horizons, Vol. 24, Issue 2, p.28-29, 2016.

• A guide to studying for the GRE Math Subject Test, based on content from my companion YouTube videos.

11. Low Degree Nullstellensatz Certificates for 3-Colorability
Electronic Journal of Combinatorics, 23(1), P1.6, 2016.
w/ Bo Li, Benjamin Lowenstein
• In a seminal paper, De Loera et. al introduce the algorithm NulLA (Nullstellensatz Linear Algebra) and use it to measure the difficulty of determining if a graph is not 3-colorable. The crux of this relies on a correspondence between 3-colorings of a graph and solutions to a certain system of polynomial equations over a field. In this article, we give a new direct combinatorial characterization of graphs that can be determined to be non-3-colorable in the first iteration of this algorithm when k=GF(2). This greatly simplifies the work of De Loera et. al, as we express the combinatorial characterization directly in terms of the graphs themselves without introducing superfluous directed graphs. Furthermore, for all graphs on at most 12 vertices, we determine at which iteration NulLA detects a graph is not 3-colorable when k=GF(2).

12. Chromatic Bounds on Orbital Chromatic Roots
Electronic Journal of Combinatorics, 21(4), P4.17, 2014.
w/ Dae Hyun Kim, Alexander H. Mun
• Given a group G of automorphisms of a graph Γ, the orbital chromatic polynomial OP_{Γ,G}(x) is the polynomial whose value at a positive integer k is the number of orbits of G on proper k-colorings of Γ. Cameron and Kayibi introduced this polynomial as a means of understanding roots of chromatic polynomials. In this light, they posed a problem asking whether the real roots of the orbital chromatic polynomial of any graph are bounded above by the largest real root of its chromatic polynomial. We resolve this problem in a resounding negative by not only constructing a counterexample, but by providing a process for generating families of counterexamples. We additionally begin the program of finding classes of graphs where the answer to this problem is true; in particular establishing its veracity for many outerplanar graphs.

13. Strong Nonnegatvity and Sums of Squares on Real Varieties
Journal of Pure and Applied Algebra 217 (5), pp. 843-850, 2013.
w/ Brian Osserman
• Motivated by scheme theory, we introduce strong nonnegativity on real varieties, which has the property that a sum of squares is strongly nonnegative. We show that this algebraic property is equivalent to nonnegativity for nonsingular real varieties. Moreover, for singular varieties, we reprove and generalize obstructions of Gouveia and Netzer to the convergence of the theta body hierarchy of convex bodies approximating the convex hull of a real variety.

14. On Volumes of Permutation Polytopes
Fields Institute Communications Vol. 69, Discrete Geometry and Optimization, pp. 55-77, 2013.
w/ Katherine Burggraf, Jesus De Loera
• This paper focuses on determining the volumes of permutation polytopes asso- ciated to cyclic groups, dihedral groups, groups of automorphisms of tree graphs, and Frobe- nius groups. We do this through the use of triangulations and the calculation of Ehrhart polynomials. We also present results on the theta body hierarchy of various permutation polytopes.

15. On The Hardness of Counting and Sampling Center Strings
IEEE/ACM Transactions on Computational Biology and Bioinformatics Vol. 9 Issue 6, pp. 1843-1846, 2012.
w/ Christina Boucher
• Given a set S of n strings, each of length l, and a non-negative value d, we define a center string as a string of length l that has Hamming distance at most d from each string in S. The #CLOSEST STRING problem aims to determine the number of unique center strings for a given set of strings S and input parameters n, l, and d. We show #CLOSEST STRING is impossible to solve exactly or even approximately in polynomial time, and that restricting #CLOSEST STRING so that any one of the parameters n, l, or d is fixed leads to an FPRAS. We show equivalent results for the problem of efficiently sampling center strings uniformly at random.

16. Applications of Convex and Algebraic Geometry to Graphs and Polytopes
Ph.D. Thesis, Advisor: Jesus De Loera. UC Davis, 2011.
17. Recognizing Graph Theoretic Properties with Polynomial Ideals
Electronic Journal of Combinatorics, 17(1), R114, 2010.
w/ Jesus De Loera, Peter N. Malkin
• Many hard combinatorial problems can be modeled by a system of polynomial equations. Noga Alon coined the term polynomial method to describe the use of nonlinear polynomials when solving combinatorial problems. We continue the exploration of the polynomial method and show how the algorithmic theory of polynomial ideals can be used to detect k-colorability, unique Hamiltonicity, and automorphism rigidity of graphs. Our techniques are diverse and involve Nullstellensatz certificates, linear algebra over finite fields, Gr ̈obner bases, toric algebra, convex programming, and real algebraic geometry.

18. On The Hardness of Counting and Sampling Center Strings
Proceedings of the 17th Annual Symposium on String Processing and Information Retrieval, pages 128-135, 2010.
w/ Christina Boucher
19. This is the conference version of the journal paper listed above.

20. Distribution of the Number of Encryptions in Revocation Schemes for Stateless Receivers
Discrete Mathematics and Theoretical Computer Science, Fifth Colloquium on Math and Computer Science, pp. 195-206, 2008.
w/ Christopher Eagle, Zhicheng Gao, Daniel Panario, Bruce Richmond
• We study the number of encryptions necessary to revoke a set of users in the complete subtree scheme (CST) and the subset-difference scheme (SD). These are well-known tree based broadcast encryption schemes. Park and Blake in: Journal of Discrete Algorithms, vol. 4, 2006, pp. 215–238, give the mean number of encryptions for these schemes. We continue their analysis and show that the limiting distribution of the number of encryptions for these schemes is normal. This implies that the mean numbers of Park and Blake are good estimates for the number of necessary encryptions used by these schemes.

21. Combinatorial Approaches to the Jacobian Conjecture
Master's Thesis. Advisor: Ian P. Goulden. University of Waterloo, 2007.
22. Asymptotics of Largest Components in Combinatorial Structures
Algorithmica 46 (3-4), pp. 493-503, 2006.
w/ Daniel Panario, Bruce Richmond, Jacki Whitely
• Given integers m and n, we study the probability that structures of size n have all components of size at most m. The results are given in term of a generalized Dickman function of n/m.