Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRecent Colorings And Labelings In Topological Coding
85
0
0.0
(
0
)
Added by
Bing Yao
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Topological Coding consists of two different kinds of mathematics: topological structure and mathematical relation. The colorings and labelings of graph theory are main techniques in topological coding applied in asymmetric encryption system. Topsnut-gpws (also, colored graphs) have the following advantages: (1) Run fast in communication networks because they are saved in computer by popular matrices rather than pictures. (2) Produce easily text-based (number-based) strings for encrypt files. (3) Diversity of asymmetric ciphers, one public-key corresponds to more private-keys, or more public-keys correspond more private-keys. (4) Irreversibility, Topsnut-gpws can generate quickly text-based (number-based) strings with bytes as long as desired, but these strings can not reconstruct the original Topsnut-gpws. (5) Computational security, since there are many non-polynomial (NP-complete, NP-hard) algorithms in creating Topsnut-gpws. (6) Provable security, since there are many mathematical conjectures (open problems) in graph labelings and graph colorings. We are committed to create more kinds of new Topsnut-gpws to approximate practical applications and antiquantum computation, and try to use algebraic method and Topsnut-gpws to establish graphic group, graphic lattice, graph homomorphism etc.
rate research
Read More
We consider a communication network where there exist wiretappers who can access a subset of channels, called a wiretap set, which is chosen from a given collection of wiretap sets. The collection of wiretap sets can be arbitrary. Secure network coding is applied to prevent the source information from being leaked to the wiretappers. In secure network coding, the required alphabet size is an open problem not only of theoretical interest but also of practical importance, because it is closely related to the implementation of such coding schemes in terms of computational complexity and storage requirement. In this paper, we develop a systematic graph-theoretic approach for improving Cai and Yeungs lower bound on the required alphabet size for the existence of secure network codes. The new lower bound thus obtained, which depends only on the network topology and the collection of wiretap sets, can be significantly smaller than Cai and Yeungs lower bound. A polynomial-time algorithm is devised for efficient computation of the new lower bound.
Barnette identified two interesting classes of cubic polyhedral graphs for which he conjectured the existence of a Hamiltonian cycle. Goodey proved the conjecture for the intersection of the two classes. We examine these classes from the point of view of distance-two colorings. A distance-two $r$-coloring of a graph $G$ is an assignment of $r$ colors to the vertices of $G$ so that any two vertices at distance at most two have different colors. Note that a cubic graph needs at least four colors. The distance-two four-coloring problem for cubic planar graphs is known to be NP-complete. We claim the problem remains NP-complete for tri-connected bipartite cubic planar graphs, which we call type-one Barnette graphs, since they are the first class identified by Barnette. By contrast, we claim the problem is polynomial for cubic plane graphs with face sizes $3, 4, 5,$ or $6$, which we call type-two Barnette graphs, because of their relation to Barnettes second conjecture. We call Goodey graphs those type-two Barnette graphs all of whose faces have size $4$ or $6$. We fully describe all Goodey graphs that admit a distance-two four-coloring, and characterize the remaining type-two Barnette graphs that admit a distance-two four-coloring according to their face size. For quartic plane graphs, the analogue of type-two Barnette graphs are graphs with face sizes $3$ or $4$. For this class, the distance-two four-coloring problem is also polynomial; in fact, we can again fully describe all colorable instances -- there are exactly two such graphs.
We show that the natural Glauber dynamics mixes rapidly and generates a random proper edge-coloring of a graph with maximum degree $Delta$ whenever the number of colors is at least $qgeq (frac{10}{3} + epsilon)Delta$, where $epsilon>0$ is arbitrary and the maximum degree satisfies $Delta geq C$ for a constant $C = C(epsilon)$ depending only on $epsilon$. For edge-colorings, this improves upon prior work cite{Vig99, CDMPP19} which show rapid mixing when $qgeq (frac{11}{3}-epsilon_0 ) Delta$, where $epsilon_0 approx 10^{-5}$ is a small fixed constant. At the heart of our proof, we establish a matrix trickle-down theorem, generalizing Oppenheims influential result, as a new technique to prove that a high dimensional simplical complex is a local spectral expander.
A mathematical topology with matrix is a natural representation of a coding relational structure that is found in many fields of the world. Matrices are very important in computation of real applications, s ce matrices are easy saved in computer and run quickly, as well as matrices are convenient to deal with communities of current networks, such as Laplacian matrices, adjacent matrices in graph theory. Motivated from convenient, useful and powerful matrices used in computation and investigation of todays networks, we have introduced Topcode-matrices, which are matrices of order $3times q$ and differ from popular matrices applied in linear algebra and computer science. Topcode-matrices can use numbers, letters, Chinese characters, sets, graphs, algebraic groups emph{etc.} as their elements. One important thing is that Topcode-matrices of numbers can derive easily number strings, since number strings are text-based passwords used in information security. Topcode-matrices can be used to describe topological graphic passwords (Topsnut-gpws) used in information security and graph connected properties for solving some problems coming in the investigation of Graph Networks and Graph Neural Networks proposed by GoogleBrain and DeepMind. Our topics, in this article, are: Topsnut-matrices, Topcode-matrices, Hanzi-matrices, adjacency ve-value matrices and pan-Topcode-matrices, and some connections between these Topcode-matrices will be proven. We will discuss algebraic groups obtained from the above matrices, graph groups, graph networking groups and number string groups for encrypting different communities of dynamic networks. The operations and results on our matrices help us to set up our overall security mechanism to protect networks.
Index coding, a source coding problem over broadcast channels, has been a subject of both theoretical and practical interest since its introduction (by Birk and Kol, 1998). In short, the problem can be defined as follows: there is an input $textbf{x} triangleq (textbf{x}_1, dots, textbf{x}_n)$, a set of $n$ clients who each desire a single symbol $textbf{x}_i$ of the input, and a broadcaster whose goal is to send as few messages as possible to all clients so that each one can recover its desired symbol. Additionally, each client has some predetermined side information, corresponding to certain symbols of the input $textbf{x}$, which we represent as the side information graph $mathcal{G}$. The graph $mathcal{G}$ has a vertex $v_i$ for each client and a directed edge $(v_i, v_j)$ indicating that client $i$ knows the $j$th symbol of the input. Given a fixed side information graph $mathcal{G}$, we are interested in determining or approximating the broadcast rate of index coding on the graph, i.e. the fewest number of messages the broadcaster can transmit so that every client gets their desired information. Using index coding schemes based on linear programs (LPs), we take a two-pronged approach to approximating the broadcast rate. First, extending earlier work on planar graphs, we focus on approximating the broadcast rate for special graph families such as graphs with small chromatic number and disk graphs. In certain cases, we are able to show that simple LP-based schemes give constant-factor approximations of the broadcast rate, which seem extremely difficult to obtain in the general case. Second, we provide several LP-based schemes for the general case which are not constant-factor approximations, but which strictly improve on the prior best-known schemes.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
