Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe flipping puzzle on a graph
195
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $S$ be a connected graph which contains an induced path of $n-1$ vertices, where $n$ is the order of $S.$ We consider a puzzle on $S$. A configuration of the puzzle is simply an $n$-dimensional column vector over ${0, 1}$ with coordinates of the vector indexed by the vertex set $S$. For each configuration $u$ with a coordinate $u_s=1$, there exists a move that sends $u$ to the new configuration which flips the entries of the coordinates adjacent to $s$ in $u.$ We completely determine if one configuration can move to another in a sequence of finite steps.
rate research
Read More
Let $X=(V,E)$ be a finite simple connected graph with $n$ vertices and $m$ edges. A configuration is an assignment of one of two colors, black or white, to each edge of $X.$ A move applied to a configuration is to select a black edge $epsilonin E$ and change the colors of all adjacent edges of $epsilon.$ Given an initial configuration and a final configuration, try to find a sequence of moves that transforms the initial configuration into the final configuration. This is the edge-flipping puzzle on $X,$ and it corresponds to a group action. This group is called the edge-flipping group $mathbf{W}_E(X)$ of $X.$ This paper shows that if $X$ has at least three vertices, $mathbf{W}_E(X)$ is isomorphic to a semidirect product of $(mathbb{Z}/2mathbb{Z})^k$ and the symmetric group $S_n$ of degree $n,$ where $k=(n-1)(m-n+1)$ if $n$ is odd, $k=(n-2)(m-n+1)$ if $n$ is even, and $mathbb{Z}$ is the additive group of integers.
In the picture-hanging puzzle we are to hang a picture so that the string loops around $n$ nails and the removal of any nail results in a fall of the picture. We show that the length of a sequence representing an element in the free group with $n$ generators that corresponds to a solution of the picture-hanging puzzle must be at least $n2^{sqrt{log_2 n}}$. In other words, this is a lower bound on the length of a sequence representing a non-trivial element in the free group with $n$ generators such that if we replace any of the generators by the identity the sequence becomes trivial.
For a graph whose vertex set is a finite set of points in $mathbb R^d$, consider the closed (open) balls with diameters induced by its edges. The graph is called a (an open) Tverberg graph if these closed (open) balls intersect. Using the idea of halving lines, we show that (i) for any finite set of points in the plane, there exists a Hamiltonian cycle that is a Tverberg graph; (ii) for any $n$ red and $n$ blue points in the plane, there exists a perfect red-blue matching that is a Tverberg graph. Using the idea of infinite descent, we prove that (iii) for any even set of points in $mathbb R^d$, there exists a perfect matching that is an open Tverberg graph; (iv) for any $n$ red and $n$ blue points in $ mathbb R^d $, there exists a perfect red-blue matching that is a Tverberg graph.
The principal ratio of a connected graph $G$, $gamma(G)$, is the ratio between the largest and smallest coordinates of the principal eigenvector of the adjacency matrix of $G$. Over all connected graphs on $n$ vertices, $gamma(G)$ ranges from $1$ to $n^{cn}$. Moreover, $gamma(G)=1$ if and only if $G$ is regular. This indicates that $gamma(G)$ can be viewed as an irregularity measure of $G$, as first suggested by Tait and Tobin (El. J. Lin. Alg. 2018). We are interested in how stable this measure is. In particular, we ask how $gamma$ changes when there is a small modification to a regular graph $G$. We show that this ratio is polynomially bounded if we remove an edge belonging to a cycle of bounded length in $G$, while the ratio can jump from $1$ to exponential if we join a pair of vertices at distance $2$. We study the connection between the spectral gap of a regular graph and the stability of its principal ratio. A naive bound shows that given a constant multiplicative spectral gap and bounded degree, the ratio remains polynomially bounded if we add or delete an edge. Using results from matrix perturbation theory, we show that given an additive spectral gap greater than $(2+epsilon)sqrt{n}$, the ratio stays bounded after adding or deleting an edge.
We study the $F$-decomposition threshold $delta_F$ for a given graph $F$. Here an $F$-decomposition of a graph $G$ is a collection of edge-disjoint copies of $F$ in $G$ which together cover every edge of $G$. (Such an $F$-decomposition can only exist if $G$ is $F$-divisible, i.e. if $e(F)mid e(G)$ and each vertex degree of $G$ can be expressed as a linear combination of the vertex degrees of $F$.) The $F$-decomposition threshold $delta_F$ is the smallest value ensuring that an $F$-divisible graph $G$ on $n$ vertices with $delta(G)ge(delta_F+o(1))n$ has an $F$-decomposition. Our main results imply the following for a given graph $F$, where $delta_F^ast$ is the fractional version of $delta_F$ and $chi:=chi(F)$: (i) $delta_Fle max{delta_F^ast,1-1/(chi+1)}$; (ii) if $chige 5$, then $delta_Fin{delta_F^{ast},1-1/chi,1-1/(chi+1)}$; (iii) we determine $delta_F$ if $F$ is bipartite. In particular, (i) implies that $delta_{K_r}=delta^ast_{K_r}$. Our proof involves further developments of the recent `iterative absorbing approach.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
