More Like this

1. Realizing trees of configurations in thin sets

   https://doi.org/10.2140/pjm.2025.335.355  

   Greenleaf, Allan; Iosevich, Alex; Taylor, Krystal (January 2025, Pacific Journal of Mathematics)

   Let $$\phi(x,y)$$ be a continuous function, smooth away from the diagonal, such that, for some $$\alpha>0$$, the associated generalized Radon transforms \begin{equation} \label{Radon} R_t^{\phi}f(x)=\int_{\phi(x,y)=t} f(y) \psi(y) d\sigma_{x,t}(y) \end{equation} map $$L^2({\mathbb R}^d) \to H^{\alpha}({\mathbb R}^d)$$ for all $t>0$. Let $$E$$ be a compact subset of $${\mathbb R}^d$$ for some $$d \ge 2$$, and suppose that the Hausdorff dimension of $$E$$ is $$>d-\alpha$$. We show that any tree graph $$T$$ on $k+1$ ($$k \ge 1$$) vertices is realizable in $$E$$, in the sense that there exist distinct $$x^1, x^2, \dots, x^{k+1} \in E$$ and $t>0$ such that the $$\phi$$-distance $$\phi(x^i, x^j)$$ is equal to $$t$$ for all pairs $(i,j)$ corresponding to the edges of the graph $$T$$. 

   more » « less
2. Triforce and corners

   https://doi.org/10.1017/s0305004119000173  

   FOX, JACOB; SAH, ASHWIN; SAWHNEY, MEHTAAB; STONER, DAVID; ZHAO, YUFEI (July 2020, Mathematical Proceedings of the Cambridge Philosophical Society)

   Abstract May the triforce be the 3-uniform hypergraph on six vertices with edges {123′, 12′3, 1′23}. We show that the minimum triforce density in a 3-uniform hypergraph of edge density δ is δ 4– o (1) but not O ( δ 4 ). Let M ( δ ) be the maximum number such that the following holds: for every ∊ > 0 and $$G = {\mathbb{F}}_2^n$$ with n sufficiently large, if A ⊆ G × G with A ≥ δ | G | 2 , then there exists a nonzero “popular difference” d ∈ G such that the number of “corners” ( x , y ), ( x + d , y ), ( x , y + d ) ∈ A is at least ( M ( δ )–∊)| G | 2 . As a corollary via a recent result of Mandache, we conclude that M ( δ ) = δ 4– o (1) and M ( δ ) = ω ( δ 4 ). On the other hand, for 0 < δ < 1/2 and sufficiently large N , there exists A ⊆ [ N ] 3 with | A | ≥ δN 3 such that for every d ≠ 0, the number of corners ( x , y , z ), ( x + d , y , z ), ( x , y + d , z ), ( x , y , z + d ) ∈ A is at most δ c log(1/ δ ) N 3 . A similar bound holds in higher dimensions, or for any configuration with at least 5 points or affine dimension at least 3. 

   more » « less
3. Subdivided Claws and the Clique-Stable Set Separation Property

   https://doi.org/10.1007/978-3-030-62497-2  

   Chudnovsky, Maria and (February 2021, MATRIX book series)

   null (Ed.)

   Let C be a class of graphs closed under taking induced subgraphs. We say that C has the clique-stable set separation property if there exists c ∈ N such that for every graph G ∈ C there is a collection P of partitions (X, Y ) of the vertex set of G with |P| ≤ |V (G)| c and with the following property: if K is a clique of G, and S is a stable set of G, and K ∩ S = ∅, then there is (X, Y ) ∈ P with K ⊆ X and S ⊆ Y . In 1991 M. Yannakakis conjectured that the class of all graphs has the clique-stable set separation property, but this conjecture was disproved by M. G¨o¨os in 2014. Therefore it is now of interest to understand for which classes of graphs such a constant c exists. In this paper we define two infinite families S, K of graphs and show that for every S ∈ S and K ∈ K, the class of graphs with no induced subgraph isomorphic to S or K has the clique-stable set separation property. 

   more » « less
4. Subdivided Claws and the Clique-Stable Set Separation Property

   https://doi.org/10.1007/978-3-030-62497-2_29  

   Chudnovsky, Maria and (February 2021, MATRIX book series)

   Let C be a class of graphs closed under taking induced subgraphs. We say that C has the clique-stable set separation property if there exists c∈N such that for every graph G∈C there is a collection P of partitions (X,Y) of the vertex set of G with |P|≤|V(G)|c and with the following property: if K is a clique of G, and S is a stable set of G, and K∩S=∅, then there is (X,Y)∈P with K⊆X and S⊆Y. In 1991 M. Yannakakis conjectured that the class of all graphs has the clique-stable set separation property, but this conjecture was disproved by Göös in 2014. Therefore it is now of interest to understand for which classes of graphs such a constant c exists. In this paper we define two infinite families S,K of graphs and show that for every S∈S and K∈K, the class of graphs with no induced subgraph isomorphic to S or K has the clique-stable set separation property. 

   more » « less
5. Hyperbolic families and coloring graphs on surfaces

   https://doi.org/https://doi.org/10.1090/btran/26  

   Postle, Luke; Thomas, Robin (December 2018, Transactions of the American Mathematical Society. Series B)

   We develop a theory of linear isoperimetric inequalities for graphs on surfaces and apply it to coloring problems, as follows. Let $ G$ be a graph embedded in a fixed surface $$ \Sigma $$ of genus $ g$ and let $$ L=(L(v):v\in V(G))$$ be a collection of lists such that either each list has size at least five, or each list has size at least four and $ G$ is triangle-free, or each list has size at least three and $ G$ has no cycle of length four or less. An $ L$-coloring of $ G$ is a mapping $$ \phi $$ with domain $ V(G)$ such that $$ \phi (v)\in L(v)$$ for every $$ v\in V(G)$$ and $$ \phi (v)\ne \phi (u)$$ for every pair of adjacent vertices $$ u,v\in V(G)$$. We prove if every non-null-homotopic cycle in $ G$ has length $$ \Omega (\log g)$$, then $ G$ has an $ L$-coloring, if $ G$ does not have an $ L$-coloring, but every proper subgraph does (``$ L$-critical graph''), then $$ \vert V(G)\vert=O(g)$$, if every non-null-homotopic cycle in $ G$ has length $$ \Omega (g)$$, and a set $$ X\subseteq V(G)$$ of vertices that are pairwise at distance $$ \Omega (1)$$ is precolored from the corresponding lists, then the precoloring extends to an $ L$-coloring of $ G$, if every non-null-homotopic cycle in $ G$ has length $$ \Omega (g)$$, and the graph $ G$ is allowed to have crossings, but every two crossings are at distance $$ \Omega (1)$$, then $ G$ has an $ L$-coloring, if $ G$ has at least one $ L$-coloring, then it has at least $$ 2^{\Omega (\vert V(G)\vert)}$$ distinct $ L$-colorings. We show that the above assertions are consequences of certain isoperimetric inequalities satisfied by $ L$-critical graphs, and we study the structure of families of embedded graphs that satisfy those inequalities. It follows that the above assertions hold for other coloring problems, as long as the corresponding critical graphs satisfy the same inequalities. 

   more » « less