2 citations · 2 across the 13 of their papers we have counts for
18 papers
On Domination Exponents for Pairs of Graphs
Grigoriy Blekherman, Annie Raymond, Alexander Razborov +1
Understanding graph density profiles is notoriously challenging. Even for pairs of graphs, complete characterizations are known only in very limited cases, such as edges versus cli…
Ubiquity of power sums in graph profiles
Grigoriy Blekherman, Annie Raymond
Graph density profiles are fundamental objects in extremal combinatorics. Very few profiles are fully known, and all are two-dimensional. We show that even in high dimensions ratio…
Tropicalizing the Graph Profile of Some Almost-Stars
Maria Dascălu, Annie Raymond
Many important problems in extremal combinatorics can be stated as certifying polynomial inequalities in graph homomorphism numbers, and in particular, many ask to certify pure bin…
Generalized Pitman-Stanley polytope: vertices and faces
William T. Dugan, Maura Hegarty, Alejandro H. Morales +1
In 1999, Pitman and Stanley introduced the polytope bearing their name along with a study of its faces, lattice points, and volume. The Pitman-Stanley polytope is well-studied due…
Undecidability of polynomial inequalities in weighted graph homomorphism densities
Grigoriy Blekherman, Annie Raymond, Fan Wei
Many problems and conjectures in extremal combinatorics concern polynomial inequalities between homomorphism densities of graphs where we allow edges to have real weights. Using th…
Non-trivial squares and Sidorenko's conjecture
Pranav Garg, Annie Raymond, Amanda Redlich
Let be the homomorphism density of a graph into a graph . Sidorenko's conjecture states that for any bipartite graph , for all gra…
A Path Forward: Tropicalization in Extremal Combinatorics
Grigoriy Blekherman, Annie Raymond
Many important problems in extremal combinatorics can be be stated as proving a pure binomial inequality in graph homomorphism numbers, i.e., proving that homh…
Proof of the Erdős-Simonovits conjecture on walks
Grigoriy Blekherman, Annie Raymond
Let be a graph on vertices and let denote the number of walks of length in divided by . Erdős and Simonovits conjectured that $w_k(G^n)^t \geq w_t…
The Linear Relaxation of an Integer Program for the Union-Closed Conjecture
Brianna Amaral, Lucien Dalton, Drew Polakowski +2
The Frankl conjecture, also known as the union-closed sets conjecture, states that in any finite non-empty union-closed family, there exists an element in at least half of the sets…
Tropicalization of Graph Profiles
Grigoriy Blekherman, Annie Raymond, Mohit Singh +1
A graph profile records all possible densities of a fixed finite set of graphs. Profiles can be extremely complicated; for instance the full profile of any triple of connected grap…
Simple Graph Density Inequalities with no Sum of Squares Proofs
Grigoriy Blekherman, Annie Raymond, Mohit Singh +1
Establishing inequalities among graph densities is a central pursuit in extremal combinatorics. A standard tool to certify the nonnegativity of a graph density expression is to wri…
The Turán Polytope
Annie Raymond
The Turán hypergraph problem asks to find the maximum number of -edges in a -uniform hypergraph on vertices that does not contain a clique of size . When , i.e.,…
The bullet problem with discrete speeds
Brittany Dygert, Christoph Kinzel, Jennifer Zhu +3
Bullets are fired, one per second, with independent speeds sampled uniformly from a discrete set. Collisions result in mutual annihilation. We show that the second fastest bullet s…
Symmetric Sums of Squares over -Subset Hypercubes
Annie Raymond, James Saunderson, Mohit Singh +1
We consider the problem of finding sum of squares (sos) expressions to establish the non-negativity of a symmetric polynomial over a discrete hypercube whose coordinates are indexe…
New Conjectures for Union-Closed Families
Jonad Pulaj, Annie Raymond, Dirk Theis
The Frankl conjecture, also known as the union-closed sets conjecture, states that in any finite non-empty union-closed family, there exists an element in at least half of the sets…
Symmetry in Turán Sums of Squares Polynomials from Flag Algebras
Annie Raymond, Mohit Singh, Rekha R. Thomas
Turán problems in extremal combinatorics ask to find asymptotic bounds on the edge densities of graphs and hypergraphs that avoid specified subgraphs. The theory of flag algebras p…
The centers of gravity of the associahedron and of the permutahedron are the same
Christophe Hohlweg, Jonathan Lortie, Annie Raymond
In this article, we show that Loday's realization of the associahedron has the the same center of gravity than the permutahedron. This proves an observation made by F. Chapoton. We…
Small Chvatal rank
Tristram Bogart, Annie Raymond, Rekha R. Thomas
We propose a variant of the Chvatal-Gomory procedure that will produce a sufficient set of facet normals for the integer hulls of all polyhedra {xx : Ax <= b} as b varies. The numb…