10 papers
Quantum Query Complexity of Persistence Statistics in Graph Zigzags
Cheng Xin
We study the query complexity of estimating scalar summaries of zigzag bar lifetimes from snapshot-adjacency bits. For graphs on labeled vertices, let …
Quantum Query Algorithms for the Constructive Diagonal Ramsey Theorem
Cheng Xin
The constructive diagonal Ramsey problem asks, given adjacency-oracle access to an -vertex graph, for a clique or independent set of the order guaranteed by Ramsey's theorem. We…
On the Turán number of the expansion of the book
Xin Cheng, Dániel Gerbner, Hilal Hama Karim
The book with pages is the graph on vertices consisting of triangles which intersect at exactly one common edge. For a given graph , the -expansion of …
Forbidding matching as trace in uniform hypergraphs
Yichen Wang, Xin Cheng, Ervin Győri +1
We say a hypergraph contains a hypergraph as trace if there exists a vertex subset such that and $…
The Turán number of the Cartesian product of a star and an edge
Xiamiao Zhao, Xin Cheng, Cheng Chi +3
Let denote the cycle of length , be a star with edges. And let be the graph consisting of copies of sharing one fixed edge. Equivalently, $B_t=K_…
Forbidding edge-critical graphs as trace in uniform hypergraphs
Yichen Wang, Xin Cheng, Ervin Győri +3
We say a hypergraph contains a graph as trace if there exists a vertex subset such that and $\{e \cap S \mid e \in E(\ma…
The Turán number of Berge paths
Xin Cheng, Dániel Gerbner, Hilal Hama Karim +2
A Berge path of length in an -uniform hypergraph is a collection of hyperedges and vertices such that for…
On the Turán number of the expansion of the -fan
Xin Cheng, Dániel Gerbner, Hilal Hama Karim +1
The -fan is the graph on vertices consisting of triangles which intersect at exactly one common vertex. For a given graph , the -expansion of is the $…
On Turán problems for suspension hypergraphs
Xin Cheng, Dániel Gerbner, Hilal Hama Karim +1
For a given graph , the -uniform suspension of is the -uniform hypergraph obtained from by taking new vertices and adding them to every edge. In this paper,…
Facility Assignment with Fair Cost Sharing: Equilibrium and Mechanism Design
Mengfan Ma, Mingyu Xiao, Tian Bai +1
In the one-dimensional facility assignment problem, m facilities and n agents are positioned along the real line. Each agent will be assigned to a single facility to receive servic…