Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Characterization of Finite Geometric Distributive Lattices
137
0
0.0
(
0
)
Added by
Pranab Basu
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Authors
Pranab Basu
Ask ChatGPT about the research
No Arabic abstract
A Lattice is a partially ordered set where both least upper bound and greatest lower bound of any pair of elements are unique and exist within the set. K{o}tter and Kschischang proved that codes in the linear lattice can be used for error and erasure-correction in random networks. Codes in the linear lattice have previously been shown to be special cases of codes in modular lattices. Two well known classifications of modular lattices are geometric and distributive lattices. We have identified the unique criterion which makes a geometric lattice distributive, thus characterizing all finite geometric distributive lattices. Our characterization helps to prove a conjecture regarding the maximum size of a distributive sublattice of a finite geometric lattice and identify the maximal case. The Whitney numbers of the class of geometric distributive lattices are also calculated. We present a few other applications of this unique characterization to derive certain results regarding linearity and complements in the linear lattice.
rate research
Read More
In the group testing problem the aim is to identify a small set of $ksim n^theta$ infected individuals out of a population size $n$, $0<theta<1$. We avail ourselves of a test procedure capable of testing groups of individuals, with the test returning a positive result iff at least one individual in the group is infected. The aim is to devise a test design with as few tests as possible so that the set of infected individuals can be identified correctly with high probability. We establish an explicit sharp information-theoretic/algorithmic phase transition $minf$ for non-adaptive group testing, where all tests are conducted in parallel. Thus, with more than $minf$ tests the infected individuals can be identified in polynomial time whp, while learning the set of infected individuals is information-theoretically impossible with fewer tests. In addition, we develop an optimal adaptive scheme where the tests are conducted in two stages.
We introduce Forman-Ricci curvature and its corresponding flow as characteristics for complex networks attempting to extend the common approach of node-based network analysis by edge-based characteristics. Following a theoretical introduction and mathematical motivation, we apply the proposed network-analytic methods to static and dynamic complex networks and compare the results with established node-based characteristics. Our work suggests a number of applications for data mining, including denoising and clustering of experimental data, as well as extrapolation of network evolution.
There is a rich connection between classical error-correcting codes, Euclidean lattices, and chiral conformal field theories. Here we show that quantum error-correcting codes, those of the stabilizer type, are related to Lorentzian lattices and non-chiral CFTs. More specifically, real self-dual stabilizer codes can be associated with even self-dual Lorentzian lattices, and thus define Narain CFTs. We dub the resulting theories code CFTs and study their properties. T-duality transformations of a code CFT, at the level of the underlying code, reduce to code equivalences. By means of such equivalences, any stabilizer code can be reduced to a graph code. We can therefore represent code CFTs by graphs. We study code CFTs with small central charge $c=nleq 12$, and find many interesting examples. Among them is a non-chiral $E_8$ theory, which is based on the root lattice of $E_8$ understood as an even self-dual Lorentzian lattice. By analyzing all graphs with $nleq 8$ nodes we find many pairs and triples of physically distinct isospectral theories. We also construct numerous modular invariant functions satisfying all the basic properties expected of the CFT partition function, yet which are not partition functions of any known CFTs. We consider the ensemble average over all code theories, calculate the corresponding partition function, and discuss its possible holographic interpretation. The paper is written in a self-contained manner, and includes an extensive pedagogical introduction and many explicit examples.
A drawing of a graph in the plane is a thrackle if every pair of edges intersects exactly once, either at a common vertex or at a proper crossing. Conways conjecture states that a thrackle has at most as many edges as vertices. In this paper, we investigate the edge-vertex ratio of maximal thrackles, that is, thrackles in which no edge between already existing vertices can be inserted such that the resulting drawing remains a thrackle. For maximal geometric and topological thrackles, we show that the edge-vertex ratio can be arbitrarily small. When forbidding isolated vertices, the edge-vertex ratio of maximal geometric thrackles can be arbitrarily close to the natural lower bound of 1/2. For maximal topological thrackles without isolated vertices, we present an infinite family with an edge-vertex ratio of 5/6.
Let $X_i, i in V$ form a Markov random field (MRF) represented by an undirected graph $G = (V,E)$, and $V$ be a subset of $V$. We determine the smallest graph that can always represent the subfield $X_i, i in V$ as an MRF. Based on this result, we obtain a necessary and sufficient condition for a subfield of a Markov tree to be also a Markov tree. When $G$ is a path so that $X_i, i in V$ form a Markov chain, it is known that the $I$-Measure is always nonnegative and the information diagram assumes a very special structure Kawabata and Yeung (1992). We prove that Markov chain is essentially the only MRF such that the $I$-Measure is always nonnegative. By applying our characterization of the smallest graph representation of a subfield of an MRF, we develop a recursive approach for constructing information diagrams for MRFs. Our work is built on the set-theoretic characterization of an MRF in Yeung, Lee, and Ye (2002).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
