More Like this

1. A completion of the proof of the Edge-statistics Conjecture

   https://doi.org/10.19086/aic.12047  

   Fox, Jacob; Sauermann, Lisa (February 2020, Advances in Combinatorics)

   Extremal combinatorics often deals with problems of maximizing a specific quantity related to substructures in large discrete structures. The first question of this kind that comes to one's mind is perhaps determining the maximum possible number of induced subgraphs isomorphic to a fixed graph $$H$$ in an $$n$$-vertex graph. The asymptotic behavior of this number is captured by the limit of the ratio of the maximum number of induced subgraphs isomorphic to $$H$$ and the number of all subgraphs with the same number vertices as $$H$$; this quantity is known as the _inducibility_ of $$H$$. More generally, one can define the inducibility of a family of graphs in the analogous way.Among all graphs with $$k$$ vertices, the only two graphs with inducibility equal to one are the empty graph and the complete graph. However, how large can the inducibility of other graphs with $$k$$ vertices be? Fix $$k$$, consider a graph with $$n$$ vertices join each pair of vertices independently by an edge with probability $$\binom{k}{2}^{-1}$$. The expected number of $$k$$-vertex induced subgraphs with exactly one edge is $$e^{-1}+o(1)$$. So, the inducibility of large graphs with a single edge is at least $$e^{-1}+o(1)$$. This article establishes that this bound is the best possible in the following stronger form, which proves a conjecture of Alon, Hefetz, Krivelevich and Tyomkyn: the inducibility of the family of $$k$$-vertex graphs with exactly $$l$$ edges where $$0<\binom{k}{2}$$ is at most $$e^{-1}+o(1)$$. The example above shows that this is tight for $l=1$ and it can be also shown to be tight for $l=k-1$. The conjecture was known to be true in the regime where $$l$$ is superlinearly bounded away from $$0$$ and $$\binom{k}{2}$$, for which the sum of the inducibilities goes to zero, and also in the regime where $$l$$ is bounded away from $$0$$ and $$\binom{k}{2}$$ by a sufficiently large linear function. The article resolves the hardest cases where $$l$$ is linearly close to $$0$$ or close to $$\binom{k}{2}$$, and provides generalizations to hypergraphs. 

   more » « less
2. On the three ball theorem for solutions of the Helmholtz equation

   https://doi.org/10.1007/s40627-021-00070-3  

   Berge, Stine Marie; Malinnikova, Eugenia (June 2021, Complex Analysis and its Synergies)

   null (Ed.)

   Abstract Let $$u_{k}$$ u k be a solution of the Helmholtz equation with the wave number k , $$\varDelta u_{k}+k^{2} u_{k}=0$$ Δ u k + k 2 u k = 0 , on (a small ball in) either $${\mathbb {R}}^{n}$$ R n , $${\mathbb {S}}^{n}$$ S n , or $${\mathbb {H}}^{n}$$ H n . For a fixed point p , we define $$M_{u_{k}}(r)=\max _{d(x,p)\le r}|u_{k}(x)|.$$ M u k ( r ) = max d ( x , p ) ≤ r | u k ( x ) | . The following three ball inequality $$M_{u_{k}}(2r)\le C(k,r,\alpha )M_{u_{k}}(r)^{\alpha }M_{u_{k}}(4r)^{1-\alpha }$$ M u k ( 2 r ) ≤ C ( k , r , α ) M u k ( r ) α M u k ( 4 r ) 1 - α is well known, it holds for some $$\alpha \in (0,1)$$ α ∈ ( 0 , 1 ) and $$C(k,r,\alpha )>0$$ C ( k , r , α ) > 0 independent of $$u_{k}$$ u k . We show that the constant $$C(k,r,\alpha )$$ C ( k , r , α ) grows exponentially in k (when r is fixed and small). We also compare our result with the increased stability for solutions of the Cauchy problem for the Helmholtz equation on Riemannian manifolds. 

   more » « less
3. Making K _r+1 -free graphs r -partite

   https://doi.org/10.1017/S0963548320000590  

   Balogh, József; Clemen, Felix Christian; Lavrov, Mikhail; Lidický, Bernard; Pfender, Florian (July 2021, Combinatorics, Probability and Computing)

   null (Ed.)

   Abstract The Erdős–Simonovits stability theorem states that for all ε > 0 there exists α > 0 such that if G is a K r+ 1 -free graph on n vertices with e ( G ) > ex( n , K r +1 )– α n 2 , then one can remove εn 2 edges from G to obtain an r -partite graph. Füredi gave a short proof that one can choose α = ε . We give a bound for the relationship of α and ε which is asymptotically sharp as ε → 0. 

   more » « less
4. Characterization of All Graphs with a Failed Skew Zero Forcing Number of 1

   https://doi.org/10.3390/math10234463  

   Johnson, Aidan; Vick, Andrew E.; Narayan, Darren A. (December 2022, Mathematics)

   Given a graph G, the zero forcing number of G, Z(G), is the minimum cardinality of any set S of vertices of which repeated applications of the forcing rule results in all vertices being in S. The forcing rule is: if a vertex v is in S, and exactly one neighbor u of v is not in S, then u is added to S in the next iteration. Hence the failed zero forcing number of a graph was defined to be the cardinality of the largest set of vertices which fails to force all vertices in the graph. A similar property called skew zero forcing was defined so that if there is exactly one neighbor u of v is not in S, then u is added to S in the next iteration. The difference is that vertices that are not in S can force other vertices. This leads to the failed skew zero forcing number of a graph, which is denoted by F−(G). In this paper, we provide a complete characterization of all graphs with F−(G)=1. Fetcie, Jacob, and Saavedra showed that the only graphs with a failed zero forcing number of 1 are either: the union of two isolated vertices; P3; K3; or K4. In this paper, we provide a surprising result: changing the forcing rule to a skew-forcing rule results in an infinite number of graphs with F−(G)=1. 

   more » « less
5. Improved Bounds on a Generalization of Tuza's Conjecture

   https://doi.org/10.37236/10829  

   Basit, Abdul; McGinnis, Daniel; Simmons, Henry; Sinnwell, Matt; Zerbib, Shira (October 2022, The Electronic Journal of Combinatorics)

   For an $$r$$-uniform hypergraph $$H$$, let $$\nu^{(m)}(H)$$ denote the maximum size of a set $$M$$ of edges in $$H$$ such that every two edges in $$M$$ intersect in less than $$m$$ vertices, and let $$\tau^{(m)}(H)$$ denote the minimum size of a collection $$C$$ of $$m$$-sets of vertices such that every edge in $$H$$ contains an element of $$C$$. The fractional analogues of these parameters are denoted by $$\nu^{*(m)}(H)$$ and $$\tau^{*(m)}(H)$$, respectively. Generalizing a famous conjecture of Tuza on covering triangles in a graph, Aharoni and Zerbib conjectured that for every $$r$$-uniform hypergraph $$H$$, $$\tau^{(r-1)}(H)/\nu^{(r-1)}(H) \leq \lceil{\frac{r+1}{2}}\rceil$$. In this paper we prove bounds on the ratio between the parameters $$\tau^{(m)}$$ and $$\nu^{(m)}$$, and their fractional analogues. Our main result is that, for every $$r$$-uniform hypergraph~$$H$$,\[ \tau^{*(r-1)}(H)/\nu^{(r-1)}(H) \le \begin{cases} \frac{3}{4}r - \frac{r}{4(r+1)} &\text{for }r\text{ even,}\\\frac{3}{4}r - \frac{r}{4(r+2)} &\text{for }r\text{ odd.} \\\end{cases} \]This improves the known bound of $$r-1$.We also prove that, for every $$r$$-uniform hypergraph $$H$$, $$\tau^{(m)}(H)/\nu^{*(m)}(H) \le \operatorname{ex}_m(r, m+1)$$, where the Turán number $$\operatorname{ex}_r(n, k)$$ is the maximum number of edges in an $$r$$-uniform hypergraph on $$n$$ vertices that does not contain a copy of the complete $$r$$-uniform hypergraph on $$k$$ vertices. Finally, we prove further bounds in the special cases $(r,m)=(4,2)$ and $(r,m)=(4,3)$. 

   more » « less