Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn trees with the same restricted U-polynomial and the Prouhet-Tarry-Escott problem
87
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
This paper focuses on the well-known problem due to Stanley of whether two non-isomorphic trees can have the same $U$-polynomial (or, equivalently, the same chromatic symmetric function). We consider the $U_k$-polynomial, which is a restricted version of $U$-polynomial, and construct with the help of solutions of the Prouhet-Tarry-Escott problem, non-isomorphic trees with the same $U_k$-polynomial for any given $k$. By doing so, we also find a new class of trees that are distinguished by the $U$-polynomial up to isomorphism.
rate research
Read More
In this article, we construct explicit examples of pairs of non-isomorphic trees with the same restricted $U$-polynomial for every $k$; by this we mean that the polynomials agree on terms with degree at most $k+1$. The main tool for this construction is a generalization of the $U$-polynomial to rooted graphs, which we introduce and study in this article. Most notably we show that rooted trees can be reconstructed from its rooted $U$-polynomial.
Consider a two-player game between players Builder and Painter. Painter begins the game by picking a coloring of the edges of $K_n$, which is hidden from Builder. In each round, Builder points to an edge and Painter reveals its color. Builders goal is to locate a particular monochromatic structure in Painters coloring by revealing the color of as few edges as possible. The fewest number of turns required for Builder to win this game is known as the restricted online Ramsey number. In this paper, we consider the situation where this particular monochromatic structure is a large matching or a large tree. We show that in any $t$-coloring of $E(K_n)$, Builder can locate a monochromatic matching on at least ${n-t+1over t+1}$ edges by revealing at most $O(nlog t)$ edges. We show also that in any $3$-coloring of $E(K_n)$, Builder can locate a monochromatic tree on at least $n/2$ vertices by revealing at most $5n$ edges.
We show that, with the exception of the words $a^2ba^2$ and $b^2ab^2$, all (finite or infinite) binary patterns in the Prouhet-Thue-Morse sequence can actually be found in that sequence as segments (up to exchange of letters in the infinite case). This result was previously attributed to unpublished work by D. Guaiana and may also be derived from publications of A. Shur only available in Russian. We also identify the (finitely many) finite binary patterns that appear non trivially, in the sense that they are obtained by applying an endomorphism that does not map the set of all segments of the sequence into itself.
A spanning tree of an edge-colored graph is rainbow provided that each of its edges receives a distinct color. In this paper we consider the natural extremal problem of maximizing and minimizing the number of rainbow spanning trees in a graph $G$. Such a question clearly needs restrictions on the colorings to be meaningful. For edge-colorings using $n-1$ colors and without rainbow cycles, known in the literature as JL-colorings, there turns out to be a particularly nice way of counting the rainbow spanning trees and we solve this problem completely for JL-colored complete graphs $K_n$ and complete bipartite graphs $K_{n,m}$. In both cases, we find tight upper and lower bounds; the lower bound for $K_n$, in particular, proves to have an unexpectedly chaotic and interesting behavior. We further investigate this question for JL-colorings of general graphs and prove several results including characterizing graphs which have JL-colorings achieving the lowest possible number of rainbow spanning trees. We establish other results for general $n-1$ colorings, including providing an analogue of Kirchoffs matrix tree theorem which yields a way of counting rainbow spanning trees in a general graph $G$.
Partitioning a set into similar, if not, identical, parts is a fundamental research topic in combinatorics. The question of partitioning the integers in various ways has been considered throughout history. Given a set ${x_1, ldots, x_n}$ of integers where $x_1<cdots<x_n$, let the {it gap sequence} of this set be the nondecreasing sequence $d_1, ldots, d_{n-1}$ where ${d_1, ldots, d_{n-1}}$ equals ${x_{i+1}-x_i:iin{1,ldots, n-1}}$ as a multiset. This paper addresses the following question, which was explicitly asked by Nakamigawa: can the set of integers be partitioned into sets with the same gap sequence? The question is known to be true for any set where the gap sequence has length at most two. This paper provides evidence that the question is true when the gap sequence has length three. Namely, we prove that given positive integers $p$ and $q$, there is a positive integer $r_0$ such that for all $rgeq r_0$, the set of integers can be partitioned into $4$-sets with gap sequence $p, q$, $r$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
