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

Xizhi Liu

Xizhi Liu contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.COData Structures and AlgorithmsMachine Learning

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
8works
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

8 published item(s)

preprint2022arXiv

Tight query complexity bounds for learning graph partitions

Given a partition of a graph into connected components, the membership oracle asserts whether any two vertices of the graph lie in the same component or not. We prove that for $n\ge k\ge 2$, learning the components of an $n$-vertex hidden graph with $k$ components requires at least $(k-1)n-\binom k2$ membership queries. Our result improves on the best known information-theoretic bound of $Ω(n\log k)$ queries, and exactly matches the query complexity of the algorithm introduced by [Reyzin and Srivastava, 2007] for this problem. Additionally, we introduce an oracle, with access to which one can learn the number of components of $G$ in asymptotically fewer queries than learning the full partition, thus answering another question posed by the same authors. Lastly, we introduce a more applicable version of this oracle, and prove asymptotically tight bounds of $\widetildeΘ(m)$ queries for both learning and verifying an $m$-edge hidden graph $G$ using it.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Hypergraphs with many extremal configurations

For every positive integer $t$ we construct a finite family of triple systems ${\mathcal M}_t$, determine its Turán number, and show that there are $t$ extremal ${\mathcal M}_t$-free configurations that are far from each other in edit-distance. We also prove a strong stability theorem: every ${\mathcal M}_t$-free triple system whose size is close to the maximum size is a subgraph of one of these $t$ extremal configurations after removing a small proportion of vertices. This is the first stability theorem for a hypergraph problem with an arbitrary (finite) number of extremal configurations. Moreover, the extremal hypergraphs have very different shadow sizes (unlike the case of the famous Turán tetrahedron conjecture). Hence a corollary of our main result is that the boundary of the feasible region of ${\mathcal M}_t$ has exactly $t$ global maxima.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Independent sets in hypergraphs omitting an intersection

A $k$-uniform hypergraph with $n$ vertices is an $(n,k,\ell)$-omitting system if it does not contain two edges whose intersection has size exactly $\ell$. If in addition it does not contain two edges whose intersection has size greater than $\ell$, then it is an $(n,k,\ell)$-system. Rödl and Šiňajová proved a lower bound for the independence number of $(n,k,\ell)$-systems that is sharp in order of magnitude for fixed $2 \le \ell \le k-1$. We consider the same question for the larger class of $(n,k,\ell)$-omitting systems. For $k\le 2\ell+1$, we believe that the behavior is similar to the case of $(n,k,\ell)$-systems and prove a nontrivial lower bound for the first open case $\ell=k-2$. For $k>2\ell+1$ we give new lower and upper bounds which show that the minimum independence number of $(n,k,\ell)$-omitting systems has a very different behavior than for $(n,k,\ell)$-systems. Our lower bound for $\ell=k-2$ uses some adaptations of the random greedy independent set algorithm, and our upper bounds (constructions) for $k> 2\ell+1$ are obtained from some pseudorandom graphs. We also prove some related results where we forbid more than two edges with a prescribed common intersection size and this leads to some applications in Ramsey theory. For example, we obtain good bounds for the Ramsey number $r_{k}(F^{k},t)$, where $F^{k}$ is the $k$-uniform Fan. Here the behavior is quite different than the case $k=2$ which reduces to the classical graph Ramsey number $r(3,t)$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A note on hypergraphs without non-trivial intersecting subgraphs

A hypergraph $\mathcal{F}$ is non-trivial intersecting if every two edges in it have a nonempty intersection but no vertex is contained in all edges of $\mathcal{F}$. Mubayi and Verstraëte showed that for every $k \ge d+1 \ge 3$ and $n \ge (d+1)n/d$ every $k$-graph $\mathcal{H}$ on $n$ vertices without a non-trivial intersecting subgraph of size $d+1$ contains at most $\binom{n-1}{k-1}$ edges. They conjectured that the same conclusion holds for all $d \ge k \ge 4$ and sufficiently large $n$. We confirm their conjecture by proving a stronger statement. They also conjectured that for $m \ge 4$ and sufficiently large $n$ the maximum size of a $3$-graph on $n$ vertices without a non-trivial intersecting subgraph of size $3m+1$ is achieved by certain Steiner systems. We give a construction with more edges showing that their conjecture is not true in general.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On a generalized Erdős-Rademacher problem

The triangle covering number of a graph is the minimum number of vertices that hit all triangles. Given positive integers $s,t$ and an $n$-vertex graph $G$ with $\lfloor n^2/4 \rfloor +t$ edges and triangle covering number $s$, we determine (for large $n$) sharp bounds on the minimum number of triangles in $G$ and also describe the extremal constructions. Similar results are proved for cliques of larger size and color critical graphs. This extends classical work of Rademacher, Erd\H os, and Lovász-Simonovits whose results apply only to $s \le t$. Our results also address two conjectures of Xiao and Katona. We prove one of them and give a counterexample and prove a modified version of the other conjecture.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Structural results for conditionally intersecting families and some applications

Let $k\ge d\ge 3$ be fixed. Let $\mathcal{F}$ be a $k$-uniform family on $[n]$. Then $\mathcal{F}$ is $(d,s)$-conditionally intersecting if it does not contain $d$ sets with union of size at most $s$ and empty intersection. Answering a question of Frankl, we present some structural results for families that are $(d,s)$-conditionally intersecting with $s\ge 2k+d-3$, and families that are $(k,2k)$-conditionally intersecting. As applications of our structural results, we present some new proofs to the upper bounds for the size of the following $k$-uniform families on $[n]$. (a) $(d,2k+d-3)$-conditionally intersecting families with $n\ge 3k^5$. (b) $(k,2k)$-conditionally intersecting families with $n\ge k^2/(k-1)$. (c) Nonintersecting $(3,2k)$-conditionally intersecting families with $n\ge 3k\binom{2k}{k}$. Our results for $(c)$ confirms a conjecture of Mammoliti and Britz for the case $d=3$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Tight bounds for Katona's shadow intersection theorem

A fundamental result in extremal set theory is Katona's shadow intersection theorem, which extends the Kruskal-Katona theorem by giving a lower bound on the size of the shadow of an intersecting family of $k$-sets in terms of its size. We improve this classical result and a related result of Ahlswede, Aydinian, and Khachatrian by proving tight bounds for families that can be quite small. For example, when $k=3$ our result is sharp for all families with $n$ points and at least $3n-7$ triples. Katona's theorem was extended by Frankl to families with matching number $s$. We improve Frankl's result by giving tight bounds for large $n$.

0 citations0 reviewsNo code linkedOpen access