Search

Sidewalk Autonomous Delivery Robots (SADRs) present a promising alternative for mitigating excessive delivery traffic in smart cities. These bots operate at pedestrian speed and work in conjunction with vans to offer efficient delivery services. Existing research emphasises the development of coordinated service schedules for vans and bots to optimise customer service. In contrast, this study examines the influence of bot return policies on their travel back to designated stations after task completion. We assess three distinct return policies that dictate the station selection for bot returns and explore the relocation of bots between stations using vans. Specifically, we present a reformulation of the fleet sizing problem as a minimum cost matching problem in a bipartite graph. This reformulation allows for the efficient calculation of optimal solutions for bot fleet sizing under different return policies within polynomial time. Notably, this computational efficiency enables the analysis of large-scale cases without sacrificing the evaluation of policies with heuristic gaps. Our findings highlight the importance of carefully selecting the appropriate return policy, as the best policies have the potential to decrease the bot fleet size by up to 70%. [ABSTRACT FROM AUTHOR]

The Graph Minors Structure Theorem of Robertson and Seymour asserts that, for every graph H, every H-minor-free graph can be obtained by clique-sums of "almost embeddable" graphs. Here a graph is "almost embeddable" if it can be obtained from a graph of bounded Euler-genus by pasting graphs of bounded pathwidth in an "orderly fashion" into a bounded number of faces, called the vortices, and then adding a bounded number of additional vertices, called apices, with arbitrary neighborhoods. Our main result is a full classification of all graphs H for which the use of vortices in the theorem above can be avoided. To this end, we identify a (parametric) graph \(\mathscr{S}_{t}\) and prove that all \(\mathscr{S}_{t}\) -minor-free graphs can be obtained by clique-sums of graphs embeddable in a surface of bounded Euler-genus after deleting a bounded number of vertices. We show that this result is tight in the sense that the appearance of vortices cannot be avoided for H-minor-free graphs, whenever H is not a minor of \(\mathscr{S}_{t}\) for some \(t\in \mathbb {N}\). Using our new structure theorem, we design an algorithm that, given an \(\mathscr{S}_{t}\) -minor-free graph G, computes the generating function of all perfect matchings of G in polynomial time. Our results, combined with known complexity results, imply a complete characterization of minor-closed graph classes where the number of perfect matchings is polynomially computable: They are exactly those graph classes that do not contain every \(\mathscr{S}_{t}\) as a minor. This provides a sharp complexity dichotomy for the problem of counting perfect matchings in minor-closed classes. [ABSTRACT FROM AUTHOR]

The article focuses on studying randomized greedy matching algorithms, particularly the Modified Randomized Greedy (MRG) algorithm and its weaker version named Random Decision Order (RDO). It mentions the RDO algorithm is shown to provide a 0.639-approximation for bipartite graphs and a 0.531-approximation for general graphs, leading to a substantial improvement in the approximation ratio of MRG.

Dirac cones are difficult to achieve in a square lattice with full symmetry. Here, we have theoretically investigated a bipartite tetragonal lattice composed of tetragons and octagons using both Tight-Binding (TB) model and density functional theory (DFT) calculations. The TB model predicts that the system exhibits nodal line semi-metallic properties when the on-site energies of all atoms are identical. When the on-site energies differ, the formation of an elliptical Dirac cone is predicted. Its physical properties (anisotropy, tilting, merging, and emerging) can be regulated by the hopping energies. An exact analytical formula is derived to determine the position of the Dirac point by the TB parameters, and a criterion for the existence of Dirac cones is obtained. The "divide-and-coupling" method is applied to understand the origin of the Dirac cone, which involves dividing the bands into several groups and examining the couplings among inter-groups and intra-groups. Various practical systems computed by DFT methods, e.g., t-BN, t-Si, 4,12,2-graphyne, and t-SiC, are also examined, and they all possess nodal lines or Dirac cones as predicted by the TB model. The results provide theoretical foundation for designing novel Dirac materials with tetragonal symmetry. [ABSTRACT FROM AUTHOR]

In bipartite networks, nodes are divided into two different sets (namely, a set of actors and a set of events), and edges exist only between actors and events. The degree sequence of bipartite graph models may contain sensitive information. Thus, it is desirable to release noisy degree sequence, not the original degree sequence, in order to decrease the risk of privacy leakage. In this article, we propose to release the degree sequence in general bipartite graphs by adding discrete Laplace noises, which satisfies differential privacy. We use the moment method to estimate the unknown model parameter. The resulted estimator satisfies differential privacy. We establish the consistency and asymptotic normality of the differentially private estimator when the number of nodes goes to infinity. Finally, we apply our theoretical results to the logistic model and the log -linear model. [ABSTRACT FROM AUTHOR]

The general position problem in graph theory asks for the largest set S of vertices of a graph G such that no shortest path of G contains more than two vertices of S. In this paper we consider a variant of the general position problem called the monophonic position problem , obtained by replacing 'shortest path' by 'induced path'. We prove some basic properties and bounds for the monophonic position number of a graph and determine the monophonic position number of some graph families, including unicyclic graphs, complements of bipartite graphs and split graphs. We show that the monophonic position number of triangle-free graphs is bounded above by the independence number. We present realisation results for the general position number, monophonic position number and monophonic hull number. Finally we discuss the complexity of the monophonic position problem. [ABSTRACT FROM AUTHOR]

A Roman { 3 } -dominating function on a graph G is a function f : V (G) → { 0 , 1 , 2 , 3 } having the property that for any vertex u ∈ V (G) , if f (u) = 0 , then ∑ v ∈ N G (u) f (v) ≥ 3 , and if f (u) = 1 , then ∑ v ∈ N G (u) f (v) ≥ 2. The weight of a Roman { 3 } -dominating function f is the sum f (V (G)) = ∑ v ∈ V (G) f (v) and the minimum weight of a Roman { 3 } -dominating function on G is called the Roman { 3 } -domination number of G and is denoted by γ { R 3 } (G). Given a graph G , Roman { 3 } - domination asks to find the minimum weight of a Roman { 3 } -dominating function on G. In this paper, we study the algorithmic aspects of Roman { 3 } - domination on various graph classes. We show that the decision version of Roman { 3 } - domination remains NP -complete for chordal bipartite graphs, planar graphs, star-convex bipartite graphs, and chordal graphs. We show that Roman { 3 } - domination cannot be approximated within a ratio of (1 3 − ɛ) ln | V (G) | for any ɛ > 0 unless P = NP for bipartite graphs as well as chordal graphs, whereas Roman { 3 } - domination can be approximated within a factor of O (ln Δ) for graphs having maximum degree Δ. We also show that Roman { 3 } - domination is APX -complete for graphs with maximum degree 4. On the positive side, we show that Roman { 3 } - domination can be solved in linear time for chain graphs and cographs. [ABSTRACT FROM AUTHOR]

We introduce the multicolored graph realization problem (MGR). The input to this problem is a colored graph (G , φ) , i.e., a graph G together with a coloring φ on its vertices. We associate each colored graph (G , φ) with a cluster graph (G φ) in which, after collapsing all vertices with the same color to a node, we remove multiple edges and self-loops. A set of vertices S is multicolored when S has exactly one vertex from each color class. The MGR problem is to decide whether there is a multicolored set S so that, after identifying each vertex in S with its color class, G [ S ] coincides with G φ. The MGR problem is related to the well-known class of generalized network problems, most of which are NP-hard, like the generalized Minimum Spanning Tree problem. The MGR is a generalization of the multicolored clique problem, which is known to be W [ 1 ] -hard when parameterized by the number of colors. Thus, MGR remains W [ 1 ] -hard, when parameterized by the size of the cluster graph. These results imply that the MGR problem is W [ 1 ] -hard when parameterized by any graph parameter on G φ , among which lies treewidth. Consequently, we look at the instances of the problem in which both the number of color classes and the treewidth of G φ are unbounded. We consider three natural such graph classes: chordal graphs, convex bipartite graphs and 2-dimensional grid graphs. We show that MGR is NP-complete when G φ is either chordal, biconvex bipartite, complete bipartite or a 2-dimensional grid. Our reductions show that the problem remains hard even when the maximum number of vertices in a color class is 3. In the case of the grid, the hardness holds even for graphs with bounded degree. We provide a complexity dichotomy with respect to cluster size. [ABSTRACT FROM AUTHOR]

In this paper, we introduce several new construction techniques of linear complimentary dual (LCD) codes. First, we show that if a LCD code is fixed by a transitive automorphism group, then the punctured code is also LCD. We show that several important families such as anti-primitive BCH codes and extended Gabidulin codes are LCD. Finally relationships among self-dual codes, λ-orthogonal matrices and LCD codes are studied. As an application we give LCD codes from Paley-type bipartite graph and from punctured MacDonalds codes. Further, we give a bound on some LCD codes. [ABSTRACT FROM AUTHOR]

Temporary ponds are small‐sized limnic systems that dry periodically. The length of the wet phase defines the hydroregime and determines community assembly in temporary ponds. Zooplankton species have adapted to desiccation by adopting some dormant strategies, such as the formation of resting stages. Hatching from resting stages is a source of recolonization after drought events and the composition of hatching taxa is also influenced by hydroregime. We compared metacommunity structure and composition of the dormant sub‐community (resting stages); the pioneer active sub‐community (fauna present immediately after inundation of ponds); and the cumulative active sub‐community (fauna present at the initial, middle and final phases of hydroperiod) in a set of temporary ponds with semipermanent and seasonal hydroregimes in two areas with mediterranean climate: central Chile and eastern Spain. We aimed to determine the influence of hydroregime and identify whether metacommunity patterns are consistent between regions sharing a mediterranean climate. We selected five semipermanent and five seasonal ponds in each region to sample sediments and active zooplankton sub‐communities. By combining hatching experiments from the sediments with direct counts of active zooplankton from the field samples, we gathered data on both dormant and active sub‐communities to build unweighted bipartite networks of species occurrences in each pond. The obtained networks were analysed to determine seasonal trends in structural features of the metacommunities (diversity, nestedness and modularity) and their relation to hydroregime (semipermanent and seasonal) and geographical location (Chile and Spain). We observed consistent differences in community structure when comparing sub‐communities at different successional stages (dormant, pioneer active and cumulative active) and with different hydroregimes (semipermanent vs. seasonal). Both α‐ and γ‐diversity showed a consistent trend, being highest in cumulative active sub‐communities and lowest in dormant ones, and were consistently higher in seasonal ponds, regardless of the region. In addition, β‐diversity was higher in the pioneer active sub‐community in both regions, with no significant differences between hydroregimes. The species composition of cumulative active sub‐communities were less heterogeneous than that of the pioneer and dormant ones. No consistent patterns were found in modularity and nestedness values across sub‐communities and hydroregimes. In agreement with our hypotheses, we observed a gradual accumulation of taxa as well as community homogenization over time in both regions. Contrary to our expectations, hydroregime did not affect these patterns and, surprisingly, shorter hydroperiods exhibited higher regional diversity. Our results suggest that hydroregime as a single variable does not have a strong explanatory power for metacommunity assembly of temporary ponds. Therefore, a more comprehensive theory is needed to anticipate the effects of the upcoming hydroperiod shortening. [ABSTRACT FROM AUTHOR]

An edge e $e$ of a matching covered graph G $G$ is removable if G − e $G-e$ is also matching covered. The notion of removable edge arises in connection with ear decompositions of matching covered graphs introduced by Lovász and Plummer. A nonbipartite matching covered graph G $G$ is a brick if it is free of nontrivial tight cuts. Carvalho, Lucchesi and Murty proved that every brick other than K 4 ${K}_{4}$ and C 6 ¯ $\bar{{C}_{6}}$ has at least Δ − 2 ${\rm{\Delta }}-2$ removable edges. A brick G $G$ is near‐bipartite if it has a pair of edges {e 1 , e 2 } $\{{e}_{1},{e}_{2}\}$ such that G −{e 1 , e 2 } $G-\{{e}_{1},{e}_{2}\}$ is a bipartite matching covered graph. In this paper, we show that in a near‐bipartite brick G $G$ with at least six vertices, every vertex of G $G$, except at most six vertices of degree three contained in two disjoint triangles, is incident with at most two nonremovable edges; consequently, G $G$ has at least | V( G ) | − 6 2 $\frac{|V(G)|-6}{2}$ removable edges. Moreover, all graphs attaining this lower bound are characterized. [ABSTRACT FROM AUTHOR]

Network analysis has become a crucial tool in genetic research, enabling the exploration of associations between genes and diseases. Its utility extends beyond genetics to include the assessment of environmental factors. Unipartite network analysis is commonly used in genomics to visualize initial insights and relationships among variables. Syndromic diseases, such as metabolic syndrome, are characterized by the simultaneous occurrence of various signs, symptoms, and clinicopathological features. Metabolic syndrome encompasses hypertension, diabetes, obesity, and dyslipidemia, and both genetic and environmental factors contribute to its development. Given that relevant data often consist of distinct sets of variables, a more intuitive visualization method is needed. This study applied multipartite network analysis as an effective method to understand the associations among genetic, environmental, and disease components in syndromic diseases. We considered three distinct variable sets: genetic factors, environmental factors, and disease components. The process involved projecting a tripartite network onto a two-mode bipartite network and then simplifying it into a one-mode network. This approach facilitated the visualization of relationships among factors across different sets and within individual sets. To transition from multipartite to unipartite networks, we suggest both sequential and concurrent projection methods. Data from the Korean Association Resource (KARE) project were utilized, including 352,228 SNPs from 8840 individuals, alongside information on environmental factors such as lifestyle, dietary, and socioeconomic factors. The single-SNP analysis step filtered SNPs, supplemented by reference SNPs reported in a genome-wide association study catalog. The resulting network patterns differed significantly by sex: demographic factors and fat intake were crucial for women, while alcohol consumption was central for men. Indirect relationships were identified through projected bipartite networks, revealing that SNPs such as rs4244457, rs2156552, and rs10899345 had lifestyle interactions on metabolic components. Our approach offers several advantages: it simplifies the visualization of complex relationships among different datasets, identifies environmental interactions, and provides insights into SNP clusters sharing common environmental factors and metabolic components. This framework provides a comprehensive approach to elucidate the mechanisms underlying complex diseases like metabolic syndrome. [ABSTRACT FROM AUTHOR]

A set D ⊆ V of a graph G = (V , E) is called a connected power dominating set of G if G [ D ] , the subgraph induced by D , is connected and every vertex in the graph can be observed from D , following the two observation rules for power system monitoring: Rule 1 : if v ∈ D , then v can observe itself and all its neighbors, and Rule 2 : for an already observed vertex whose all neighbors except one are observed, then the only unobserved neighbor becomes observed as well. Given a graph G , Minimum Connected Power Domination is to find a connected power dominating set of minimum cardinality of G and Decide Connected Power Domination is the decision version of Minimum Connected Power Domination. Decide Connected Power Domination is known to be N P -complete for general graphs. In this paper, we prove that Decide Connected Power Domination remains N P -complete for star-convex bipartite graphs, perfect elimination bipartite graphs and split graphs. This answers some open problems posed in [B. Brimkov, D. Mikesell and L. Smith, Connected power domination in graphs, J. Comb. Optim. 38(1) (2019) 292–315]. On the positive side, we show that Minimum Connected Power Domination is polynomial-time solvable for chain graphs, a proper subclass of perfect elimination bipartite graph, and for threshold graphs, a proper subclass of split graphs. Further, we show that Minimum Connected Power Domination cannot be approximated within (1 −) ln | V | for any > 0 unless P = N P , for bipartite graphs as well as for chordal graphs. Finally, we show that Minimum Connected Power Domination is APX -hard for bounded degree graphs. [ABSTRACT FROM AUTHOR]

In this paper, we present a noise-robust approach for the 3D pose estimation of multiple people using appearance similarity. The common methods identify the cross-view correspondences between the detected keypoints and determine their association with a specific person by measuring the distances between the epipolar lines and the joint locations of the 2D keypoints across all the views. Although existing methods achieve remarkable accuracy, they are still sensitive to camera calibration, making them unsuitable for noisy environments where any of the cameras slightly change angle or position. To address these limitations and fix camera calibration error in real-time, we propose a framework for 3D pose estimation which uses appearance similarity. In the proposed framework, we detect the 2D keypoints and extract the appearance feature and transfer it to the central server. The central server uses geometrical affinity and appearance similarity to match the detected 2D human poses to each person. Then, it compares these two groups to identify calibration errors. If a camera with the wrong calibration is identified, the central server fixes the calibration error, ensuring accuracy in the 3D reconstruction of skeletons. In the experimental environment, we verified that the proposed algorithm is robust against false geometrical errors. It achieves around 11.5% and 8% improvement in the accuracy of 3D pose estimation on the Campus and Shelf datasets, respectively. [ABSTRACT FROM AUTHOR]

Simple Summary: This study investigates the complex interactions between quill mites of the family Syringophilidae and starlings. We identified five species of quill mites infesting 24 species of starlings, uncovering intricate host–parasite dynamics across the Palaearctic, Afrotropical, Oriental, and Oceanian zoogeographical regions. A detailed statistical analysis of the Picobiinae–Sturnidae network revealed low connectivity but high modularity, indicating specific relationships between the mites and their starling hosts. The network structure demonstrated four distinct modules, highlighting the specialised and compartmentalised characteristics of these associations. Furthermore, the distribution of Picobia mites was found to align with the phylogeny of their starling hosts, with particular mites targeting specific starling clades. The social and breeding behaviours of starlings were observed to contribute to the high prevalence of these mites. This comprehensive network analysis provides new insights into the ecological dynamics of host–parasite interactions. The subfamily Picobiinae (Acariformes: Syringophilidae) comprises obligate and permanent parasites of birds found exclusively in the quills of contour feathers. We studied associations of picobiine mites with birds of the family Sturnidae (Aves: Passeriformes) across the Palaearctic, Afrotropical, Oriental, and Oceanian zoogeographical regions. Among the 414 examined bird individuals belonging to 44 species (35.2% of all sturnids), 103 individuals from 24 species (54.5% of examined species) were parasitised by quill mites. The diversity of mites was represented by five species, including one newly described, Picobia malayi Patan and Skoracki sp. n. Statistical analysis of the Picobiinae–Sturnidae bipartite network demonstrated a low connectance value (Con = 0.20) and high modularity, with significant differences in the H2′ specialisation index compared to null model values. The network structure, characterised by four distinct modules, highlighted the specificity and limited host range of the Picobiinae–Sturnidae associations. The distribution of Picobia species among starlings was congruent with the phylogeny of their hosts, with different mites parasitising specific clades of starlings. Additionally, the findings suggest that the social and breeding behaviours of starlings influence quite a high prevalence. Finally, our studies support the validity of museum collections to study these parasitic interactions. [ABSTRACT FROM AUTHOR]

Chain graphs and threshold graphs play a very important role in Spectral Graph Theory, since the maximizers for the largest eigenvalue of the adjacency matrix (for graphs of fixed order and size, either connected or disconnected) belong to these classes (threshold graphs in the general case, and chain graphs in the bipartite case). Nesting in the neighborhood of vertices in these graphs has gained the attention of various researchers. Motivated by this structure, we generalize and define a new class of graphs named it as 'partial threshold graphs' and study the properties. In this article, we give bounds and expressions for the Wiener index and Hyper-Wiener index of a partial threshold graph. We extend the study further and give a set of integers, except which every other integer is the Wiener index of some partial threshold graph. The highlight of the article is an algorithm for the inverse Wiener index problem of partial threshold graphs. [ABSTRACT FROM AUTHOR]

This paper introduces state polynomials, i.e., polynomials in noncommuting variables and formal states of their products. A state analog of Artin's solution to Hilbert's 17th problem is proved showing that state polynomials, positive over all matrices and matricial states, are sums of squares with denominators. Somewhat surprisingly, it is also established that a Krivine–Stengle Positivstellensatz fails to hold in the state polynomial setting. Further, archimedean Positivstellensätze in the spirit of Putinar and Helton–McCullough are presented leading to a hierarchy of semidefinite relaxations converging monotonically to the optimum of a state polynomial subject to state constraints. This hierarchy can be seen as a state analog of the Lasserre hierarchy for optimization of polynomials, and the Navascués–Pironio–Acín scheme for optimization of noncommutative polynomials. The motivation behind this theory arises from the study of correlations in quantum networks. Determining the maximal quantum violation of a polynomial Bell inequality for an arbitrary network is reformulated as a state polynomial optimization problem. Several examples of quadratic Bell inequalities in the bipartite and the bilocal tripartite scenario are analyzed. To reduce the size of the constructed SDPs, sparsity, sign symmetry and conditional expectation of the observables' group structure are exploited. To obtain the above-mentioned results, techniques from noncommutative algebra, real algebraic geometry, operator theory, and convex optimization are employed. [ABSTRACT FROM AUTHOR]

In this paper, we use semidefinite programming and representation theory to compute new lower bounds on the crossing number of the complete bipartite graph K m , n , extending a method from de Klerk et al. (SIAM J Discrete Math 20:189–202, 2006) and the subsequent reduction by De Klerk, Pasechnik and Schrijver (Math Prog Ser A and B 109:613–624, 2007). We exploit the full symmetry of the problem using a novel decomposition technique. This results in a full block-diagonalization of the underlying matrix algebra, which we use to improve bounds on several concrete instances. Our results imply that cr (K 10 , n) ≥ 4.87057 n 2 - 10 n , cr (K 11 , n) ≥ 5.99939 n 2 - 12.5 n , cr (K 12 , n) ≥ 7.25579 n 2 - 15 n , cr (K 13 , n) ≥ 8.65675 n 2 - 18 n for all n. The latter three bounds are computed using a new and well-performing relaxation of the original semidefinite programming bound. This new relaxation is obtained by only requiring one small matrix block to be positive semidefinite. [ABSTRACT FROM AUTHOR]

Let G be a graph and d i be the degree of a vertex v i in G. For a symmetric real function f (x , y) , one can get an edge-weighted graph in such a way that for each edge v i v j of G , the weight of v i v j is assigned by f (d i , d j). Hence, we have a weighted adjacency matrix A f (G) of G , in which the ij -entry is equal to f (d i , d j) if v i v j ∈ E (G) and 0 otherwise. In this paper, we use a unified approach to deal with the spectral properties of A f (G) for f (x , y) to be the functions of graphical or topological function-indices. Firstly, we obtain uniform interlacing inequalities for the weighted adjacency eigenvalues. For the edge-weight functions defined by almost a half of popularly used topological indices, it can be shown that our inequalities cannot be improved. Secondly, we establish a uniform equivalent condition for a connected graph G to have m distinct weighted adjacency eigenvalues. As an application, a combinatorial characterization for a graph to have two and three distinct weighted adjacency eigenvalues is presented, respectively. Moreover, bipartite graphs and unicyclic graphs with three distinct weighted adjacency eigenvalues are characterized. This paper attempts to unify the spectral study for weighted adjacency matrices of graphs with degree-based edge-weights. [ABSTRACT FROM AUTHOR]

A tree T $T$ is said to be even if all pairs of vertices of degree one in T $T$ are joined by a path of even length. We conjecture that every r $r$‐regular nonbipartite connected graph G $G$ has a spanning even tree and verify this conjecture when G $G$ has a 2‐factor. Well‐known results of Petersen and Hanson et al. imply that the only remaining unsolved case is when r $r$ is odd and G $G$ has at least r $r$ bridges. We investigate this case further and propose some related conjectures. [ABSTRACT FROM AUTHOR]

Given a graph L $L$, the Turán number ex(n,L) $\text{ex}(n,L)$ is the maximum possible number of edges in an n $n$‐vertex L $L$‐free graph. The study of Turán number of graphs is a central topic in extremal graph theory. Although the celebrated Erdős‐Stone‐Simonovits theorem gives the asymptotic value of ex(n,L) $\text{ex}(n,L)$ for nonbipartite L $L$, it is challenging in general to determine the exact value of ex(n,L) $\text{ex}(n,L)$ for χ(L)≥3 $\chi (L)\ge 3$. The odd‐ballooning of H $H$ is a graph such that each edge of H $H$ is replaced by an odd cycle and all new vertices of odd cycles are distinct. Here the length of odd cycles is not necessarily equal. The exact value of Turán number of the odd‐ballooning of H $H$ is previously known for H $H$ being a cycle, a path, a tree with assumptions, and K2,3 ${K}_{2,3}$. In this paper, we manage to obtain the exact value of Turán number of the odd‐ballooning of Ks,t ${K}_{s,t}$ with 2≤s≤t $2\le s\le t$, where (s,t)∉{(2,2),(2,3)} $(s,t)\notin \{(2,2),(2,3)\}$ and each odd cycle has length at least five. [ABSTRACT FROM AUTHOR]

We consider the stochastic matching model on a non-bipartite compatibility graph and analyze the impact of adding an edge to the expected number of items in the system. One may see adding an edge as increasing the flexibility of the system, for example, asking a family registering for social housing to list fewer requirements in order to be compatible with more housing units. Therefore, it may be natural to think that adding edges to the compatibility graph will lead to a decrease in the expected number of items in the system and the waiting time to be assigned. In our previous work, we proved this is not always true for the First Come First Matched discipline and provided sufficient conditions for the existence of the performance paradox: despite a new edge in the compatibility graph, the expected total number of items can increase. These sufficient conditions are related to the heavy-traffic assumptions in queueing systems. The intuition behind this is that the performance paradox occurs when the added edge in the compatibility graph disrupts the draining of a bottleneck. In this paper, we generalize this performance paradox result to a family of so-called greedy matching policies and explore the type of compatibility graphs where such a paradox occurs. Intuitively, a greedy matching policy never leaves compatible items unassigned, so the state space of the system consists of finite words of item classes that belong to an independent set of the compatibility graph. Some examples of greedy matching policies are First Come First Match, Match the Longest, Match the Shortest, Random, Priority. We prove several results about the existence of performance paradoxes for greedy disciplines for some family of graphs. More precisely, we prove several results about the lifting of the paradox from one graph to another one. For a certain family of graphs, we prove that there exists a paradox for the whole family of greedy policies. Most of these results are based on strong aggregation of Markov chains and graph theoretical properties. [ABSTRACT FROM AUTHOR]

This document is an editorial introduction to the second part of a special issue of the journal Queueing Systems. The special issue focuses on product forms, stochastic matching, and redundancy models in the analysis of queueing systems. The papers in this collection explore various aspects of matching queues and redundancy systems, including fluid approximation, heavy traffic limits, and different scheduling policies. The goal of the special issue is to highlight the connections between these models and their product-form stationary distributions, and to inspire new directions for future research. [Extracted from the article]

Social recommendation often incorporates trusted social links with user-item interactions to enhance rating prediction. Although methods that aggregate explicit social links have shown promising prospects, they are often constrained by the absence of explicit social data and the assumption of homogeneity, thus overlooking variations in social influence and consistency. These limitations hinder semantic expression and recommendation performance. Therefore, we propose a novel framework for social recommendation. First, we design a bipartite network embedding scheme, which learns vertex representations in the embedding space by modeling 1st-order explicit relations and higher-order implicit relations between vertices. Then, the similarity of the embedding vectors is used to extract top-k semantically consistent friends for each user. Next, we design an algorithm to assign a specific influence value to each user. Finally, we combine the top-k friends of the user and their influence values into an ensemble and add it as a regularization term to the rating prediction process of the user to correct the bias. Experiments on three real benchmark datasets show significant improvements in EISF over state-of-the-art methods. [ABSTRACT FROM AUTHOR]

In this study, we investigate the impact of introducing enterprise relationship to train machine learning (ML) algorithms on improving its ability of forecasting small and medium-sized enterprises' (SMEs) credit risk in supply chain finance (SCF). First, we incorporate attributes of SME node in the CEs-SMEs network, a bipartite network constructed with transaction data in the Chinese automobile industry, into financial indicators to train ML algorithms for improving forecasting performance. Second, we employ the weighted one-mode projection approach to extract a projected-SMEs network that reveals the relationship among SMEs from the CEs-SMEs network and examine whether the ML algorithms' forecasting performances is improved when considering attributes in the projected-SMEs network. Third, we analyze the correlation between SME's credit risk and individual network attribute to specifically understand the impact of enterprise relationship on credit risk. Overall, the empirical results indicate that the forecasting performance is obviously better when enterprise transaction relationship is considered, and it is further enhanced after we apply weighted one-mode projection approach. Meanwhile, the variable importance analysis and the binomial logistic regression demonstrate how significantly each network attribute is correlated with credit risk, and the discussion on partial dependence plot shows that SMEs with large degree are non-risky generally. [ABSTRACT FROM AUTHOR]

In this paper, we define the zero-divisor graph of a meethyperlattice with respect to a hyperideal. We prove the diameter of a P-hyperlattice and Nakano hyperlattice are at most 3 and 4 respectively. We obtain that the zero-divisor graph with respect to the intersection of two prime hyperideals is complete bipartite. We prove certain properties of these zero-divisor graphs with suitable examples. [ABSTRACT FROM AUTHOR]

In the realm of credit card fraud detection, the landscape is continually evolving, demanding innovative approaches to stay ahead of increasingly sophisticated fraudulent activities. Our research pioneers a groundbreaking methodology that amalgamates the power of bipartite graph visualization with advanced machine learning techniques. This fusion yields a comprehensive framework capable of effectively evaluating the efficacy of a random forest classifier in uncovering fraudulent credit card transactions. Our study showcases the compelling application of this methodology, offering a paradigm shift in how we analyze and understand credit card fraud detection systems. By seamlessly integrating machine learning algorithms with network analysis, we provide a holistic view of the data, unveiling intricate patterns hidden within. At the heart of our approach lies the innovative use of bipartite graphs, which serve as a dynamic visual bridge between model predictions and real-world outcomes. This visual representation not only enhances interpretability but also facilitates a deeper understanding of the classifier’s performance. By visually mapping the relationships between transactions and their respective classifications, our methodology offers actionable insights into both successful detection and potential areas for improvement. Empowering analysts and stakeholders, our approach facilitates informed decisionmaking by enabling them to fine-tune model parameters and enhance the overall effectiveness of fraud detection systems. Through this synergy between cutting-edge machine learning and network analysis techniques, we provide a powerful tool to combat the critical challenge of credit card fraud prevention. Step into the future of fraud detection with our innovative methodology, where every transaction is scrutinized with precision, and where security is not just a possibility, but a promise fulfilled. [ABSTRACT FROM AUTHOR]

Host–parasite interactions are influenced by present and past eco‐evolutionary interactions and the local environment. An ecological community defines the potential host range of each parasite and the potential parasite diversity of each host species. Past and present processes translate potential to realised interaction niches of parasite and host species. Host–parasite interactions are antagonistic, which may slow the saturation of their interaction niches. Intervality, a property of bipartite networks, measures saturation of interaction niches. Intervality of a community increases as the interaction niches of species of one guild (e.g. hosts) become saturated for their interactions with another guild (e.g. parasites). Characteristics driving intervality in host and parasite communities are largely unknown, as well as the effect of environmental change on intervality of these communities. In our study, we assess if the characteristics ‘phylogenetic relatedness' and ‘overlap in ecological interactions' explain intervality of rodent host–helminth parasite communities. In addition, we contrast intervality of these communities from habitats that differ in their history of human‐driven modification. We performed the analyses for the interaction niches of both parasites and hosts, independently. Our results indicated that host and parasite communities were non‐interval or significantly less interval than expected by chance. Phylogenetic relatedness and overlap in ecological interactions did not explain the maximum values of intervality. We speculate that antagonistic coevolution in host–parasite communities may hinder communities to reach saturation, which would explain why it is difficult to find the characteristics that explain intervality of a community. Interestingly, intervality of the interaction niche of parasites (host range) increased with habitat modification (i.e. saturation increased), whereas intervality of the interaction niche of hosts (parasite diversity) decreased as habitat modification increased. These opposite trends suggest that interaction niches of parasites and hosts respond differently to habitat modification. [ABSTRACT FROM AUTHOR]

For f : R 2 → R $f:{{\mathbb{R}}}^{2}\to {\mathbb{R}}$, let Γ R( f ) ${{\rm{\Gamma }}}_{{\mathbb{R}}}(f)$ be a two‐dimensional algebraically defined graph, that is, a bipartite graph where each partite set is a copy of R 2 ${{\mathbb{R}}}^{2}$ and two vertices (a , a 2 ) $(a,{a}_{2})$ and [x , x 2 ] $[x,{x}_{2}]$ are adjacent if and only if a 2 + x 2 = f(a , x ) ${a}_{2}+{x}_{2}=f(a,x)$. It is known that Γ R(X Y ) ${{\rm{\Gamma }}}_{{\mathbb{R}}}(XY)$ has girth 6 and can be extended to the point‐line incidence graph of the classical real projective plane. However, it was unknown whether there exists f ∈ R[X , Y ] $f\in {\mathbb{R}}[X,Y]$ such that Γ R( f ) ${{\rm{\Gamma }}}_{{\mathbb{R}}}(f)$ has girth 6 and is nonisomorphic to Γ R(X Y ) ${{\rm{\Gamma }}}_{{\mathbb{R}}}(XY)$. This paper answers this question affirmatively and thus provides a construction of a nonclassical real projective plane. This paper also studies the diameter and girth of Γ R( f ) ${{\rm{\Gamma }}}_{{\mathbb{R}}}(f)$ for families of bivariate functions f $f$. [ABSTRACT FROM AUTHOR]

If G = (V , E) is a (finite and simple) graph, we call an independent set X a gated independent set in G if for each x ∈ X , there exists a neighbor y of x such that (X ∖ { x }) ∪ { y } is an independent set in G. We define the gated independence number gi (G) of G to be the maximum cardinality of a gated independent set in G. We demonstrate that the gated independence number is closely related to both matching and domination parameters of graphs. We prove that the inequalities im (G) ⩽ gi (G) ⩽ m ur (G) hold for every graph G , where im (G) and m ur (G) denote the induced and uniquely restricted matching numbers of G. On the other hand, we show that γ i (G) ⩽ gi (G) and γ pr (G) ⩽ 2 gi (G) for every graph G without any isolated vertex, where γ i (G) and γ pr (G) denote the independence and paired domination numbers. Furthermore, we provide bounds on the gated independence number involving the order, size and maximum degree. In particular, we prove that gi (G) ⩾ n 5 for every n -vertex subcubic graph G without any isolated vertex or any component isomorphic to K 3 , 3 , and gi (B) ⩽ 3 n 8 for every n -vertex connected cubic bipartite graph B. [ABSTRACT FROM AUTHOR]

Background: Conducting traditional wet experiments to guide drug development is an expensive, time-consuming and risky process. Analyzing drug function and repositioning plays a key role in identifying new therapeutic potential of approved drugs and discovering therapeutic approaches for untreated diseases. Exploring drug-disease associations has far-reaching implications for identifying disease pathogenesis and treatment. However, reliable detection of drug-disease relationships via traditional methods is costly and slow. Therefore, investigations into computational methods for predicting drug-disease associations are currently needed. Results: This paper presents a novel drug-disease association prediction method, RAFGAE. First, RAFGAE integrates known associations between diseases and drugs into a bipartite network. Second, RAFGAE designs the Re_GAT framework, which includes multilayer graph attention networks (GATs) and two residual networks. The multilayer GATs are utilized for learning the node embeddings, which is achieved by aggregating information from multihop neighbors. The two residual networks are used to alleviate the deep network oversmoothing problem, and an attention mechanism is introduced to combine the node embeddings from different attention layers. Third, two graph autoencoders (GAEs) with collaborative training are constructed to simulate label propagation to predict potential associations. On this basis, free multiscale adversarial training (FMAT) is introduced. FMAT enhances node feature quality through small gradient adversarial perturbation iterations, improving the prediction performance. Finally, tenfold cross-validations on two benchmark datasets show that RAFGAE outperforms current methods. In addition, case studies have confirmed that RAFGAE can detect novel drug-disease associations. Conclusions: The comprehensive experimental results validate the utility and accuracy of RAFGAE. We believe that this method may serve as an excellent predictor for identifying unobserved disease-drug associations. [ABSTRACT FROM AUTHOR]

The conditional fractional matching preclusion number (CFMP number for short) fmp1(G) of a graph G is the minimum number of edges whose deletion results in a graph without isolated vertices and without fractional perfect matchings. In this paper, we study the CFMP number of complete graphs, complete bipartite graphs and twisted cubes. Also, we give Nordhaus–Gaddum-type results for the CFMP numbers of general graphs. [ABSTRACT FROM AUTHOR]

We call a proper edge coloring of a graph G $G$ a B‐coloring if every 4‐cycle of G $G$ is colored with four different colors. Let q B( G ) ${q}_{B}(G)$ denote the smallest number of colors needed for a B‐coloring of G $G$. Motivated by earlier papers on B‐colorings, here we consider q B( G ) ${q}_{B}(G)$ for planar and outerplanar graphs in terms of the maximum degree Δ = Δ( G ) ${\rm{\Delta }}={\rm{\Delta }}(G)$. We prove that q B( G ) ≤ 2 Δ + 8 ${q}_{B}(G)\le 2{\rm{\Delta }}+8$ for planar graphs, q B( G ) ≤ 2 Δ ${q}_{B}(G)\le 2{\rm{\Delta }}$ for bipartite planar graphs, and q B( G ) ≤ Δ + 1 ${q}_{B}(G)\le {\rm{\Delta }}+1$ for outerplanar graphs with Δ ≥ 4 ${\rm{\Delta }}\ge 4$. We conjecture that, for Δ ${\rm{\Delta }}$ sufficiently large, q B( G ) ≤ 2 Δ( G ) ${q}_{B}(G)\le 2{\rm{\Delta }}(G)$ for planar G $G$, and q B( G ) ≤ Δ( G ) ${q}_{B}(G)\le {\rm{\Delta }}(G)$ for outerplanar G $G$. [ABSTRACT FROM AUTHOR]

We consider the adjacency spectrum of cycle-spliced signed graphs (CSSG), i.e., signed graphs whose blocks are (independent) signed cycles. For a signed graph S, the nullity η(S) is the multiplicity of the 0-eigenvalue. The adjancency spectrum of cycle-spliced (signed) graphs is studied in the literature for the relation between the nullity η and the cyclomatic number c, in particular, it is known that 0 = η(S) = c(S) + 1. In this paper, nonsingular cycle-spliced bipartite signed graphs are characterized. For cycle-spliced signed graphs S having only odd cycles, we show that η(S) is 0 or 1. Finally, we compute the nullity of CSSGs consisting of at most three cycles. [ABSTRACT FROM AUTHOR]

A zero-one matrix |$M$| is said to contain another zero-one matrix |$A$| if we can delete some rows and columns of |$M$| and replace some |$1$| -entries with |$0$| -entries such that the resulting matrix is |$A$|⁠. The extremal number of |$A$|⁠ , denoted |$\operatorname{ex}(n,A)$|⁠ , is the maximum number of |$1$| -entries that an |$n\times n$| zero-one matrix can have without containing |$A$|⁠. The systematic study of this function for various patterns |$A$| goes back to the work of Füredi and Hajnal from 1992, and the field has many connections to other areas of mathematics and theoretical computer science. The problem has been particularly extensively studied for so-called acyclic matrices, but very little is known about the general case (i.e. the case where |$A$| is not necessarily acyclic). We prove the first asymptotically tight general result by showing that if |$A$| has at most |$t$| |$1$| -entries in every row, then |$\operatorname{ex}(n,A)\leq n^{2-1/t+o(1)}$|⁠. This verifies a conjecture of Methuku and Tomon. Our result also provides the first tight general bound for the extremal number of vertex-ordered graphs with interval chromatic number |$2$|⁠ , generalizing a celebrated result of Füredi and Alon, Krivelevich, and Sudakov about the (unordered) extremal number of bipartite graphs with maximum degree |$t$| in one of the vertex classes. [ABSTRACT FROM AUTHOR]

Climate change is altering species distribution and modifying interactions in microbial communities. Understanding microbial community structure and their interactions is crucial to interpreting ecosystem responses to climate change. Here, we examined the assemblages of stream bacteria and fungi, and the associations between the two groups along elevational gradients in two regions with contrasting precipitation and temperature, that is the Galong and Qilian mountains of the Tibetan Plateau. In the wetter and warmer region, the species richness significantly increased and decreased with elevation for bacteria and fungi, respectively, while were nonsignificant in the drier and colder region. Their bipartite network structure was also different by showing significant increases in connectance and nestedness towards higher elevations only in the wetter and warmer region. In addition, these correlation network structure generally exhibited similar positive association with species richness in the wetter and warmer region and the drier and colder region. In the wetter and warmer region, climatic change along elevation was more important in determining connectance and nestedness, whereas microbial species richness exerted a stronger influence on network structure and robustness in the drier and colder region. These findings indicate substantial forthcoming changes in microbial diversity and network structure in warming climates, especially in wetter and warmer regions on Earth, advancing the understanding of microbial bipartite interactions' response to climate change. [ABSTRACT FROM AUTHOR]

The bipartite polarization problem is an optimization problem where the goal is to find the highest polarized bipartition on a weighted and labeled graph that represents a debate developed through some social network, where nodes represent user's opinions and edges agreement or disagreement between users. This problem can be seen as a generalization of the maxcut problem, and in previous work, approximate solutions and exact solutions have been obtained for real instances obtained from Reddit discussions, showing that such real instances seem to be very easy to solve. In this paper, we further investigate the complexity of this problem by introducing an instance generation model where a single parameter controls the polarization of the instances in such a way that this correlates with the average complexity to solve those instances. The average complexity results we obtain are consistent with our hypothesis: the higher the polarization of the instance, the easier is to find the corresponding polarized bipartition. In view of the experimental results, it is computationally feasible to implement transparent mechanisms to monitor polarization on online discussions and to inform about solutions for creating healthier social media environments. [ABSTRACT FROM AUTHOR]

In the paper, we introduce the signless Laplacian A B C -matrix Q ̃ (G) = D ¯ (G) + A ̃ (G) , where D ¯ (G) is the diagonal matrix of A B C -degrees and A ̃ (G) is the A B C -matrix of G. The eigenvalues of the matrix Q ̃ (G) are the signless Laplacian A B C -eigenvalues of G. We give some basic properties of the matrix Q ̃ (G) , which includes relating independence number and clique number with signless Laplacian A B C -eigenvalues. For bipartite graphs, we show that the signless Laplacian A B C -spectrum and the Laplacian A B C -spectrum are the same. We characterize the graphs with exactly two distinct signless Laplacian A B C -eigenvalues. Also, we consider the problem of the characterization of the graphs with exactly three distinct signless Laplacian A B C -eigenvalues and solve it for bipartite graphs and, in some cases, for non-bipartite graphs. We also introduce the concept of the trace norm of the matrix Q ̃ (G) − t r (Q ̃ (G)) n I , called the signless Laplacian A B C -energy of G. We obtain some upper and lower bounds for signless Laplacian A B C -energy and characterize the extremal graphs attaining it. Further, for graphs of order at most 6, we compare the signless Laplacian energy and the A B C -energy with the signless Laplacian A B C -energy and found that the latter behaves well, as there is a single pair of graphs with the same signless Laplacian A B C -energy unlike the 26 pairs of graphs with same signless Laplacian energy and eight pairs of graphs with the same A B C -energy. [ABSTRACT FROM AUTHOR]

The mobility pattern of a population plays a key role in the spread of epidemics. Despite extensive work on epidemic spreading, little attention has been paid to the impact of subpopulation size. This paper investigates the spread of epidemics on a bipartite metapopulation network considering recurrent mobility patterns and different sizes of subpopulations. With the Markovian process approach, the epidemic threshold can be predicted as a function of subpopulation size and epidemic parameters. Simulation and theoretical results indicate that there exists a critical mobility intensity below which the epidemic will be eliminated, while limiting the size of the subpopulation can suppress the epidemic. Additionally, the epidemic threshold will approach zero when the size of the public area is large. The results can help the prevention of epidemic spreading under recurrent crowd mobility. [ABSTRACT FROM AUTHOR]

We investigate a graph-theoretic approach to the problem of distinguishing quantum product states in the fundamental quantum communication framework called local operations and classical communication (LOCC). We identify chordality as the key graph structure that drives distinguishability in one-way LOCC, and we derive a one-way LOCC characterization for chordal graphs that establishes a connection with the theory of matrix completions. We also derive minimality conditions on graph parameters that allow for the determination of indistinguishability of states. We present a number of applications and examples built on these results. [ABSTRACT FROM AUTHOR]

Let a = (a i) i ≥ 1 be a sequence in a field F , and f : F × F → F be a function such that f (a i , a i) ≠ 0 for all i ≥ 1. For any tournament T over [ n ] , consider the n × n symmetric matrix M T with zero diagonal whose (i , j) th entry (for i < j) is f (a i , a j) if i → j in T , and f (a j , a i) if j → i in T. It is known [3] that if T is a uniformly random tournament over [ n ] , then rank (M T) ≥ (1 2 − o (1)) n with high probability when char (F) ≠ 2 and f is a linear function. In this paper, we investigate the other extremal question: how low can the ranks of such matrices be? We work with sequences a that take only two distinct values, so the rank of any such n × n matrix is at least n / 2. First, we show that the rank of any such matrix depends on whether an associated bipartite graph has certain eigenvalues of high multiplicity. Using this, we show that if f is linear, then there are real matrices M T (f ; a) of rank at most n 2 + O (1). For rational matrices, we show that for each ε > 0 we can find a sequence a (ε) for which there are matrices M T (f ; a) of rank at most (1 2 + ε) n + O (1). These matrices are constructed from symmetric designs, and we also use them to produce bisection-closed families of size greater than ⌊ 3 n / 2 ⌋ − 2 for n ≤ 15 , which improves the previously best known bound given in [5]. [ABSTRACT FROM AUTHOR]

Noncoding RNA (NcRNA)-protein interactions (NPIs) play fundamentally important roles in carrying out cellular activities. Although various predictors based on molecular features and graphs have been published to boost the identification of NPIs, most of them often ignore the information between known NPIs or exhibit insufficient learning ability from graphs, posing a significant challenge in effectively identifying NPIs. To develop a more reliable and accurate predictor for NPIs, in this article, we propose NPI-DCGNN, an end-to-end NPI predictor based on a dual-channel graph neural network (DCGNN). NPI-DCGNN initially treats the known NPIs as an ncRNA-protein bipartite graph. Subsequently, for each ncRNA-protein pair, NPI-DCGNN extracts two local subgraphs centered around the ncRNA and protein, respectively, from the bipartite graph. After that, it utilizes a dual-channel graph representation learning layer based on GNN to generate high-level feature representations for the ncRNA-protein pair. Finally, it employs a fully connected network and output layer to predict whether an interaction exists between the pair of ncRNA and protein. Experimental results on four experimentally validated datasets demonstrate that NPI-DCGNN outperforms several state-of-the-art NPI predictors. Our case studies on the NPInter database further demonstrate the prediction power of NPI-DCGNN in predicting NPIs. With the availability of the source codes (https://github.com/zhangxin11111/NPI-DCGNN), we anticipate that NPI-DCGNN could facilitate the studies of ncRNA interactome by providing highly reliable NPI candidates for further experimental validation. [ABSTRACT FROM AUTHOR]

Based on the complex network, the relationship in the real complex system can be modeled, and the bipartite network is a special complex network, which can describe the complex system containing two kinds of objects. Although existing bipartite networks can model complex systems, conventional methods are restricted to a couple of limitations. (1) The dynamic interaction between nodes cannot be described over time. (2) The implicit features of nodes in the network cannot be effectively mined. Based on these, this paper proposes a dynamic bipartite network model (DBN) to model the dynamic interaction between two types of objects in real complex systems, and mine the structure features and preference features of nodes in the network. First, the dynamic interaction between two types of objects in a complex system is modeled as a dynamic bipartite network, which can reflect the interaction between objects in each time slice. Then, the structure features and preference features of each time slice are mined based on the dynamic bipartite network, where the structure features reflect the dynamic structural changes of the nodes, and the preference features reflect the potential preferences of the nodes. Finally, the features of each time slice are fused and input into the gate recurrent unit model to predict the interaction between nodes. Extensive experiments are performed on a large-scale real complex system. The results show that DBN significantly outperforms state-of-the-art prediction methods in terms of multiple evaluation metrics. [ABSTRACT FROM AUTHOR]

In crisp graph theory, there are numerous topological indices accessible, including the Misbalance Prodeg Index, which is one of the most well-known degree-based topological indexes. In crisp graphs, both vertices and edges have membership values of 1 or 0, whereas in fuzzy graphs, both vertices and edges have different memberships. This is an entire contrast to the crisp graph. In this paper, we introduce the Fuzzy Misbalance Prodeg Index of a fuzzy graph, which is a generalized form of the Misbalance Prodeg Index of a graph. We find bounds of this index and find bounds of certain classes of graphs such as path graph, cycle graph, complete graph, complete bipartite graph, and star graph. We give an algorithm to find the Fuzzy Misbalance Prodeg Index of a graph for the model of multi-criteria decision-making is established. We present applications from daily life in multi-criteria decision-making. We apply our obtained model of the Fuzzy Misbalance Prodeg Index for the multicriteria decision-making to the choice of the best supplier and we also show the graphical analysis of our index with the other indices that show how our index is better than other existing indices. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Central China Normal University is the property of Huazhong Normal University and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

The problem of Zarankiewicz asks for the maximum number of edges in a bipartite graph on n vertices which does not contain the complete bipartite graph K k , k as a subgraph. A classical theorem due to Kővári, Sós, and Turán says that this number of edges is O n 2 - 1 / k . An important variant of this problem is the analogous question in bipartite graphs with VC-dimension at most d, where d is a fixed integer such that k ≥ d ≥ 2 . A remarkable result of Fox et al. (J. Eur. Math. Soc. (JEMS) 19:1785–1810, 2017) with multiple applications in incidence geometry shows that, under this additional hypothesis, the number of edges in a bipartite graph on n vertices and with no copy of K k , k as a subgraph must be O n 2 - 1 / d . This theorem is sharp when k = d = 2 , because by design any K 2 , 2 -free graph automatically has VC-dimension at most 2, and there are well-known examples of such graphs with Ω n 3 / 2 edges. However, it turns out this phenomenon no longer carries through for any larger d. We show the following improved result: the maximum number of edges in bipartite graphs with no copies of K k , k and VC-dimension at most d is o (n 2 - 1 / d) , for every k ≥ d ≥ 3 . [ABSTRACT FROM AUTHOR]

Motivated by applications in the gig economy, we study approximation algorithms for a sequential pricing problem. The input is a bipartite graph G=(I,J,E) between individuals I and jobs J. The platform has a value of vj for matching job j to an individual worker. In order to find a matching, the platform can consider the edges (ij)∈E in any order and make a one-time take-it-or-leave-it offer of a price πij=w of its choosing to i for completing j. The worker accepts the offer with a known probability pijw; in this case, the job and the worker are irrevocably matched. What is the best way to make offers to maximize revenue and/or social welfare? The optimal algorithm is known to be NP-hard to compute (even if there is only a single job). With this in mind, we design efficient approximations to the optimal policy via a new random-order online contention resolution scheme (RO-OCRS) for matching. Our main result is a 0.456-balanced RO-OCRS in bipartite graphs and a 0.45-balanced RO-OCRS in general graphs. These algorithms improve on the recent bound of 12(1−e−2)≈0.432 and improve on the best-known lower bounds for the correlation gap of matching, despite applying to a significantly more restrictive setting. As a consequence of our online contention resolution scheme results, we obtain a 0.456-approximate algorithm for the sequential pricing problem. We further extend our results to settings where workers can only be contacted a limited number of times and show how to achieve improved results for this problem via improved algorithms for the well-studied stochastic probing problem. Funding: This work was supported by the National Science Foundation [Grant CCF2209520] and a gift from Amazon Research. [ABSTRACT FROM AUTHOR]

Three-dimensional multi-object tracking (MOT) using lidar point cloud data is crucial for applications in autonomous driving, smart cities, and robotic navigation. It involves identifying objects in point cloud sequence data and consistently assigning unique identities to them throughout the sequence. Occlusions can lead to missed detections, resulting in incorrect data associations and ID switches. To address these challenges, we propose a novel point cloud multi-object tracker called GBRTracker. Our method integrates an intra-frame graph structure into the backbone to extract and aggregate spatial neighborhood node features, significantly reducing detection misses. We construct an inter-frame bipartite graph for data association and design a sophisticated cost matrix based on the center, box size, velocity, and heading angle. Using a minimum-cost flow algorithm to achieve globally optimal matching, thereby reducing ID switches. For unmatched detections, we design a motion-based re-identification (ReID) feature embedding module, which uses velocity and the heading angle to calculate similarity and association probability, reconnecting them with their corresponding trajectory IDs or initializing new tracks. Our method maintains high accuracy and reliability, significantly reducing ID switches and trajectory fragmentation, even in challenging scenarios. We validate the effectiveness of GBRTracker through comparative and ablation experiments on the NuScenes and Waymo Open Datasets, demonstrating its superiority over state-of-the-art methods. [ABSTRACT FROM AUTHOR]

A graph G with four or more vertices is called bicritical if the removal of any pair of distinct vertices of G results in a graph with a perfect matching. A bicritical graph is minimal if the deletion of each edge results in a non-bicritical graph. Recently, Y. Zhang et al. and F. Lin et al. respectively showed that bicritical graphs without removable edges and minimal bricks have at least four cubic vertices. In this note, we show that minimal bicritical graphs also have at least four cubic vertices, so confirming O. Favaron and M. Shi's conjecture in the case of k = 2 on minimal k -factor-critical graphs. [ABSTRACT FROM AUTHOR]