7 papers · 1 filter
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…