Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA coding theoretic approach to the uniqueness conjecture for projective planes of prime order
59
0
0.0
(
0
)
Authors
Bhaskar Bagchi
Ask ChatGPT about the research
No Arabic abstract
An outstanding folklore conjecture asserts that, for any prime $p$, up to isomorphism the projective plane $PG(2,mathbb{F}_p)$ over the field $mathbb{F}_p := mathbb{Z}/pmathbb{Z}$ is the unique projective plane of order $p$. Let $pi$ be any projective plane of order $p$. For any partial linear space ${cal X}$, define the inclusion number $i({cal X},pi)$ to be the number of isomorphic copies of ${cal X}$ in $pi$. In this paper we prove that if ${cal X}$ has at most $log_2 p$ lines, then $i({cal X},pi)$ can be written as an explicit rational linear combination (depending only on ${cal X}$ and $p$) of the coefficients of the complete weight enumerator (c.w.e.) of the $p$-ary code of $pi$. Thus, the c.w.e. of this code carries an enormous amount of structural information about $pi$. In consequence, it is shown that if $p > 2^ 9=512$, and $pi$ has the same c.w.e. as $PG(2,mathbb{F}_p)$, then $pi$ must be isomorphic to $PG(2,mathbb{F}_p)$. Thus, the uniqueness conjecture can be approached via a thorough study of the possible c.w.e. of the codes of putative projective planes of prime order.
rate research
Read More
In 1972, Tutte posed the $3$-Flow Conjecture: that all $4$-edge-connected graphs have a nowhere zero $3$-flow. This was extended by Jaeger et al.(1992) to allow vertices to have a prescribed, possibly non-zero difference (modulo $3$) between the inflow and outflow. They conjectured that all $5$-edge-connected graphs with a valid prescription function have a nowhere zero $3$-flow meeting that prescription. Kochol (2001) showed that replacing $4$-edge-connected with $5$-edge-connected would suffice to prove the $3$-Flow Conjecture and Lovasz et al.(2013) showed that both conjectures hold if the edge connectivity condition is relaxed to $6$-edge-connected. Both problems are still open for $5$-edge-connected graphs. The $3$-Flow Conjecture was known to hold for planar graphs, as it is the dual of Grotzschs Colouring Theorem. Steinberg and Younger (1989) provided the first direct proof using flows for planar graphs, as well as a proof for projective planar graphs. Richter et al.(2016) provided the first direct proof using flows of the Strong $3$-Flow Conjecture for planar graphs. We prove the Strong $3$-Flow Conjecture for projective planar graphs.
Label the vertices of the complete graph $K_v$ with the integers ${ 0, 1, ldots, v-1 }$ and define the length of the edge between $x$ and $y$ to be $min( |x-y| , v - |x-y| )$. Let $L$ be a multiset of size $v-1$ with underlying set contained in ${ 1, ldots, lfloor v/2 rfloor }$. The Buratti-Horak-Rosa Conjecture is that there is a Hamiltonian path in $K_v$ whose edge lengths are exactly $L$ if and only if for any divisor $d$ of $v$ the number of multiples of $d$ appearing in $L$ is at most $v-d$. We introduce growable realizations, which enable us to prove many new instances of the conjecture and to reprove known results in a simpler way. As examples of the new method, we give a complete solution when the underlying set is contained in ${ 1,4,5 }$ or in ${ 1,2,3,4 }$ and a partial result when the underlying set has the form ${ 1, x, 2x }$. We believe that for any set $U$ of positive integers there is a finite set of growable realizations that implies the truth of the Buratti-Horak-Rosa Conjecture for all but finitely many multisets with underlying set $U$.
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.
We prove that, for every theory $T$ which is given by an ${mathcal L}_{omega_1,omega}$ sentence, $T$ has less than $2^{aleph_0}$ many countable models if and only if we have that, for every $Xin 2^omega$ on a cone of Turing degrees, every $X$-hyperarithmetic model of $T$ has an $X$-computable copy. We also find a concrete description, relative to some oracle, of the Turing-degree spectra of all the models of a counterexample to Vaughts conjecture.
This paper studies the problem of upper bounding the number of independent sets in a graph, expressed in terms of its degree distribution. For bipartite regular graphs, Kahn (2001) established a tight upper bound using an information-theoretic approach, and he also conjectured an upper bound for general graphs. His conjectured bound was recently proved by Sah et al. (2019), using different techniques not involving information theory. The main contribution of this work is the extension of Kahns information-theoretic proof technique to handle irregular bipartite graphs. In particular, when the bipartite graph is regular on one side, but it may be irregular in the other, the extended entropy-based proof technique yields the same bound that was conjectured by Kahn (2001) and proved by Sah et al. (2019).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
