BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Chong Shangguan

Chong Shangguan contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.COInformation Theorymath.IT

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
6works
0followers
3topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

6 published item(s)

preprint2023arXiv

Improved Gilbert-Varshamov bounds for hopping cyclic codes and optical orthogonal codes

Hopping cyclic codes (HCCs) are (non-linear) cyclic codes with the additional property that the $n$ cyclic shifts of every given codeword are all distinct, where $n$ is the code length. Constant weight binary hopping cyclic codes are also known as optical orthogonal codes (OOCs). HCCs and OOCs have various practical applications and have been studied extensively over the years. The main concern of this paper is to present improved Gilbert-Varshamov type lower bounds for these codes, when the minimum distance is bounded below by a linear factor of the code length. For HCCs, we improve the previously best known lower bound of Niu, Xing, and Yuan by a linear factor of the code length. For OOCs, we improve the previously best known lower bound of Chung, Salehi, and Wei, and Yang and Fuja by a quadratic factor of the code length. As by-products, we also provide improved lower bounds for frequency hopping sequences sets and error-correcting weakly mutually uncorrelated codes. Our proofs are based on tools from probability theory and graph theory, in particular the McDiarmid's inequality on the concentration of Lipschitz functions and the independence number of locally sparse graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Degenerate Turán densities of sparse hypergraphs

For fixed integers $r>k\ge 2,e\ge 3$, let $f_r(n,er-(e-1)k,e)$ be the maximum number of edges in an $r$-uniform hypergraph in which the union of any $e$ distinct edges contains at least $er-(e-1)k+1$ vertices. A classical result of Brown, Erdős and Sós in 1973 showed that $f_r(n,er-(e-1)k,e)=Θ(n^k).$ The degenerate Turán density is defined to be the limit (if it exists) $$π(r,k,e):=\lim_{n\rightarrow\infty}\frac{f_r(n,er-(e-1)k,e)}{n^k}.$$ Extending a recent result of Glock for the special case of $r=3,k=2,e=3$, we show that $$π(r,2,3):=\lim_{n\rightarrow\infty}\frac{f_r(n,3r-4,3)}{n^2}=\frac{1}{r^2-r-1}$$ for arbitrary fixed $r\ge 4$. For the more general cases $r>k\ge 3$, we show that $$\frac{1}{r^k-r}\le\liminf_{n\rightarrow\infty}\frac{f_r(n,3r-2k,3)}{n^k}\le\limsup_{n\rightarrow\infty}\frac{f_r(n,3r-2k,3)}{n^k}\le \frac{1}{k!\binom{r}{k}-\frac{k!}{2}}.$$ The main difficulties in proving these results are the constructions establishing the lower bounds. The first construction is recursive and purely combinatorial, and is based on a (carefully designed) approximate induced decomposition of the complete graph, whereas the second construction is algebraic, and is proved by a newly defined matrix property which we call {\it strongly 3-perfect hashing}.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Error Detection and Correction in Communication Networks

Let $G$ be a connected graph on $n$ vertices and $C$ be an $(n,k,d)$ code with $d\ge 2$, defined on the alphabet set $\{0,1\}^m$. Suppose that for $1\le i\le n$, the $i$-th vertex of $G$ holds an input symbol $x_i\in\{0,1\}^m$ and let $\vec{x}=(x_1,\ldots,x_n)\in\{0,1\}^{mn}$ be the input vector formed by those symbols. Assume that each vertex of $G$ can communicate with its neighbors by transmitting messages along the edges, and these vertices must decide deterministically, according to a predetermined communication protocol, that whether $\vec{x}\in C$. Then what is the minimum communication cost to solve this problem? Moreover, if $\vec{x}\not\in C$, say, there is less than $\lfloor(d-1)/2\rfloor$ input errors among the $x_i$'s, then what is the minimum communication cost for error correction? In this paper we initiate the study of the two problems mentioned above. For the error detection problem, we obtain two lower bounds on the communication cost as functions of $n,k,d,m$, and our bounds are tight for several graphs and codes. For the error correction problem, we design a protocol which can efficiently correct a single input error when $G$ is a cycle and $C$ is a repetition code. We also present several interesting problems for further research.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

New Turán exponents for two extremal hypergraph problems

An $r$-uniform hypergraph is called $t$-cancellative if for any $t+2$ distinct edges $A_1,\ldots,A_t,B,C$, it holds that $(\cup_{i=1}^t A_i)\cup B\neq (\cup_{i=1}^t A_i)\cup C$. It is called $t$-union-free if for any two distinct subsets $\mathcal{A},\mathcal{B}$, each consisting of at most $t$ edges, it holds that $\cup_{A\in\mathcal{A}} A\neq \cup_{B\in\mathcal{B}} B$. Let $C_t(n,r)$ (resp. $U_t(n,r)$) denote the maximum number of edges of a $t$-cancellative (resp. $t$-union-free) $r$-uniform hypergraph on $n$ vertices. Among other results, we show that for fixed $r\ge 3,t\ge 3$ and $n\rightarrow\infty$ $$Ω(n^{\lfloor\frac{2r}{t+2}\rfloor+\frac{2r\pmod{t+2}}{t+1}})=C_t(n,r)=O(n^{\lceil\frac{r}{\lfloor t/2\rfloor+1}\rceil})\text{ and } Ω(n^{\frac{r}{t-1}})=U_t(n,r)=O(n^{\lceil\frac{r}{t-1}\rceil}),$$ thereby significantly narrowing the gap between the previously known lower and upper bounds. In particular, we determine the Turán exponent of $C_t(n,r)$ when $2\mid t \text{ and } (t/2+1)\mid r$, and of $U_t(n,r)$ when $(t-1)\mid r$. The main tool used in proving the two lower bounds is a novel connection between these problems and sparse hypergraphs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Sparse Hypergraphs with Applications to Coding Theory

For fixed integers $r\ge 3,e\ge 3,v\ge r+1$, an $r$-uniform hypergraph is called $\mathscr{G}_r(v,e)$-free if the union of any $e$ distinct edges contains at least $v+1$ vertices. Brown, Erdős and Sós showed that the maximum number of edges of such a hypergraph on $n$ vertices, denoted as $f_r(n,v,e)$, satisfies $$Ω(n^{\frac{er-v}{e-1}})=f_r(n,v,e)=\mathcal{O}(n^{\lceil\frac{er-v}{e-1}\rceil}).$$ For $e-1\mid er-v$, the lower bound matches the upper bound up to a constant factor; whereas for $e-1\nmid er-v$, in general it is a notoriously hard problem to determine the correct exponent of $n$. Among other results, we improve the above lower bound by showing that $$f_r(n,v,e)=Ω(n^{\frac{er-v}{e-1}}(\log n)^{\frac{1}{e-1}})$$ for any $r,e,v$ satisfying $\gcd(e-1,er-v)=1$. The hypergraph we constructed is in fact $\mathscr{G}_r(ir-\lceil\frac{(i-1)(er-v)}{e-1}\rceil,i)$-free for every $2\le i\le e$, and it has several interesting applications in Coding Theory. The proof of the new lower bound is based on a novel application of the lower bound on the hypergraph independence number due to Duke, Lefmann, and R{ö}dl.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The hat guessing number of graphs

Consider the following hat guessing game: $n$ players are placed on $n$ vertices of a graph, each wearing a hat whose color is arbitrarily chosen from a set of $q$ possible colors. Each player can see the hat colors of his neighbors, but not his own hat color. All of the players are asked to guess their own hat colors simultaneously, according to a predetermined guessing strategy and the hat colors they see, where no communication between them is allowed. Given a graph $G$, its hat guessing number ${\rm{HG}}(G)$ is the largest integer $q$ such that there exists a guessing strategy guaranteeing at least one correct guess for any hat assignment of $q$ possible colors. In 2008, Butler et al. asked whether the hat guessing number of the complete bipartite graph $K_{n,n}$ is at least some fixed positive (fractional) power of $n$. We answer this question affirmatively, showing that for sufficiently large $n$, the complete $r$-partite graph $K_{n,\ldots,n}$ satisfies ${\rm{HG}}(K_{n,\ldots,n})=Ω(n^{\frac{r-1}{r}-o(1)})$. Our guessing strategy is based on a probabilistic construction and other combinatorial ideas, and can be extended to show that ${\rm{HG}}(\vec{C}_{n,\ldots,n})=Ω(n^{\frac{1}{r}-o(1)})$, where $\vec{C}_{n,\ldots,n}$ is the blow-up of a directed $r$-cycle, and where for directed graphs each player sees only the hat colors of his outneighbors.

0 citations0 reviewsNo code linkedOpen access