11 papers · 1 filter
Random independent sets in triangle-free and linear Berge--free hypergraphs
Jing Yu, Junchi Zhang
We study probability distributions on independent sets of uniform hypergraphs with local constraints. For a positive vertex-weight function on an -uniform hypergraph, de…
Bounded Twin-Width Tournaments are $\dchi$-Bounded
Chaoliang Tang, Junchi Zhang
For a tournament and a vertex ordering , let be the graph of backward arcs in . The diclique number of a tournament is $\domega(T)=\min_{\prec}ω(T^{\p…
Real-analytic finitely forcible kernels
Junchi Zhang
Lovász and Szegedy asked whether a nonconstant continuous, or even smooth, finitely forcible kernel exists. For every , we construct an explicit nonconstant real-anal…
Infinitesimal finite forcibility and step kernels
Xichao Shu, Jing Yu, Junchi Zhang
We characterize infinitesimal finite forcibility for bounded symmetric real kernels. We prove that the graph-density gradients at a kernel span a finite-dimensional space if and on…
On independent sets in uncrowded uniform hypergraphs
Jing Yu, Junchi Zhang
We prove an average-degree lower bound on the independence number of uncrowded uniform hypergraphs. For every fixed and every , there exists such that…
The list coloring number of uncrowded hypergraphs
Jing Yu, Junchi Zhang
We prove that for every fixed integer and every , every sufficiently large finite uncrowded -uniform hypergraph of maximum degree has list chrom…
Submodular flows and extreme flows on measurable spaces
Jing Yu, Junchi Zhang, Mingyang Zhou
The theory of submodular flows, introduced by Edmonds and Giles, is a cornerstone of combinatorial optimization, unifying network flows, matroid intersections and directed cut cove…
Hypergraph independence bounds: from maximum degree to average degree
Jing Yu, Junchi Zhang
We prove a transfer theorem for hereditary classes of -uniform hypergraphs. Let be such a class, and for write and for the maximu…
The linear Turán number of the 3-graph
Chaoliang Tang, Hehui Wu, Junchi Zhang
We prove that for any linear 3-graph on vertices without a path of length 5, the number of edges is at most , and the equality holds if and only if the graph is…
New lower bounds on the non-repetitive chromatic number of some graphs
Tianyi Tao, Junchi Zhang, Wentao Zhang +1
A graph \( G \) is said to be (vertex) non-repetitively colored if no simple path in \( G \) has a sequence of vertex colors that forms a repetition. Formally, a coloring \( c: V(G…
On 1-11-representability and multi-1-11-representability of graphs
Mohammed Alshammari, Sergey Kitaev, Chaoliang Tang +2
Jeff Remmel introduced the concept of a -11-representable graph in 2017. This concept was first explored by Cheon et al. in 2019, who considered it as a natural extension of wor…