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.
 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.
 A Proof of the Peak Polynomial Positivity Conjecture
submitted, 7 pp
w/ Alex DiazLopez, 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.
 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 intersectioncompleteness characterizes realizable 2sparse codes, and show that any realizable 2sparse code has embedding dimension at most 3. Furthermore, we prove that in R^2 and R^3, realizations of 2sparse codes using closed sets are equivalent to those with open sets, and this allows us to provide some preliminary results on distinguishing which 2sparse codes have embedding dimension at most 2.
 The qanalog 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 qanalog 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 qanalog 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.
 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 nonconvex codes. In many cases, these signatures are sufficient to determine convexity, and reveal bounds on the minimal dimension of the underlying Euclidean space.
 Low Degree Nullstellensatz Certificates for 3Colorability
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 3colorable. The crux of this relies on a correspondence between 3colorings 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 non3colorable 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 3colorable when k=GF(2).
 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 kcolorings 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.
 Strong Nonnegatvity and Sums of Squares on Real Varieties
Journal of Pure and Applied Algebra 217 (5), pp. 843850, 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.
 On Volumes of Permutation Polytopes
Fields Institute Communications Vol. 69, Discrete Geometry and Optimization, pp. 5577, 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.
 On The Hardness of Counting and Sampling Center Strings
IEEE/ACM Transactions on Computational Biology and Bioinformatics Vol. 9 Issue 6, pp. 18431846, 2012.
w/ Christina Boucher
 Given a set S of n strings, each of length l, and a nonnegative 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.

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 kcolorability, 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.
 On The Hardness of Counting and Sampling Center Strings
Proceedings of the 17th Annual Symposium on String Processing and Information Retrieval, pages 128135, 2010.
w/ Christina Boucher
This is the conference version of the journal paper listed above.
 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. 195206, 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 subsetdifference scheme (SD). These are wellknown 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.
 Asymptotics of Largest Components in Combinatorial Structures
Algorithmica 46 (34), pp. 493503, 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.