More Like this

1. Short Proof of the Asymptotic Confirmation of the Faudree-Lehel Conjecture

   https://doi.org/10.37236/11413  

   Przybyło, Jakub; Wei, Fan (October 2023, The Electronic Journal of Combinatorics)

   Given a simple graph $$G$$, the irregularity strength of $$G$$, denoted $s(G)$, is the least positive integer $$k$$ such that there is a weight assignment on edges $$f: E(G) \to \{1,2,\dots, k\}$$ for which each vertex weight $$f^V(v):= \sum_{u: \{u,v\}\in E(G)} f(\{u,v\})$$ is unique amongst all $$v\in V(G)$$. In 1987, Faudree and Lehel conjectured that there is a constant $$c$$ such that $$s(G) \leq n/d + c$$ for all $$d$$-regular graphs $$G$$ on $$n$$ vertices with $d>1$, whereas it is trivial that $$s(G) \geq n/d$$. In this short note we prove that the Faudree-Lehel Conjecture holds when $$d \geq n^{0.8+\epsilon}$$ for any fixed $$\epsilon >0$$, with a small additive constant $c=28$ for $$n$$ large enough. Furthermore, we confirm the conjecture asymptotically by proving that for any fixed $$\beta\in(0,1/4)$$ there is a constant $$C$$ such that for all $$d$$-regular graphs $$G$$, $$s(G) \leq \frac{n}{d}(1+\frac{C}{d^{\beta}})+28$$, extending and improving a recent result of Przybyło that $$s(G) \leq \frac{n}{d}(1+ \frac{1}{\ln^{\epsilon/19}n})$$ whenever $$d\in [\ln^{1+\epsilon} n, n/\ln^{\epsilon}n]$$ and $$n$$ is large enough. 

   more » « less
2. Generalized Splines on Graphs with Two Labels and Polynomial Splines on Cycles

   https://doi.org/10.37236/11155  

   Anderson, Portia; Matherne, Jacob P; Tymoczko, Julianna (January 2024, The Electronic Journal of Combinatorics)

   Generalized splines are an algebraic combinatorial framework that generalizes and unifies various established concepts across different fields, most notably the classical notion of splines and the topological notion of GKM theory. The former consists of piecewise polynomials on a combinatorial geometric object like a polytope, whose polynomial pieces agree to a specified degree of differentiability. The latter is a graph-theoretic construction of torus-equivariant cohomology that Shareshian and Wachs used to reformulate the well-known Stanley-Stembridge conjecture, a reformulation that was recently proven to hold by Brosnan and Chow and independently Guay-Paquet. This paper focuses on the theory of generalized splines. A generalized spline on a graph $$G$$ with each edge labeled by an ideal in a ring $$R$$ consists of a vertex-labeling by elements of $$R$$ so that the labels on adjacent vertices $u, v$ differ by an element of the ideal associated to the edge $uv$. We study the $$R$$-module of generalized splines and produce minimum generating sets for several families of graphs and edge-labelings: $1)$ for all graphs when the set of possible edge-labelings consists of at most two finitely-generated ideals, and $2)$ for cycles when the set of possible edge-labelings consists of principal ideals generated by elements of the form $(ax+by)^2$ in the polynomial ring $$\mathbb{C}[x,y]$$. We obtain the generators using a constructive algorithm that is suitable for computer implementation and give several applications, including contextualizing several results in the theory of classical (analytic) splines. 

   more » « less
3. Many Cliques with Few Edges

   https://doi.org/10.37236/9550  

   Kirsch, Rachel; Radcliffe, A. J. (January 2021, The Electronic Journal of Combinatorics)

   null (Ed.)

   Recently Cutler and Radcliffe proved that the graph on $$n$$ vertices with maximum degree at most $$r$$ having the most cliques is a disjoint union of $$\lfloor n/(r+1)\rfloor$$ cliques of size $r+1$ together with a clique on the remainder of the vertices. It is very natural also to consider this question when the limiting resource is edges rather than vertices. In this paper we prove that among graphs with $$m$$ edges and maximum degree at most $$r$$, the graph that has the most cliques of size at least two is the disjoint union of $$\bigl\lfloor m \bigm/\binom{r+1}{2} \bigr\rfloor$$ cliques of size $r+1$ together with the colex graph using the remainder of the edges. 

   more » « less
4. Multitrees in random graphs

   https://doi.org/10.37236/10804  

   Frieze, A.; Pegden, W. (January 2023, The Electronic journal of combinatorics)

   Let $$N=\binom{n}{2}$$ and $$s\geq 2$$. Let $$e_{i,j},\,i=1,2,\ldots,N,\,j=1,2,\ldots,s$$ be $$s$$ independent permutations of the edges $$E(K_n)$$ of the complete graph $$K_n$$. A {\em MultiTree} is a set $$I\subseteq [N]$$ such that the edge sets $$E_{I,j}$$ induce spanning trees for $$j=1,2,\ldots,s$$. In this paper we study the following question: what is the smallest $m=m(n)$ such that w.h.p. $[m]$ contains a MultiTree. We prove a hitting time result for $s=2$ and an $$O(n\log n)$$ bound for $$s\geq 3$$. 

   more » « less
5. Multitrees in Random Graphs

   https://doi.org/10.37236/10804  

   Frieze, Alan; Pegden, Wesley (January 2023, The Electronic Journal of Combinatorics)

   Let $$N=\binom{n}{2}$$ and $$s\geq 2$$. Let $$e_{i,j},\,i=1,2,\ldots,N,\,j=1,2,\ldots,s$$ be $$s$$ independent permutations of the edges $$E(K_n)$$ of the complete graph $$K_n$$. A MultiTree is a set $$I\subseteq [N]$$ such that the edge sets $$E_{I,j}$$ induce spanning trees for $$j=1,2,\ldots,s$$. In this paper we study the following question: what is the smallest $m=m(n)$ such that w.h.p. $[m]$ contains a MultiTree. We prove a hitting time result for $s=2$ and an $$O(n\log n)$$ bound for $$s\geq 3$$. 

   more » « less