Counting shellings of complete bipartite graphs and trees by Gao, Yibo, Peng, Junyao

“…In this paper, we focus on complete bipartite graphs and trees. For complete bipartite graphs, we obtain an exact formula for their shelling numbers. …”
Get full text

Coloring Bipartite Graphs with Semi-small List Size by Zhu, Daniel G.

“…Abstract Recently, Alon, Cambie, and Kang introduced asymmetric list coloring of bipartite graphs, where the size of each vertex’s list depends on its part. …”
Get full text

Root polytopes, Tutte polynomials, and a duality theorem for bipartite graphs by Kalman, Tamas, Postnikov, Alexander

“…Let G be a connected bipartite graph with colour classes E and V and root polytope Q. …”
Get full text
Get full text

Sidorenko's conjecture, colorings and independent sets by Csikvari, Peter, Lin, Zhicong

“…For instance, for a bipartite graph H the number of q-colorings ch(H, q) satisfies ch(H, q) ≥ q[superscript v(H)](q − 1/q)[superscript e(H)]. …”
Get full text
Get full text

Conflict-Free Coloring of Graphs by Abel, Zachary R, Alvarez, Victor, Demaine, Erik D, Fekete, Sándor P., Gour, Aman, Hesterberg, Adam Classen, Keldenich, Phillip, Scheffer, Christian

“…For open neighborhoods, we show that every planar bipartite graph has a conflict-free coloring with at most four colors; on the other hand, we prove that for k ∈ {1,2,3}, it is NP-complete to decide whether a planar bipartite graph has a conflict-free k-coloring. …”
Get full text

A Fast L-p Spike Alignment Metric by Dubbs, Alexander Joseph, Seiler, Brad A., Magnasco, Marcel O.

“…We show how to implement a fast algorithm for the computation of this metric based on bipartite graph matching theory.…”
Get full text

The Green’s function for the Hückel (tight binding) model by Movassagh, Ramis, Tsuji, Yuta, Hoffmann, Roald, Strang, W. Gilbert

“…The matrix representation of this model is isomorphic to an unoriented vertex adjacency matrix of a bipartite graph, which is also the Laplacian matrix plus twice the identity. …”
Get full text
Get full text

Erdos–Hajnal-type theorems in hypergraphs by Conlon, David, Fox, Jacob, Sudakov, Benny

“…However, it is known that an H-free graph must contain a complete or empty bipartite graph with parts of polynomial size. We prove an analogue of this result for 3-uniform hypergraphs, showing that if a 3-uniform hypergraph on n vertices is H-free, for any given H, then it must contain a complete or empty tripartite subgraph with parts of order c(logn)[superscript 1/2 + δ(H)], where δ(H) > 0 depends only on H. …”
Get full text

Nondegenerate Spheres in Four Dimensions by Do, Thao

“…While proving this, we find it convenient to work with a more general definition of nondegeneracy: a bipartite graph $$G=(P,Q)$$ G = ( P , Q ) is called $$\beta $$ β -nondegenerate if $$|N(q_1)\cap N(q_2)|<\beta |N(q_1)|$$ | N ( q 1 ) ∩ N ( q 2 ) | < β | N ( q 1 ) | for any two distinct vertices $$q_1,q_2\in Q$$ q 1 , q 2 ∈ Q ; here N(q) denotes the set of neighbors of q and $$\beta $$ β is some positive constant less than 1. …”
Get full text

Matroids and integrality gaps for hypergraphic steiner tree relaxations by Goemans, Michel X., Olver, Neil, Rothvoss, Thomas, Zenklusen, Rico

Get full text
Get full text

A fast new algorithm for weak graph regularity by Lovász, László Miklós, Zhao, Yufei

“…The algorithm outputs an approximation of a given graph as a weighted sum of ϵ-O(1) many complete bipartite graphs. As a corollary, we give a deterministic algorithm for estimating the number of copies of H in an n-vertex graph G up to an additive error of at most ϵn v(H), in time ϵ-O H(1) n 2…”
Get full text

The number of independent sets in an irregular graph by Sah, Ashwin, Sawhney, Mehtaab, Zhao, Yufei

“…Equality occurs when G is a disjoint union of complete bipartite graphs. The inequality was previously proved for regular graphs by Kahn and Zhao. …”
Get full text

A reverse Sidorenko inequality by Sah, Ashwin, Sawhney, Mehtaab, Stoner, David, Zhao, Yufei

“…For 2-spin Ising models, our results give a complete characterization of extremal graphs: complete bipartite graphs maximize the partition function of 2-spin antiferromagnetic models and cliques maximize the partition function of ferromagnetic models. …”
Get full text